Paperlane

no. 5 · Friday 30 October 2026

EPPA for Reducts of the Random Graph

Sofia Brenner, Jan Hubička and Matěj Konečný

math.CO

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.

fields
Combinatorics, Logic
pdf ↗ page arXiv:2610.39760 ↗