Content deleted Content added
Erel Segal (talk | contribs) |
m v2.05b - Bot T5 CW#2 - Fix errors for CW project (Tag with incorrect syntax) |
||
| (17 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 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.▼
▲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
== Definition by 2-colorability ==
Line 11 ⟶ 17:
== Definition by odd cycles ==
A '''cycle''' (or a '''circuit''') in a hypergraph is a cyclic alternating sequence of distinct vertices and hyperedges: (''v''<sub>1</sub>, ''e''<sub>1</sub>, ''v''<sub>2</sub>, ''e''<sub>2</sub>, ..., ''v<sub>k</sub>'', ''e<sub>k</sub>'', ''v<sub>k</sub>''<sub>+1</sub>=''v''<sub>1</sub>), where every vertex ''v<sub>i</sub>'' is contained in both ''e<sub>i</sub>''<sub>
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|
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|
== Properties ==
Some theorems on bipartite graphs have been generalized to balanced hypergraphs.<ref>{{Cite journal|
* 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
* 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''<sub>1</sub>, ''V''<sub>2</sub>, if <math>|e\cap V_2| \geq |e\cap V_1|</math> for all edges ''e'' in ''E'', then |''V''<sub>2</sub>| ≥ |''V''<sub>1</sub>|. 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>
== Comparison with other notions of bipartiteness ==
Line 30 ⟶ 38:
The properties of bipartiteness and balance do not imply each other.
'''Balance does not imply bipartiteness'''. 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 bipartite, since to have exactly one green vertex in each of the first two hyperedges, we must have two green vertices in the last hyperedge.▼
Bipartiteness does not imply balance. For example, 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 bipartite by the partition ''X''={1}, ''Y''={2,3,4}. But 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.▼
▲'''Bipartiteness does not imply balance'''. For example, 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 bipartite by the partition ''X''={1}, ''Y''={2,3,4}. But 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
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''.▼
▲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''.
▲Balance does not imply bipartiteness. 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 bipartite, since to have exactly one green vertex in each of the first two hyperedges, we must have two green vertices in the last hyperedge.
'''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.
== 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|url=http://www.sciencedirect.com/science/article/pii/0012365X85901566|journal=Discrete Mathematics|language=en|volume=57|issue=1|pages=59–65|doi=10.1016/0012-365X(85)90156-6|issn=0012-365X}}</ref>▼
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''.
Lehel proved that a hypergraph H is totally balanced iff every subhypergraph of H is a tree-hypergraph.<ref name=":2" />▼
== 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
▲
=== 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.
== References ==
{{reflist}}
[[Category:Hypergraphs]]
| |||