EPPA numbers of graphs

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/00216208:11320/25:10489750

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

EPPA numbers of graphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

EPPA numbers of graphs

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

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

Název periodika

Journal of Combinatorial Theory. B

ISSN

0095-8956

e-ISSN

1096-0902

Svazek periodika

170

Číslo periodika v rámci svazku

Januar

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

22

Strana od-do

203-224

Kód UT WoS článku

001331597300001

EID výsledku v databázi Scopus

2-s2.0-85205438713