Approximately counting and sampling small witnesses using a colourful decision oracle

Holger Dell, John Lapinskas, Kitty Meeks

In this paper, we design efficient algorithms to approximately count the number of edges of a given $k$-hypergraph, and to sample an approximately uniform random edge. The hypergra…