Looms

Abstract

A pair $(A,B)$ of hypergraphs is called orthogonal if $|a\cap b|=1$ for every pair of edges $a\in A$ and $b\in 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.

20 pages; Minor revisions; Added a coauthor; To appear in Discrete Mathematics