Skip to main content
MathOverflow

Return to Question

added 289 characters in body
Source Link
Connor
Connor
  • 281
  • 1
  • 7

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

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

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

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

added 8 characters in body
Source Link
Connor
Connor
  • 281
  • 1
  • 7

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$,$$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 $$e_G(A,B)=e_H(A,B)\ge \tilde{d}n^2,$$ where $\tilde{d}>0$ may depend on $d$?

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

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

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

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

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

Source Link
Connor
Connor
  • 281
  • 1
  • 7

Find large "induced" bipartite graph in a dense graph?

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

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