Quadratic EPPA lower bound outside finite homogeneous subgraphs
Quadratic EPPA lower bound outside finite homogeneous subgraphs
Let be a graph on vertices. A finite graph is homogeneous if every isomorphism between finite induced subgraphs extends to an automorphism, and an EPPA-witness of is a finite graph extending all partial automorphisms of .
Quadratic EPPA conjecture. The graph is either a subgraph of a finite homogeneous graph, or every EPPA-witness of has at least
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.