Skip to main content
improved presentation of TeX; added tag
Source Link
Rune
  • 2.4k
  • 3
  • 23
  • 31

The Erdős–Stone theorem theory says that the densest graph not containing a graph H (which has chromatic number r) has number of edges equal to $(r-2)/(r-1) {n \choose 2}$ asymptotically.

However, this doesn't say much for bipartite graphs (since r=2). I wanted to know what are the best results known for the densest graphs not containing a particular bipartite graph H. I'm guessing this problem is still open and hasn't been completely resolved.

This problem is easy if H is a forest, since every graph with $|E| > k|V|$ contains every forest on k vertices as a subgraph. For even cycles, I know there is a result of Bondy and Simonovits which says:

"if $|E| \geq 100k|V|^{1+1/k}$ then G contains a $C_{2l}$ for every $l$ in $[k, n^{1/k}]$."

So can someone point me to the best known results now for bipartite cyclic graphs?

The Erdős–Stone theorem theory says that the densest graph not containing a graph H (which has chromatic number r) has number of edges equal to $(r-2)/(r-1) {n \choose 2}$ asymptotically.

However, this doesn't say much for bipartite graphs (since r=2). I wanted to know what are the best results known for the densest graphs not containing a particular bipartite graph H. I'm guessing this problem is still open and hasn't been completely resolved.

This problem is easy if H is a forest, since every graph with $|E| > k|V|$ contains every forest on k vertices as a subgraph. For even cycles, I know there is a result of Bondy and Simonovits which says "if $|E| \geq 100k|V|^{1+1/k}$ then G contains a $C_{2l}$ for every $l$ in $[k, n^{1/k}]$."

So can someone point me to the best known results now for bipartite cyclic graphs?

The Erdős–Stone theorem theory says that the densest graph not containing a graph H (which has chromatic number r) has number of edges equal to $(r-2)/(r-1) {n \choose 2}$ asymptotically.

However, this doesn't say much for bipartite graphs (since r=2). I wanted to know what are the best results known for the densest graphs not containing a particular bipartite graph H. I'm guessing this problem is still open and hasn't been completely resolved.

This problem is easy if H is a forest, since every graph with $|E| > k|V|$ contains every forest on k vertices as a subgraph. For even cycles, I know there is a result of Bondy and Simonovits which says:

"if $|E| \geq 100k|V|^{1+1/k}$ then G contains a $C_{2l}$ for every $l$ in $[k, n^{1/k}]$."

So can someone point me to the best known results now for bipartite cyclic graphs?

Source Link
Rune
  • 2.4k
  • 3
  • 23
  • 31

Erdős–Stone theorem type edge density estimates for bipartite graphs?

The Erdős–Stone theorem theory says that the densest graph not containing a graph H (which has chromatic number r) has number of edges equal to $(r-2)/(r-1) {n \choose 2}$ asymptotically.

However, this doesn't say much for bipartite graphs (since r=2). I wanted to know what are the best results known for the densest graphs not containing a particular bipartite graph H. I'm guessing this problem is still open and hasn't been completely resolved.

This problem is easy if H is a forest, since every graph with $|E| > k|V|$ contains every forest on k vertices as a subgraph. For even cycles, I know there is a result of Bondy and Simonovits which says "if $|E| \geq 100k|V|^{1+1/k}$ then G contains a $C_{2l}$ for every $l$ in $[k, n^{1/k}]$."

So can someone point me to the best known results now for bipartite cyclic graphs?