EPPA numbers of graphs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F25%3A00599008" target="_blank" >RIV/67985840:_____/25:00599008 - isvavai.cz</a>

Alternative codes found

RIV/00216208:11320/25:10489750

Result on the web

<a href="https://doi.org/10.1016/j.jctb.2024.09.003" target="_blank" >https://doi.org/10.1016/j.jctb.2024.09.003</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jctb.2024.09.003" target="_blank" >10.1016/j.jctb.2024.09.003</a>

Result language

angličtina

Original language name

EPPA numbers of graphs

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10101 - Pure mathematics

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2025

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Journal of Combinatorial Theory. B

ISSN

0095-8956

e-ISSN

1096-0902

Volume of the periodical

170

Issue of the periodical within the volume

Januar

Country of publishing house

US - UNITED STATES

Number of pages

22

Pages from-to

203-224

UT code for WoS article

001331597300001

EID of the result in the Scopus database

2-s2.0-85205438713