Cilleruelo's minimum-degree conjecture for infinite C4C_4-free graphs

Let G\mathcal{G} be a countable infinite graph with no cycle of length four, and let Gn\mathcal{G}_n be the subgraph induced by its first nn vertices. Write δ(Gn)\delta(\mathcal{G}_n) for its minimum degree. Cilleruelo's conjecture.

lim infnδ(Gn)n=0.\liminf_{n\to\infty}\frac{\delta(\mathcal{G}_n)}{\sqrt n}=0.

Finite C4C_4-free graphs can have minimum degree asymptotic to n\sqrt n, but the author explains that algebraic constructions are too rigid to extend to infinite graphs. The conjecture asserts that every countable infinite C4C_4-free graph must have substantially smaller minimum degree along an infinite subsequence.

Sources & referencesView supporting material

Primary source

Javier Cilleruelo, “Infinite graphs that do not contain cycles of length four”, arXiv:1401.4502 (2016).

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.