Graph-intersecting set systems and LYM inequalities

For a graph H, an H-intersecting collection is a collection of packings on a ground set [n] with V(H) parts where, for every edge ab of H, every two distinct packings in the collection, P1 and P2, satisfy P1a∩P2b≠Ø. We give a general method for producing LYM-like inequalities for H-intersecting collections, for any graph H. Our technique involves counting permutations having a certain “following” pattern of sets from the collection. For every graph H, we provide the optimal set of permutations to count, encoded by the arcs of a “follow digraph” F. We fully characterize the relationship between graphs H and follow digraphs F. Our inequalities inherently bound the maximum number of packings in H-intersecting collections, and for specific graphs H, we use them to derive bounds. If H is the star on 3 vertices, then an H-intersecting collection has size at most 12a+ba=O(φn∕n), where φ=12(1+5), a≈φb, and a+2b=n. If H is Kv with a loop on each vertex, with v≥3, then an H-intersecting collection has size at most 14⌊2n∕v⌋⌊n∕v⌋, for all n≥22v∕3, improving a bound given by Poljak and Tuza by a factor of 2. Assuming that optimal H-intersecting collections have a limiting behaviour, we derive a simplified form for our inequalities. When H is a complete graph Kv with a loop on each vertex, then, under these assumptions, we prove that an H-intersecting collection has size at most 1v2−v2n∕v+2n∕v+1(1+o(1)), which improves our bound for large enough n and v.