Balanced hypergraph: Difference between revisions

Revision as of 20:23, 1 July 2020

Latest revision as of 01:06, 19 February 2025

(23 intermediate revisions by 8 users not shown)

Line 1:

[[File:Balanced hypergraph, first definition.svg|thumb|300px|The initial graph is '''2-colorable''', as the vertices can be colored such that each edge has one of each color.

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

<br /><br />

Any number of any vertices (here, 1 vertex, vertex "v2") can be deleted from the initial graph, as shown in the next graph. After re-coloring the vertices, it is shown the graph is still 2-colorable.

<br /><br />

Any ''singletons'', or edges with only 1 vertex, are disregarded, as these obviously cannot be 2-colored.]]

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

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 itsIts Applications|volume=1|pages=119-133|via=119–133}}</ref> as a natural generalization of bipartite graphs. He provided two equivalent definitions.

== Definition by 2-colorability ==

Line 11 ⟶ 17:

== 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''₁), where every vertex ''v_i'' is contained in both ''e_i''₋₁ 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|last1=Conforti|first1=Michele|last2=Cornuéjols|first2=Gérard|last3=Kapoor|first3=Ajai|last4=Vušković|first4=Kristina|author4-link= Kristina Vušković |date=1996-09-01|title=Perfect matchings in balanced hypergraphs|journal=Combinatorica|language=en|volume=16|issue=3|pages=325–329|doi=10.1007/BF01261318|s2cid=206792822|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 simple graph is balanced iff it contains no odd-length cycles at all, which holds iff it is bipartite.

== Other notions of bipartiteness ==

The see that this sense is stonger than 2-colorability, let ''H'' be the hypergraph with vertices {1,2,3,4} and edges:<blockquote>{ {1,2,3} , {1,2,4} , {1,3,4} }</blockquote>It is 2-colorable (it is even exactly-2-colorable), but it is not balanced. For example, if vertex 1 is removed, we get the restriction of ''H'' to {2,3,4}, which has the following hyperedges;<blockquote>{ {2,3} , {2,4} , {3,4} }</blockquote>It is not 2-colorable, since in any 2-coloring there are at least two vertices with the same color, and thus at least one of the hyperedges is monochromatic.

[[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}}

The above example shows that exact 2-colorability does not imply balancedness; to see that balancedness does not imply exact-2-colorability either, let ''H'' be the hypergraph:<ref>{{Cite web|title=coloring - Which generalization of bipartite graphs is stronger?|url=https://math.stackexchange.com/questions/3728221/which-generalization-of-bipartite-graphs-is-stronger|access-date=2020-06-27|website=Mathematics Stack Exchange}}</ref><blockquote>{ {1,2} , {3,4} , {1,2,3,4} }</blockquote>it is 2-colorable and remains 2-colorable upon removing any number of vertices from it. However, It is not exactly 2-colorable, since to have exactly one green vertex in each of the first two hyperedges, we must have two green vertices in the last hyperedge.

== Properties ==

Some theorems on bipartite graphs have been generalized to balanced hypergraphs.<ref>{{Cite journal|lastlast1=Berge|firstfirst1=Claude|last2=Vergnas|first2=Michel LAS|date=1970|title=Sur Un Theorems Du Type König Pour Hypergraphes|url=https://nyaspubs.onlinelibrary.wiley.com/doi/abs/10.1111/j.1749-6632.1970.tb56451.x|journal=Annals of the New York Academy of Sciences|language=en|volume=175|issue=1|pages=32–40|doi=10.1111/j.1749-6632.1970.tb56451.x|s2cid=84670737 |issn=1749-6632}}</ref><ref name="lp2lp">{{Cite Lovasz Plummer}}</ref>{{Rp|468–470}}

* A hypergraph is 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).

* In every balanced hypergraph, the minimum [[Vertex cover in hypergraphs|vertex-cover]] has the same size as its maximum [[Matching in hypergraphs|matching]]. This generalizes the [[Kőnig's theorem (graph theory)|Kőnig-Egervary theorem]] on bipartite graphs.

* In every balanced hypergraph, the [[Degree (graph theory)|degree]] (= the maximum number of hyperedges containing some one vertex) equals the [[Edge coloring|chromatic index]] (= the least number of colors required for coloring the hyperedges such that no two hyperedges with the same color have a vertex in common).<ref>{{Cite journal|last=Lovász|first=L.|date=1972-06-01|title=Normal hypergraphs and the perfect graph conjecture|url=http://www.sciencedirect.com/science/article/pii/0012365X72900064|journal=Discrete Mathematics|language=en|volume=2|issue=3|pages=253–267|doi=10.1016/0012-365X(72)90006-4|issn=0012-365X|doi-access=}}</ref> This generalizes a theorem of Konig on bipartite graphs.

* Every balanced hypergraph satisfies a generalization of [[Hall's marriage theorem]]:<ref name=":1" /> it admits a perfect matching iff for all disjoint vertex-sets ''V''₁, ''V''₂, if <math>|e\cap V_2| \geq |e\cap V_1|</math> for all edges ''e'' in ''E'', then |''V''₂| ≥ |''V''₁|. See [[Hall-type theorems for hypergraphs]].

* Every balanced hypergraph with maximum degree ''D'', can be partitioned into ''D'' edge-disjoint matchings.<ref name=":0" />{{Rp|Chapter 5}}<ref name=":1" />{{Rp|Corollary 3}}

A ''k''-fold transversal of a balanced hypergraph can be expressed as a union of ''k'' pairwise-disjoint transversals, and such partition can be obtained in polynomial time.<ref>{{Cite journal|last1=Dahlhaus|first1=Elias|last2=Kratochvíl|first2=Jan|last3=Manuel|first3=Paul D.|last4=Miller|first4=Mirka|date=1997-11-27|title=Transversal partitioning in balanced hypergraphs|journal=Discrete Applied Mathematics|language=en|volume=79|issue=1|pages=75–89|doi=10.1016/S0166-218X(97)00034-6|issn=0166-218X|doi-access=}}</ref>

== OtherComparison with other notions of bipartiteness ==

Besides balance, there are alternative generalizations of bipartite graphs. A hypergraph is called '''bipartite''' if its vertex set ''V'' can be partitioned into two sets, ''X'' and ''Y'', such that each hyperedge contains '''''exactly one''''' element of ''X'' (see [[bipartite hypergraph]]). Obviously every bipartite graph is 2-colorable.

The properties of bipartiteness and balance do not imply each other.

The above example shows that exact 2-colorability'''Balance does not imply balancedness; to see that balancedness does not imply exact-2-colorability either,bipartiteness'''. letLet ''H'' be the hypergraph:<ref>{{Cite web|title=coloring - Which generalization of bipartite graphs is stronger?|url=https://math.stackexchange.com/questions/3728221/which-generalization-of-bipartite-graphs-is-stronger|access-date=2020-06-27|website=Mathematics Stack Exchange}}</ref><blockquote>{ {1,2} , {3,4} , {1,2,3,4} }</blockquote>it is 2-colorable and remains 2-colorable upon removing any number of vertices from it. However, It is not exactly 2-colorablebipartite, since to have exactly one green vertex in each of the first two hyperedges, we must have two green vertices in the last hyperedge.

The'''Bipartiteness seedoes thatnot thisimply sensebalance'''. isFor stonger than 2-colorabilityexample, let ''H'' be the hypergraph with vertices {1,2,3,4} and edges:<blockquote>{ {1,2,3} , {1,2,4} , {1,3,4} }</blockquote>It is 2-colorablebipartite (itby isthe evenpartition exactly-2-colorable)''X''={1}, but''Y''={2,3,4}. itBut is not balanced. For example, if vertex 1 is removed, we get the restriction of ''H'' to {2,3,4}, which has the following hyperedges;:<blockquote>{ {2,3} , {2,4} , {3,4} }</blockquote>It is not 2-colorable, since in any 2-coloring there are at least two vertices with the same color, and thus at least one of the hyperedges is monochromatic.

Another way to see that ''H'' is not balanced is that it contains the odd-length cycle ''C'' = (2 - {1,2,3} - 3 - {1,3,4} - 4 - {1,2,4} - 2), and no edge of ''C'' contains all three vertices 2,3,4 of ''C''.

'''Tripartiteness does not imply balance'''. For example, let ''H'' be the tripartite hypergraph with vertices {1,2},{3,4},{5,6} and edges:<blockquote>{ {1,3,5}, {2,4,5}, {1,4,6} }</blockquote>It is not balanced since if we remove the vertices 2,3,6, the remainder is:<blockquote>{ {1,5}, {4,5}, {1,4} }</blockquote>which is not colorable since it is a 3-cycle.

Another way to see that it is not balanced is that It contains the odd-length cycle ''C'' = (1 - {1,3,5} - 5 - {2,4,5} - 4 - {1,4,6} - 1), and no edge of ''C'' contains all three vertices 1,4,5 of ''C''.

== Related properties ==

=== Totally balanced hypergraphs ===

A hypergraph is called '''totally balanced''' if every cycle ''C'' in ''H'' of length at least 3 (not necessarily odd-length) has an edge containing at least three vertices of ''C''.<ref name=":2">{{Cite journal|last=Lehel|first=Jenö|date=1985-11-01|title=A characterization of totally balanced hypergraphs|journal=Discrete Mathematics|language=en|volume=57|issue=1|pages=59–65|doi=10.1016/0012-365X(85)90156-6|issn=0012-365X|doi-access=free}}</ref>

A hypergraph H is totally balanced iff every subhypergraph of H is a tree-hypergraph.<ref name=":2" />

=== Normal hypergraphs ===

The '''Konig property''' of a hypergraph H is the property that its minimum [[Vertex cover in hypergraphs|vertex-cover]] has the same size as its maximum [[Matching in hypergraphs|matching]]. The [[Kőnig's theorem (graph theory)|Kőnig-Egervary theorem]] says that all bipartite graphs have the Konig property.

The balanced hypergraphs are exactly the hypergraphs H such that every ''partial subhypergraph'' of ''H'' has the Konig property (i.e., H has the Konig property even upon deleting any number of hyperedges and vertices).

If every ''partial'' hypergraph of H has the Konig property (i.e., H has the Konig property even upon deleting any number of hyperedges - but not vertices), then H is called a '''normal hypergraph'''.<ref name=":02">{{Cite journal|last1=Beckenbach|first1=Isabel|last2=Borndörfer|first2=Ralf|date=2018-10-01|title=Hall's and Kőnig's theorem in graphs and hypergraphs|journal=Discrete Mathematics|language=en|volume=341|issue=10|pages=2753–2761|doi=10.1016/j.disc.2018.06.013|s2cid=52067804 |issn=0012-365X|doi-access=}}</ref>

Thus, totally-balanced implies balanced, which implies normal.

== See also ==

== References ==

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

{{reflist}}

[[Category:Hypergraphs]]