ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let t,k∈Nt,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:N2→Nf:\mathbb{N}^2\to\mathbb{N}.

Thomassen's conjecture. There is a function f:N2→Nf:\mathbb{N}^2\rightarrow\mathbb{N} such that, for all t,k∈Nt,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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.