Half graph

In graph theory, a branch of mathematics, a half graph is a special type of bipartite graph. These graphs are called the half graphs because they have approximately half of the edges of a complete bipartite graph on the same vertices. The name was given to these graphs by Paul Erdős and András Hajnal.[1]

A 14-vertex half graph

Definition

To define the half graph on ${\displaystyle 2n}$ vertices ${\displaystyle u_{1},\dots u_{n}}$ and ${\displaystyle v_{1},\dots v_{n}}$, connect ${\displaystyle u_{i}}$ to ${\displaystyle v_{j}}$ by an edge whenever ${\displaystyle i\leq j}$.[1]

The same concept can also be defined in the same way for infinite graphs over two copies of any ordered set of vertices.[1] The half graph over the natural numbers (with their usual ordering) has the property that each vertex ${\displaystyle v_{j}}$ has finite degree, at most ${\displaystyle j}$. The vertices on the other side of the bipartition have infinite degree.[2]

Irregularity

One application for the half graph occurs in the Szemerédi regularity lemma, which states that the vertices of any graph can be partitioned into a constant number of subsets of equal size, such that most pairs of subsets are regular (the edges connecting the pair behave in certain ways like a random graph of some particular density). If the half graph is partitioned in this way into ${\displaystyle k}$ subsets, the number of irregular pairs will be at least proportional to ${\displaystyle k}$. Therefore, it is not possible to strengthen the regularity lemma to show the existence of a partition for which all pairs are regular.[3]

Matching

The half graph has a unique perfect matching. This is straightforward to see by induction: ${\displaystyle u_{n}}$ must be matched to its only neighbor, ${\displaystyle v_{n}}$, and the remaining vertices form another half graph. More strongly, every bipartite graph with a unique perfect matching is a subgraph of a half graph.[4]

In graphs of uncountable chromatic number

If the chromatic number of a graph is uncountable, then the graph necessarily contains as a subgraph a half graph on the natural numbers. This half graph, in turn, contains every complete bipartite graph in which one side of the bipartition is finite and the other side is countably infinite.[5]

References

1. Erdős, Paul (1984), "Some combinatorial, geometric and set theoretic problems in measure theory", in Kölzow, D.; Maharam-Stone, D. (eds.), Measure Theory Oberwolfach 1983, Lecture Notes in Mathematics, 1089, Springer
2. Nešetřil, Jaroslav; Shelah, Saharon (2003), "On the order of countable graphs", European Journal of Combinatorics, 24 (6): 649–663, arXiv:math/0404319, doi:10.1016/S0195-6698(03)00064-7, MR 1995579
3. Conlon, David; Fox, Jacob (2012), "Bounds for graph regularity and removal lemmas", Geometric and Functional Analysis, 22 (5): 1191–1256, arXiv:1107.4829, doi:10.1007/s00039-012-0171-x, MR 2989432
4. Godsil, C. D. (1985), "Inverses of trees", Combinatorica, 5 (1): 33–39, doi:10.1007/bf02579440. See in particular Lemma 2.1.
5. Erdős, Paul; Hajnal, András (1985), "Chromatic number of finite and infinite graphs and hypergraphs" (PDF), Discrete Mathematics, 53: 281–285, doi:10.1016/0012-365X(85)90148-7, MR 0786496. The result that graphs of uncountable chromatic number contain an infinite half graph is credited in this paper to Hajnal and cited to a 1973 paper of the same authors with Shelah, but that paper states the result only in the weaker form that graphs of uncountable chromatic number contain complete bipartite graphs where one side is any finite number and the other side is infinite.