Cilleruelo's lower-bound conjecture for infinite C4C_4-free graphs

Let ϵ>0\epsilon>0. A countable infinite graph with no cycle of length four is called C4C_4-free, and let Gn\mathcal{G}_n denote the subgraph induced by the first nn vertices. Write δ(Gn)\delta(\mathcal{G}_n) for its minimum degree. Cilleruelo's conjecture. For every ϵ>0\epsilon>0, there exists a countable infinite C4C_4-free graph G\mathcal{G} such that

δ(Gn)n1/2ϵ.\delta(\mathcal{G}_n)\gg n^{1/2-\epsilon}.

This conjecture proposes that, despite the obstruction posed by extending finite algebraic constructions to infinite graphs, infinite C4C_4-free graphs can still have minimum degree close to the finite-graph scale n\sqrt n.

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.