Esperet–Kang–Thomassé conjecture on dense induced bipartite subgraphs

About 8 years old · traced to

Let dd be a positive real number, and let GG be a triangle-free graph with minimum degree at least dd. An induced bipartite subgraph of GG is a bipartite subgraph induced by a subset of the vertices of GG, and its average degree is the average of its vertex degrees. Esperet–Kang–Thomassé conjecture. The graph GG contains an induced bipartite subgraph with average degree

Ω(ln⁡d).\Omega(\ln d).

This conjecture strengthens the known bound of order ln⁡d/ln⁡ln⁡d\ln d/\ln\ln d proved for every triangle-free graph of minimum degree dd. It asks whether the logarithmic factor can be achieved without the additional ln⁡ln⁡d\ln\ln d loss.

References

Primary source

Stefan Glock, “A note on dense bipartite induced subgraphs”, arXiv:2006.05101 (2020).

Additional references

4 papers in this index state this conjecture (2018–2020). The statement above is taken from the most recent of them; the others are arXiv:1811.11116, arXiv:1810.12144, arXiv:1808.02512.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.