Balanced hypergraph: Difference between revisions

Revision as of 19:24, 2 July 2020

Revision as of 19:23, 12 July 2020

Line 1:

In [[graph theory]], a '''balanced hypergraph''' is a [[hypergraph]] that has several properties analogous to that of a [[bipartite graph]].

Balanced hypergraphs were introduced by [[Claude Berge|Berge]]<ref name=":0">{{Cite journal|last=Berge|first=Claude|date=1970|title=Sur certains hypergraphes généralisant les graphes bipartites|url=|journal=Combinatorial Theory and its Applications|volume=1|pages=119-133119–133|via=}}</ref> as a natural generalization of bipartite graphs. He provided two equivalent definitions.

== Definition by 2-colorability ==

Line 11:

== Definition by odd cycles ==

A '''cycle''' (or a '''circuit''') in a hypergraph is a cyclic alternating sequence of distinct vertices and hyperedges: (''v''₁, ''e''₁, ''v''₂, ''e''₂, ..., ''v_k'', ''e_k'', ''v_k''₊₁=''v''₁), where every vertex ''v_i'' is contained in both ''e_i''_-1−1 and ''e_i''. The number ''k'' is called the ''length'' of the cycle.

A hypergraph is '''balanced''' iff every odd-length cycle ''C'' in ''H'' has an edge containing at least three vertices of ''C''.<ref name=":1">{{Cite journal|last=Conforti|first=Michele|last2=Cornuéjols|first2=Gérard|last3=Kapoor|first3=Ajai|last4=Vušković|first4=Kristina|date=1996-09-01|title=Perfect matchings in balanced hypergraphs|url=https://doi.org/10.1007/BF01261318|journal=Combinatorica|language=en|volume=16|issue=3|pages=325–329|doi=10.1007/BF01261318|issn=1439-6912}}</ref>

Line 17:

Note that in a simple graph all edges contain only two vertices. Hence, a simple graph is balanced iff it contains no odd-length cycles at all, which holds iff it is bipartite.

[[Claude Berge|Berge]]<ref name=":0" /> proved that the two definitions are equivalent; a proof is also available here.<ref name="lp" />{{rp|468-469468–469}}

== Properties ==