The representation of multi-hypergraphs by set intersections

Stanisław Bylka; Jan Komar

Discussiones Mathematicae Graph Theory (2007)

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

Abstract

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

How to cite

top

Stanisł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. [1] C. Berge, Graphs and Hypergraphs (Amsterdam, 1973). 
  2. [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. [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. [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. [5] F. Harary, Graph Theory (Addison-Wesley, 1969) 265-277. 
  6. [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. [7] E.S. Marczewski, Sur deux properties des classes d'ensembles, Fund. Math. 33 (1945) 303-307. 
  8. [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. [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. [10] E. Prisner, Intersection multigraphs of uniform hypergraphs, Graphs and Combinatorics 14 (1998) 363-375. Zbl0910.05048

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.