Balanced hypergraph: Difference between revisions

Revision as of 20:23, 1 July 2020

Revision as of 20:29, 1 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-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 ana cyclic alternating sequence of distinct vertices and hyperedges: (''v''₁, ''e''₁, ''v''₂, ''e''₂, ..., ''v_k'', ''e_k'', ''v_k''₊₁=''v''₁). The number ''k'' is 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>{{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>

A hypergraph is called '''balanced''' iff it does not contain an unbalanced odd-length circuit just like a simple graph is bipartite iff it does not contain an odd-length cycle).

Note that in a simple graph all edges contain only two vertices. Hence, a graph is balanced iff it contains no odd 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-469}}

== Other notions of bipartiteness ==

Line 30 ⟶ 34:

* [[Bipartite hypergraph]] - an alternative generalization of a [[bipartite graph]].

== References ==

[[Category:Hypergraphs]]