EPPA numbers of graphs

David Bradley-Williams; Peter J. Cameron; Jan Hubička; Matěj Konečný

doi:10.1016/j.jctb.2024.09.003

EPPA numbers of graphs

David Bradley-Williams^*, Peter J. Cameron^*, Jan Hubička^*, Matěj Konečný^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

Abstract

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) ≥ 2ⁿ/sqrt(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 K_k-free graphs.

Original language	English
Pages (from-to)	203-224
Number of pages	22
Journal	Journal of Combinatorial Theory, Series B
Volume	170
Early online date	3 Oct 2024
DOIs	https://doi.org/10.1016/j.jctb.2024.09.003
Publication status	Published - 1 Jan 2025

Keywords

EPPA
Hrushovski property
Graphs
Random Graphs
Partial automorphisms
Permutation groups

Access to Document

10.1016/j.jctb.2024.09.003Licence: CC BY

Bradley-Williams_2024_JoCTB_EPPA-numbers-of-graphs_CC
© 2024 The Authors. This is an open access article under the CC BY license (https://creativecommons.org/licenses/by/4.0/).
Final published version, 523 KBLicence: CC BY

Cite this

@article{2ac54bdeaed04d4eb3d00d8d2fefd6fc,

title = "EPPA numbers of graphs",

abstract = "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) ≥ 2n/sqrt(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.",

keywords = "EPPA, Hrushovski property, Graphs, Random Graphs, Partial automorphisms, Permutation groups",

author = "David Bradley-Williams and Cameron, {Peter J.} and Jan Hubi{\v c}ka and Mat{\v e}j Kone{\v c}n{\'y}",

note = "Funding: D.B-W. supported by the project EXPRO 20-31529X of the Czech Science Foundation (GA{\v C}R) and by the Czech Academy of Sciences CAS (RVO 67985840). J.H. Supported by the project 21-10775S of the Czech Science Foundation (GA{\v C}R) in the earlier stages of this project, and by a project that has received funding from the European Research Council under the European Union's Horizon 2020 research and innovation programme (grant agreement No 810115) in the later stages. M.K. supported by the European Research Council (Project POCOCOP, ERC Synergy Grant 101071674).",

year = "2025",

month = jan,

day = "1",

doi = "10.1016/j.jctb.2024.09.003",

language = "English",

volume = "170",

pages = "203--224",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press/Elsevier ",

}

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 - Funding: D.B-W. supported by the project EXPRO 20-31529X of the Czech Science Foundation (GAČR) and by the Czech Academy of Sciences CAS (RVO 67985840). J.H. Supported by the project 21-10775S of the Czech Science Foundation (GAČR) in the earlier stages of this project, and by a project that has received funding from the European Research Council under the European Union's Horizon 2020 research and innovation programme (grant agreement No 810115) in the later stages. M.K. supported by the European Research Council (Project POCOCOP, ERC Synergy Grant 101071674).

PY - 2025/1/1

Y1 - 2025/1/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) ≥ 2n/sqrt(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.

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) ≥ 2n/sqrt(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.

KW - EPPA

KW - Hrushovski property

KW - Graphs

KW - Random Graphs

KW - Partial automorphisms

KW - Permutation groups

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 -

EPPA numbers of graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this