Cross-intersecting pairs of hypergraphs

DOI10.1016/J.JCTA.2016.12.002MaRDI QIDQ507820zbMATH OpenOpenAlexFDO

Authors Ron Aharoni, David M. Howard

Publication date 9 February 2017

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.06387

zbMATH Keywords

rainbow matchings\(r\)-partite hypergaphscross-intersecting hypergraphsErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Two hypergraphs $H_1,H_2$ are called {em cross-intersecting} if $e_{1}cap{e}_{2}eqemptyset$ for every pair of edges $e_{1}in{H}_1,e_{2}in{H}_2$. Each of the hypergraphs is then said to {em block} the other. Given parameters $n,r,m$ we determine the maximal size of a sub-hypergraph of $[n{]}^r$ (meaning that it is $r$-partite, with all sides of size $n$) for which there exists a blocking sub-hypergraph of $[n{]}^r$ of size $m$. The answer involves a fractal-like (that is, self-similar) sequence, first studied by Knuth. We also study the same question with $$ replacing $[n{]}^r$.

Recommendations

• The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families
• Sharp results concerning disjoint cross-intersecting families
• A short proof of a cross-intersection theorem of Hilton
• An Erdős-Ko-Rado theorem for cross t-intersecting families
• Partition-crossing hypergraphs

Cites work

• scientific article; zbMATH DE number 3166040 (Why is no real title available?)
• scientific article; zbMATH DE number 4029608 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• A new generalization of the Erdős-Ko-Rado theorem
• An Erdős-Ko-Rado theorem for cross t-intersecting families
• An analogue of the Erdoes-Ko-Rado theorem for the Hamming schemes H(n,q)
• Cross \(t\)-intersecting integer sequences from weighted Erdős-Ko-Rado
• Cross-intersecting families of vectors
• Erdős-Ko-Rado from Kruskal-Katona
• Extremal problems for finite sets and convex hulls---a survey
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On cross \(t\)-intersecting families of sets
• On the size of graphs with complete-factors
• Shadows and shifting
• Shadows of colored complexes.
• The eigenvalue method for cross t-intersecting families
• The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families
• The maximum product of weights of cross-intersecting families

Cited in

(3)

• A rainbow \(r\)-partite version of the Erdős-Ko-Rado theorem
• Partition-crossing hypergraphs
• On Rainbow Matchings for Hypergraphs

This page was built for publication: Cross-intersecting pairs of hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507820)