A Hypergraph Version of a Graph Packing Theorem by Bollobás and Eldridge |
| |
| Authors: | Alexandr Kostochka Christopher Stocker Peter Hamburger |
| |
| Institution: | 1. DEPARTMENT OF MATHEMATICS UNIVERSITY OF ILLINOIS, URBANA, IL 61801, SOBOLEV INSTITUTE OF MATHEMATICS, , NOVOSIBIRSK, 630090 RUSSIA;2. DEPARTMENT OF MATHEMATICS UNIVERSITY OF ILLINOIS, , URBANA, IL, 61801;3. DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE, WESTERN KENTUCKY UNIVERSITY, , BOWLING GREEN, KY, 42101‐1078 |
| |
| Abstract: | Two n‐vertex hypergraphs G and H pack, if there is a bijection  such that for every edge  , the set  is not an edge in H. Extending a theorem by Bollobás and Eldridge on graph packing to hypergraphs, we show that if  and n‐vertex hypergraphs G and H with  with no edges of size 0, 1,  and n do not pack, then either - one of G and H contains a spanning graph‐star, and each vertex of the other is contained in a graph edge, or
- one of G and H has
 edges of size  not containing a given vertex, and for every vertex x of the other hypergraph some edge of size  does not contain x. |
| |
| Keywords: | graph packing hypergraph |
|
|
