[Nauty] prune routine for genbg
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
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