3
$\begingroup$

Fix $C>0$. I am interested in graphs with the following mixing property:

$$\Big|E(S,T)-\frac{1}{2}|S||T|\Big|\leq C\sqrt{|S||T|\max\{|S|,|T|\}}$$

for every disjoint $S,T\subseteq V$. Note that this is stronger than what the expander mixing lemma guarantees for expander graphs with $d=n/2$.

Has this particular property been studied already?

$\endgroup$
2
  • 5
    $\begingroup$ Such graphs cannot be arbitrarily large (for fixed $C$), because any sufficiently large graph of a given density will contain a copy of the complete bipartite graph $K_{m,m}$ for any fixed $m$, which will contradict your property for $m$ large enough depending on $C$. (Graphs obeying your property will have density about 1/2.) $\endgroup$
    – Terry Tao
    Dec 30, 2013 at 23:15
  • $\begingroup$ Wow, you're right. I ignored a log factor in $n$ on the right-hand side, thinking I didn't need it, but I do. For the sake of documentation, I found a lot of useful information by googling "graph discrepancy". $\endgroup$ Dec 31, 2013 at 0:01

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.