# The representation of multi-hypergraphs by set intersections

Discussiones Mathematicae Graph Theory (2007)

- Volume: 27, Issue: 3, page 565-582
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topStanisław Bylka, and Jan Komar. "The representation of multi-hypergraphs by set intersections." Discussiones Mathematicae Graph Theory 27.3 (2007): 565-582. <http://eudml.org/doc/270430>.

@article{StanisławBylka2007,

abstract = {This paper deals with weighted set systems (V,,q), where V is a set of indices, $ ⊂ 2^V$ 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 = (R_v)_\{v∈ V\}$ of subsets of a set S such that
$|⋂_\{v∈ E\} R_v| = 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.},

author = {Stanisław Bylka, Jan Komar},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {intersection graph; intersection hypergraph},

language = {eng},

number = {3},

pages = {565-582},

title = {The representation of multi-hypergraphs by set intersections},

url = {http://eudml.org/doc/270430},

volume = {27},

year = {2007},

}

TY - JOUR

AU - Stanisław Bylka

AU - Jan Komar

TI - The representation of multi-hypergraphs by set intersections

JO - Discussiones Mathematicae Graph Theory

PY - 2007

VL - 27

IS - 3

SP - 565

EP - 582

AB - This paper deals with weighted set systems (V,,q), where V is a set of indices, $ ⊂ 2^V$ 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 = (R_v)_{v∈ V}$ of subsets of a set S such that
$|⋂_{v∈ E} R_v| = 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.

LA - eng

KW - intersection graph; intersection hypergraph

UR - http://eudml.org/doc/270430

ER -

## References

top- [1] C. Berge, Graphs and Hypergraphs (Amsterdam, 1973).
- [2] J.C. Bermond and J.C. Meyer, Graphe représentatif des aretes d'un multigraphe, J. Math. Pures Appl. 52 (1973) 229-308. Zbl0219.05078
- [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. Zbl0876.05052
- [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. Zbl0137.43202
- [5] F. Harary, Graph Theory (Addison-Wesley, 1969) 265-277.
- [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. Zbl1014.68122
- [7] E.S. Marczewski, Sur deux properties des classes d'ensembles, Fund. Math. 33 (1945) 303-307.
- [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. Zbl0445.05079
- [9] T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory, SIAM Monographs on Discrete Math. and Appl., 2 (SIAM Philadelphia, 1999). Zbl0945.05003
- [10] E. Prisner, Intersection multigraphs of uniform hypergraphs, Graphs and Combinatorics 14 (1998) 363-375. Zbl0910.05048

## NotesEmbed ?

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