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?

Improve this question
$\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
    Commented 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$
    – Dustin G. Mixon
    Commented Dec 31, 2013 at 0:01

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .