Packing of nonuniform hypergraphs - product and sum of sizes conditions

• Autorzy: Paweł Naroski
• Języki publikacji: EN

Abstrakty

EN

Hypergraphs $H₁,...,H_N$ of order n are mutually packable if one can find their edge disjoint copies in the complete hypergraph of order n. We prove that two hypergraphs are mutually packable if the product of their sizes satisfies some upper bound. Moreover we show that an arbitrary set of the hypergraphs is mutually packable if the sum of their sizes is sufficiently small.

Słowa kluczowe

EN

nonuniform hypergraph; packing

Kategorie tematyczne

• 05C70: Factorization, matching, partitioning, covering and packing
• 05D05: Extremal set theory
• 05C65: Hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2009
• Tom: 29
• Numer: 3
• Strony: 651-656

Daty

wydano

2009

otrzymano

2008-05-07

poprawiono

2008-08-12

zaakceptowano

2008-09-30

Twórcy

autor

Paweł Naroski

• Faculty of Mathematics and Information Science, Warsaw University of Technology, Pl. Politechniki 1, 00-661 Warsaw, Poland

Bibliografia

• [1] D. Burns and S. Schuster, Every (p,p-2) graph is contained in its complement, J. Graph Theory 1 (1977) 277-279, doi: 10.1002/jgt.3190010308.
• [2] D. Burns and S. Schuster, Embeddings (p,p-1) graphs in their complements, Israel J. Math. 4, 30 (1978) 313-320, doi: 10.1007/BF02761996.
• [3] M. Pilśniak and M. Woźniak, A note on packing of two copies of a hypergraph, Discuss. Math. Graph Theory 27 (2007) 45-49, doi: 10.7151/dmgt.1343.
• [4] V. Rödl, A. Ruciński and A. Taraz, Hypergraph packing and graph embedding, Combinatorics, Probability and Computing 8 (1999) 363-376, doi: 10.1017/S0963548399003879.
• [5] N. Sauer and J. Spencer, Edge disjoint placements of graphs, J. Combin. Theory (B) 25 (1978) 295-302, doi: 10.1016/0095-8956(78)90005-9.
• [6] S. Schuster, Fixed-point-free embeddings of graphs in their complements, Internat. J. Math. & Math. Sci. 1 (1978) 335-338, doi: 10.1155/S0161171278000356.
• [7] M. Woźniak, Embedding graphs of small size, Discrete Appl. Math. 51 (1994) 233-241, doi: 10.1016/0166-218X(94)90112-0.
• [8] M. Woźniak, Packing of graphs, Dissertationes Math. 362 (1997) 1-78.
• [9] M. Woźniak, Packing of graphs and permutations - a survey, Discrete Math. 276 (2004) 379-391, doi: 10.1016/S0012-365X(03)00296-6.
• [10] H.P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988) 395-404, doi: 10.1016/0012-365X(88)90232-4.

Identyfikatory

DOI

10.7151/dmgt.1471