Looms

09/07/2023

∙

by   Ron Aharoni, et al.

∙

0

∙

share

A pair (A,B) of hypergraphs is called orthogonal if |a ∩ b|=1 for every pair of edges a ∈ A and b ∈ B. An orthogonal pair of hypergraphs is called a loom if each of its two members is the set of minimum covers of the other. Looms appear naturally in the context of a conjecture of Gyárfás and Lehel on the covering number of cross-intersecting hypergraphs. We study their properties and ways of construction, and prove special cases of a conjecture that if true would imply the Gyárfás–Lehel conjecture.