most recent 30 from http://mathoverflow.net 2013-06-19T03:22:09Z http://mathoverflow.net/feeds/question/115457 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115457/existence-of-cut-based-pseudorandom-graphs-beating-the-random-graph Nick B. 2012-12-05T01:16:30Z 2012-12-06T20:50:59Z

<p>The question is simply this: Does there exist a (family of) graph $G=(V,E)$ such that $\max_{S\subset V} |E(S,S^c)- \frac{|S||S^C|}{2}|\leq o(n^{3/2})$. Such graphs would be very pseudorandom as the edge density of all their cuts would be extremely close to the expected value if we had picked each edge with probability a half. </p> <p>Background: As discussed in the following Math-overflow question <a href="http://mathoverflow.net/questions/53389/max-cut-value-in-a-random-graph" rel="nofollow">http://mathoverflow.net/questions/53389/max-cut-value-in-a-random-graph</a>, with high probability a random $G(n,\frac{1}{2})$ graph has a cut $(S,S^c)$ with more than $\frac{n^2}{8}+\Omega(n^{3/2})$ edges. This implies that the following max-deviation lower bound: For almost every $G=(V,E)$ we have,</p> <p>$ \max_{S\subset V} |E(S,S^c)- \frac{|S||S^C|}{2}| = \Omega(n^{3/2})$</p> <p>This lower bound means that simply by taking a random graph you cannot solve the above problem. </p> <p>It could be true that the above for amost every graph result actually holds for every graph and this quantity is always $\Omega(n^{3/2})$. A proof of this would be quite interesting and would give evidence to a conjecture that I have in mind.</p>

http://mathoverflow.net/questions/115457/existence-of-cut-based-pseudorandom-graphs-beating-the-random-graph/115641#115641 Kevin P. Costello 2012-12-06T20:50:59Z 2012-12-06T20:50:59Z

<p>This isn't a full solution, just a couple of observations too long to fit into a comment. </p> <p>First of all, it's worth noting that both of the "one-sided" versions of this statement are false. In the complete bipartite graph $K_{n/2,n/2}$, every cut satisfies $E(S,S^C) \geq \frac{1}{2}|S||S^C|$, and in the union of two disjoint copies of $K_{n/2}$ every cut satisfies $E(S,S^C) \leq \frac{1}{2}|S||S^C|$ (these examples can be modified by adding $O(n)$ edges so that their density is exactly $1/2$ if $n$ is a multiple of $4$). This rules out a number of arguments that attempt to construct (randomly or otherwise) an unusually dense cut. </p> <p>Secondly, the following weaker statement IS true: If $G$ is an $n/2$-regular graph, then there are disjoint subsets $S$ and $T$ such that $E(S,T) \geq \frac{1}{2}|S| |T| + \Omega(n^{3/2})$. A rough sketch of the argument is to take $S$ to be a random subset of the vertices where each vertex is in $S$ with probability $0.1$, then take $T$ to be all the vertices outside of $S$ having at least $|S|/2+0.01 \sqrt{n}$ neighbors in $S$. This automatically forces $E(S,T) \geq |S||T|/2+0.01 |T| \sqrt{n}$, so we just need to show that $|T|$ is large for some $S$. </p> <p>Each vertex is in $T$ with positive probability (this is where we need regularity), so the expected number of vertices in $T$ is at least $cn$. This means that some $S$ must have a $T$ at least this large. </p> <p>Unfortunately, this probably does not extend to an argument giving a cut across the whole graph, since the conclusion is one-sided. </p>