Finite two-graphs have coherent EPPA while some graph classes do not
EPPA for Reducts of the Random Graph
Discrete Mathematics
Summary
The authors investigated a property called EPPA related to special kinds of graphs. They showed that finite two-graphs have a stronger version called coherent EPPA. However, they found that certain types of graphs, like graphs with global complementation, do not have EPPA. Their results complete a long-standing classification question about the EPPA property for simplified versions of the random graph.
What this means in practice
- •For graph algorithm designers: Avoid building algorithms relying on EPPA properties for graphs modulo global complementation, as this paper shows such EPPA does not exist.
- •For combinatorial model theorists: Use the classification of EPPA and coherent EPPA for reducts of the random graph to guide construction of structures with desired symmetry properties.
A theory result. No direct application yet.
Authors
Sofia Brenner, Jan Hubička, Matěj Konečný
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.