Packing of nonuniform hypergraphs - product and sum of sizes conditions

Paweł Naroski

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 3, page 651-656
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Paweł Naroski. "Packing of nonuniform hypergraphs - product and sum of sizes conditions." Discussiones Mathematicae Graph Theory 29.3 (2009): 651-656. <http://eudml.org/doc/270789>.

@article{PawełNaroski2009,
abstract = {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.},
author = {Paweł Naroski},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {nonuniform hypergraph; packing},
language = {eng},
number = {3},
pages = {651-656},
title = {Packing of nonuniform hypergraphs - product and sum of sizes conditions},
url = {http://eudml.org/doc/270789},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Paweł Naroski
TI - Packing of nonuniform hypergraphs - product and sum of sizes conditions
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 3
SP - 651
EP - 656
AB - 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.
LA - eng
KW - nonuniform hypergraph; packing
UR - http://eudml.org/doc/270789
ER -

References

top
  1. [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. Zbl0375.05046
  2. [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. Zbl0379.05023
  3. [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. Zbl1133.05064
  4. [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. Zbl0938.05046
  5. [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. Zbl0417.05037
  6. [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. Zbl0391.05047
  7. [7] M. Woźniak, Embedding graphs of small size, Discrete Appl. Math. 51 (1994) 233-241, doi: 10.1016/0166-218X(94)90112-0. Zbl0807.05025
  8. [8] M. Woźniak, Packing of graphs, Dissertationes Math. 362 (1997) 1-78. 
  9. [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. Zbl1031.05041
  10. [10] H.P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988) 395-404, doi: 10.1016/0012-365X(88)90232-4. Zbl0685.05036

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.