2023/11/14 by David Bradley-Williams, Bradley-Williams, David, Peter J. Cameron +5
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2311.07995
openalex publication_date 2023/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
If G is a graph, A and B its induced subgraphs, and f\colon 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 \mathopeppa\nolimits(G), is the smallest number of vertices of an EPPA-witness for G, and we put \mathopeppa\nolimits(n) = max\\mathopeppa\nolimits(G) : | G| = n\. In this note we review the state of the area, prove several lower bounds (in particular, we show that \mathopeppa\nolimits(n)≥ (2n)/(√(n)), 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.