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 |
|
|