Graph-intersecting set systems and LYM inequalities

详细信息    查看全文

• 作者：Elizabeth Maltais^a ; ^{emalt012@uottawa.ca} ; Lucia Moura^b ; ^a ; ^{lucia@eecs.uottawa.ca} ; Mike Newman^a ; ^{mnewman@uottawa.ca}
• 关键词：LYM inequality ; Qualitative independence ; Covering array ; Intersecting set system ; Packing ; Graph-intersecting collection
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：340
• 期：3
• 页码：379-398
• 全文大小：615 K
• 卷排序：340

文摘

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