PreprintarXiv licencearXiv
EPPA for Reducts of the Random Graph
Abstract
We prove that finite two-graphs have coherent EPPA and that neither graphs modulo global complementation nor two-graphs modulo global complementation have EPPA. This completes the classification of EPPA and coherent EPPA for the reducts of the random graph, answering a question and confirming a conjecture of Evans, Hubička, Konečný and Nešetřil.
Related
- Quadratic differentials and random walks on the dual graph of a pants decomposition
- The number of realisations of a random graph
- The chromatic number of a random graph with o(n3/2) edges
- Paths maximize the expected range of graph-indexed random walks
- Exponential random graph models with soft clique constraints
BibTeX
@misc{brenner2026eppa,
title = {{EPPA for Reducts of the Random Graph}},
author = {Sofia Brenner and Jan Hubička and Matěj Konečný},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39760},
eprint = {2610.39760},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39760},
}
RIS
TY - UNPB
TI - EPPA for Reducts of the Random Graph
AU - Sofia Brenner
AU - Jan Hubička
AU - Matěj Konečný
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39760
UR - https://arxiv.org/abs/2610.39760
AB - We prove that finite two-graphs have coherent EPPA and that neither graphs modulo global complementation nor two-graphs modulo global complementation have EPPA. This completes the classification of EPPA and coherent EPPA for the reducts of the random graph, answering a question and confirming a conjecture of Evans, Hubička, Konečný and Nešetřil.
ER -