Pseudorandom clique-free graphs

Anurag Bishnoi wrote a post about a recently finished preprint on pseudorandom clique-free graphs written by me, Anurag, and Valentina Pepe. We (slightly) improve a construction by Alon and Krivelevich from 1997.

Anurag's Math Blog

Pseudorandom graphs are graphs that in some way behaves like a random graph with the same edge density. One way in which this happens is as follows. In the random graph $latex G(n, p)$, with $latex p = p(n) leq 0.99$, a direct application of Chernoff bound implies that the probability of the following event approaches $latex 1$ as $latex n$ approaches infinity:

$latex |e(S, T) – p|S||T|| = O(sqrt{pn |S||T|}$

where $latex S,T$ are arbitrary subsets of vertices and $latex e(S,T)$ denotes the number of edges with one end vertex in $latex S$ and the other one in $latex T$.  Note that $latex p|S||T|$ is the expected number of edges between $latex S$ and $latex T$ in this model, and $latex sqrt{p(1 – p)|S||T|}$ is the standard deviation. Now let $latex G$ be a $latex d$-regular graph on $latex n$-vertices and let $latex lambda$ be the second largest…

View original post 804 more words


A New Math Blog

In the last few years, I became a reader of various math blogs. In a few days weeks I will publish my first proper post here. My idea of this blog is that I publish two or three posts per year. Each post will focus on a recent research project of mine and attempt to present it to a wider audience.