Q1: Consider a $2^n$ by $2^n$ bipartite graph with at least $(1-\epsilon)2^{2n}$ edges. For any $\epsilon > 0$ and $n$ large enough, is it always possible to find a $2^{(1-f(\epsilon))n}$ by $2^{(1-f(\epsilon))n}$ complete bipartite subgraph, where $\underset{\epsilon\rightarrow0^+}{lim}f(\epsilon)=0$?

  • $\begingroup$ I suspect not. Consider a matching of M 2^n edges. Any complete A-B bipartite subgraph where the sizes of A and B add up to more than 2^n will contain an edge of M. Now as n grows, 2^n will drop below the epsilon fraction, but the f(epsilon) will be forced to remain above 1/2. Gerhard "Ask Me About System Design" Paseman, 2013.04.29 $\endgroup$ – Gerhard Paseman Apr 29 '13 at 21:16
  • $\begingroup$ By the way, if this is homework, you should mention MathOverflow when using the above comment in your answer. Gerhard "Credit Where Credit Is Due" Paseman, 2013.04.29 $\endgroup$ – Gerhard Paseman Apr 29 '13 at 21:19
  • $\begingroup$ Hi Gerhard, thanks for your reply! I did not understand why we should consider the case where A and B add up to more than 2^n. Also could you explain a little more why f(epsilon) will be forced to remain above 1/2? $\endgroup$ – Patrick Apr 29 '13 at 21:58
  • 2
    $\begingroup$ I'm longing for Q2... $\endgroup$ – François G. Dorais Apr 29 '13 at 22:10
  • $\begingroup$ Patrick: take a complete (and balanced) bipartite graph with 2^2n edges, and color 2^n edges red when they are part of a particular matching. Pick a subset A of one side of the vertices. What can you say about a subset B of the other side if B is such that there are no red edges between any member of A and any member of B? Also, I would like to see some motivation for this problem. It would also be good to know what type of class might assign this as a problem. Gerhard "Will Know How To Answer" Paseman, 2013.04.29 $\endgroup$ – Gerhard Paseman Apr 29 '13 at 22:25

No. The correct bound for the largest guaranteed balanced complete bipartite subgraph is $\Theta_{\epsilon}(n)$, where the implied constant depending on $\epsilon$ tends to infinity as $\epsilon \to 0$, so it is only logarithmic in the total number of vertices.

For the upper bound, consider the random bipartite graph with parts of order $2^n$ where each edge appears with probability $1-\epsilon/2$. By Chernoff's inequality, with high probability, this graph will have at least a $1-\epsilon$ fraction of the pairs as edges, and a simple union bound over all possible $K_{t,t}$ with $t=g(\epsilon)n$ for an appropriate choice of $g(\epsilon)$ shows that this also will be $K_{t,t}$-free with high probability. This is essentially the same argument as given by Erdos in his classical lower bound on Ramsey numbers from 1947.

For the lower bound, suppose we are trying to show that there is a $K_{t,t}$. Then count the number of pairs $(v,T)$ consisting of one vertex from the first part and a set $T$ of $t$ vertices from the second part which are all neighbors of $v$. The number of such pairs is $\sum_{v}{\textrm{deg}(v) \choose t}$. One can lower bound this using the number of edges of the graph and Jensen's inequality. On the other hand, if there is no $K_{t,t}$ each $T$ is in at most $t$ pairs and hence the number of such pairs is at most $(t-1){2^n \choose t}$. One gets a contradiction to there being no $K_{t,t}$ if $t$ is too small.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.