Do there exist constants $d>0$, $0<c<1$, $\delta>0$ so that for all large $n$, there exists a graph $H$ satisfying $$e_H\ge dn^2,$$ and then no matter how we remove some edges from $H$ to get an $n$-vertex subgraph $G$, whenever $G$ has minimum degree at least $cn$, there are two disjoint vertex-subsets $A,B$ of $G$ with $|A|,|B|\ge\delta n$ and $$e_G(A,B)=e_H(A,B)\ge \tilde{d}n^2,$$ where $\tilde{d}>0$ may depend on $d$?

In words, for any large $n$, is there a dense $n$-vertex graph $H$ so that for any subgraph $G$ of $H$ with high minimum degree, we can find two large disjoint vertex-subsets of $G$ so that the edges of $G$ between these two sets are same as those of $H$, and they are dense?

I try to start with $H=K_n$. Then we only need to show $K_n$ has a subgraph $G$ so that there are two linear size vertex-subsets, the edges of $G$ between them are same as those of $K_n$.

  • $\begingroup$ This question is very hard to follow as written. This is how I took what you written. So you want to know if there is a dense graph $H$ that satisfies the following: Let $G$ be any subgraph of $H$ with high minimum degree, then there are two disjoint subsets $A$ and $B$ of $VG)$ such that the number of edges between $A$ and $B$ in $G$ is large. Am I correct? $\endgroup$ – Mike Mar 12 '19 at 19:53
  • $\begingroup$ Yes, but also with requirement that the edges between $A$ and $B$ in $G$ are same as those of $H$. $\endgroup$ – Connor Mar 12 '19 at 19:56
  • 2
    $\begingroup$ OK but I didn't get that from the way you worded your question originally. You really ought to consider editting it. $\endgroup$ – Mike Mar 12 '19 at 20:00
  • $\begingroup$ It reflects on $e_G(A,B)=e_H(A,B)$. $\endgroup$ – Connor Mar 13 '19 at 0:02
  • $\begingroup$ If you place each vertex of $G$ in $A$ or $B$ independently at random then $A$ and $B$ are linear in $n$ and the number of edges of $G$ (or $H$) between $A$ and $B$ is at least $cn^2/4$ in expectation. $\endgroup$ – Louis Esperet Mar 13 '19 at 17:26

The answer is no (if I understood your question correctly this time).

Fix $H$ and take $G$ to be a random subgraph of $H$, where you keep each edge with probability $p$, for some constant $p>0$. For fixed sets $A$ and $B$ with at least $\tilde{\delta}n^2$ edges of $H$ between them, the number of edges of $H\setminus G$ between $A$ and $B$ is at least $\tilde{\delta}n^2(1-p)$ in average, and is highly concentrated around its mean (it follows from the Chernoff bound that it is zero with probability at most $\exp(-\Omega(n^2))$). Since there are at most $\exp(O(n))$ such pairs $A,B$, it follows from the union bound that with non-zero probability, for any such sets $A$ and $B$, there is at least one edge of $H\setminus G$ between $A$ and $B$. So you will never have $e_G(A,B)=e_H(A,B)$ in this case.


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.