Thomassen's conjecture on dense bipartite subgraphs of large girth

Let t,kNt,k\in\mathbb{N}. A bipartite graph has average degree at least f(t,k)f(t,k) if its average degree is at least the value of a function f:N2Nf:\mathbb{N}^2\to\mathbb{N}.

Thomassen's conjecture. There is a function f:N2Nf:\mathbb{N}^2\rightarrow\mathbb{N} such that, for all t,kNt,k\in\mathbb{N}, every bipartite graph of average degree at least f(t,k)f(t,k) has a subgraph of average degree at least tt and girth at least kk.

This is a conjecture about finding arbitrarily dense subgraphs of arbitrarily large prescribed girth in bipartite graphs. The paper notes that the case of girth 66 is currently the best known.

Sources & referencesView supporting material

Primary source

Rose McCarty, “Dense induced subgraphs of dense bipartite graphs”, arXiv:2004.00035 (2020).

Additional references

3 papers in this index state this conjecture (2013–2020). The statement above is taken from the most recent of them; the others are arXiv:1403.1995, arXiv:1303.4982.

Source: https://arxiv.org/abs/2004.00035 Thomassen (1983), source attribution in the paper

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.