The representation of multi-hypergraphs by set intersections
Stanisław Bylka ; Jan Komar
Discussiones Mathematicae Graph Theory, Tome 27 (2007), p. 565-582 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

This paper deals with weighted set systems (V,,q), where V is a set of indices, ⊂2V and the weight q is a nonnegative integer function on . The basic idea of the paper is to apply weighted set systems to formulate restrictions on intersections. It is of interest to know whether a weighted set system can be represented by set intersections. An intersection representation of (V,,q) is defined to be an indexed family R=(Rv)v∈V of subsets of a set S such that |⋂v∈ERv|=q(E) for each E ∈ . A necessary condition for the existence of such representation is the monotonicity of q on i.e., if F ⊂ then q(F) ≥ q(). Some sufficient conditions for weighted set systems representable by set intersections are given. Appropriate existence theorems are proved by construction of the solutions. The notion of intersection multigraphs to intersection multi- hypergraphs - hypergraphs with multiple edges, is generalized. Some conditions for intersection multi-hypergraphs are formulated.

Publié le : 2007-01-01
EUDML-ID : urn:eudml:doc:270430 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1383,
     author = {Stanis\l aw Bylka and Jan Komar},
     title = {The representation of multi-hypergraphs by set intersections},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {27},
     year = {2007},
     pages = {565-582},
     zbl = {1142.05057},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1383}
}

Stanisław Bylka; Jan Komar. The representation of multi-hypergraphs by set intersections. Discussiones Mathematicae Graph Theory, Tome 27 (2007) pp. 565-582. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1383/

[000] [1] C. Berge, Graphs and Hypergraphs (Amsterdam, 1973).

[001] [2] J.C. Bermond and J.C. Meyer, Graphe représentatif des aretes d'un multigraphe, J. Math. Pures Appl. 52 (1973) 229-308. | Zbl 0219.05078

[002] [3] S. Bylka and J. Komar, Intersection properties of line graphs, Discrete Math. 164 (1997) 33-45, doi: 10.1016/S0012-365X(96)00041-6. | Zbl 0876.05052

[003] [4] P. Erdös, A. Goodman and L. Posa, The representation of graphs by set intersections, Canadian J. Math. 18 (1966) 106-112, doi: 10.4153/CJM-1966-014-3. | Zbl 0137.43202

[004] [5] F. Harary, Graph Theory (Addison-Wesley, 1969) 265-277.

[005] [6] V. Grolmusz, Constructing set systems with prescribed intersection size, Journal of Algorithms 44 (2002) 321-337, doi: 10.1016/S0196-6774(02)00204-3. | Zbl 1014.68122

[006] [7] E.S. Marczewski, Sur deux properties des classes d'ensembles, Fund. Math. 33 (1945) 303-307.

[007] [8] A. Marczyk, Properties of line multigraphs of hypergraphs, Ars Combinatoria 32 (1991) 269-278. Colloquia Mathematica Societatis Janos Bolyai, 18. Combinatorics, Keszthely (Hungary, 1976) 1185-1189. | Zbl 0445.05079

[008] [9] T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory, SIAM Monographs on Discrete Math. and Appl., 2 (SIAM Philadelphia, 1999). | Zbl 0945.05003

[009] [10] E. Prisner, Intersection multigraphs of uniform hypergraphs, Graphs and Combinatorics 14 (1998) 363-375. | Zbl 0910.05048