[Nauty] prune routine for genbg

Jakub Sliacan jakub.sliacan at gmail.com
Tue Oct 16 01:54:07 AEDT 2018


In extremal combinatorics it's quite desirable to have a fast
implementation of a function that generates all hypergraphs (up to
isomorphism) which avoid a certain set of small hypergraphs. Say, in 3-reg
hypergraphs (3-graphs), one would want all 3-graphs on 8 vertices which
avoid a tetrahedron (K4 = 4 vertices and 4 "edges"). I saw that thanks to
some wonderful options to genbg function one can generate various families
of 3-graphs. Then there's the prune routine which needs to be written by
the user. This is called after every step and keeps only the graphs which
are K4-avoiders.

My concern is that implementing the prune routine would take me a long time
and it would likely be the slowest part of the entire process! Hence: has
anyone already implemented anything along those lines?

Thanks for your time!


More information about the Nauty mailing list