Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1016/j.disc.2016.08.027 | Discrete Mathematics |
Keywords | Field | DocType |
LYM inequality,Qualitative independence,Covering array,Intersecting set system,Packing,Graph-intersecting collection | Discrete mathematics,Graph,Complete graph,Combinatorics,Vertex (geometry),Permutation,Digraph,Mathematics,Limiting | Journal |
Volume | Issue | ISSN |
340 | 3 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Elizabeth Maltais | 1 | 2 | 1.39 |
Lucia Moura | 2 | 99 | 17.78 |
Mike Newman | 3 | 38 | 5.81 |