# Existence of (Cut-Based) pseudorandom graphs beating the random graph

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.

Background: As discussed in the following Math-overflow question Max cut value in a random graph, 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,

$\max_{S\subset V} |E(S,S^c)- \frac{|S||S^C|}{2}| = \Omega(n^{3/2})$

This lower bound means that simply by taking a random graph you cannot solve the above problem.

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.

-
If you look at a random partition into two parts of any graph with vertex degrees close to n/2, the variance of the number of edges across the cut is $\Theta(n^2)$, which is the same within a constant to what it is for random graphs. This proves nothing really, but I strongly suspect the worse of all $2^n$ cuts will still be $\Theta(n^{3/2})$ above expectation. – Brendan McKay Dec 5 '12 at 14:18
The approach of taking a random partition and analyzing higher moments would probably not be sufficiently strong to prove this. But one approach could be to use the fact that we know this for random graphs, and hence for graphs $O(n^{3/2})$ close to random graphs. And given a graph G we have to see what this non-randomness can give us. Maybe in graphs far away from random one can use a random partition to achieve this. (indeed if the relative density is bounded away from 1/2 this works)Also some have suggested that maybe \emph{discrepancy theory} is the keyword in this problem. – Nick B. Dec 5 '12 at 18:20

This isn't a full solution, just a couple of observations too long to fit into a comment.

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.

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$.

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.

Unfortunately, this probably does not extend to an argument giving a cut across the whole graph, since the conclusion is one-sided.

-
This is really interesting. I have two comments: First of all, Can't you deduce the general statement of your weak form a reduction: Let G=(V,E) be our graph and Take G1 and G2 to be two copies of G. Take G′=$G_1\cup G_2$ and now connect $v\in G_1$ with $u\in G_2$ if their preimage in G were not connected. Now the relative degree of each vertex would be 1/2 in G′. Now any cut ,or weak-cut, deviation in G′ will manifest itself with deviation in G losing a factor of 1/4 in the reduction. – Nick B. Dec 6 '12 at 22:22
We wouldn't be done with the reduction yet because the "cut" that we get in $G$ might be in the form $(S,T)$ such that $S\cap T\neq \emptyset$. But I think in that case if $S\cap T$ is large enough to be annoying, you should be able to still get the desired result by taking the intersection $S\cap T$ and taking a random cut across it. You basically reduce to the case that if a graph has relative density bounded away from 1/2 the above result is easy by taking random cuts. I hope the hand-wavy argument above actually goes through – Nick B. Dec 6 '12 at 22:53
Second comment: I don't see why your argument resolves the general case. I might be making a silly mistake but consider the following: Let $G$ be (a family) of counterexample to above,i.e. $|E(S,S^c)-|S||S^c|/2|\leq o(n^{3/2})$ .Then use your above construction to take $E(S,T)\geq 1/2 |S||T|+ \Omega(n^{3/2})$ .Let $U=(S\cup T)^c$. Apply the assumptions above to the cuts $(S, U\cup T)$ and $(T,S \cup U)$. This will imply that $E(S,U)≤\frac{|S||U|}{2}−\Omega(n^{3/2})$ and similarly for $(S,T)$. But this would imply a large deviation in the cut $(S\cup T,U)$. Doesn't it? – Nick B. Dec 6 '12 at 23:50