Quadratic EPPA lower bound outside finite homogeneous subgraphs

Let GG be a graph on nn vertices. A finite graph is homogeneous if every isomorphism between finite induced subgraphs extends to an automorphism, and an EPPA-witness of GG is a finite graph extending all partial automorphisms of GG.

Quadratic EPPA conjecture. The graph GG is either a subgraph of a finite homogeneous graph, or every EPPA-witness of GG has at least

Ω(n2)\Omega(n^2)

vertices.

This would improve the general lower bound discussed in the paper from a weaker estimate to a quadratic one. The source gives no resolution.

Sources & referencesView supporting material

Primary source

David Bradley-Williams, Peter J. Cameron, Jan Hubička and Matěj Konečný, “EPPA numbers of graphs”, arXiv:2311.07995 (2024).

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.