Papers for

combinatorial model theorists

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Finite two-graphs have coherent EPPA while some graph classes do not

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.

Thu 29 OctDiscrete Mathematics

The gist

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.

Open → 2610.39760v1