TY - JOUR

T1 - EPPA numbers of graphs

AU - Bradley-Williams, David

AU - Cameron, Peter J.

AU - Hubička, Jan

AU - Konečný, Matěj

N1 - Publisher Copyright:
© 2024 The Authors

PY - 2025/1

Y1 - 2025/1

N2 - If G is a graph, A and B its induced subgraphs, and f:A→B an isomorphism, we say that f is a partial automorphism of G. In 1992, Hrushovski proved that graphs have the extension property for partial automorphisms (EPPA, also called the Hrushovski property), that is, for every finite graph G there is a finite graph H, an EPPA-witness for G, such that G is an induced subgraph of H and every partial automorphism of G extends to an automorphism of H. The EPPA number of a graph G, denoted by eppa(G), is the smallest number of vertices of an EPPA-witness for G, and we put eppa(n)=max{eppa(G):|G|=n}. In this note we review the state of the area, prove several lower bounds (in particular, we show that eppa(n)≥[Formula presented], thereby identifying the correct base of the exponential) and pose many open questions. We also briefly discuss EPPA numbers of hypergraphs, directed graphs, and Kk-free graphs.

AB - If G is a graph, A and B its induced subgraphs, and f:A→B an isomorphism, we say that f is a partial automorphism of G. In 1992, Hrushovski proved that graphs have the extension property for partial automorphisms (EPPA, also called the Hrushovski property), that is, for every finite graph G there is a finite graph H, an EPPA-witness for G, such that G is an induced subgraph of H and every partial automorphism of G extends to an automorphism of H. The EPPA number of a graph G, denoted by eppa(G), is the smallest number of vertices of an EPPA-witness for G, and we put eppa(n)=max{eppa(G):|G|=n}. In this note we review the state of the area, prove several lower bounds (in particular, we show that eppa(n)≥[Formula presented], thereby identifying the correct base of the exponential) and pose many open questions. We also briefly discuss EPPA numbers of hypergraphs, directed graphs, and Kk-free graphs.

KW - EPPA

KW - Graphs

KW - Hrushovski property

KW - Partial automorphisms

KW - Permutation groups

KW - Random graphs

UR - http://www.scopus.com/inward/record.url?scp=85205438713&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2024.09.003

DO - 10.1016/j.jctb.2024.09.003

M3 - Article

AN - SCOPUS:85205438713

SN - 0095-8956

VL - 170

SP - 203

EP - 224

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -