Half graph

In a half graph, every two vertices are at distance one, two, or three. Any two vertices ${\displaystyle u_{i}}$ and ${\displaystyle u_{j}}$ are at distance two via a path through ${\displaystyle v_{n}}$, and any two vertices ${\displaystyle v_{i}}$ and ${\displaystyle v_{j}}$ are at distance two via a path through ${\displaystyle u_{1}}$. If two vertices on opposite sides of the bipartition are not adjacent (at distance one), then they are at distance three via a path through both ${\displaystyle u_{1}}$ and ${\displaystyle v_{n}}$. Half-graphs are a special case of the bipartite chain graphs (bipartite graphs in which, on each side of the bipartition, the vertices can be ordered by neighborhood inclusion), which are in turn a special case of the bipartite distance-hereditary graphs. Thus, half-graphs are distance-hereditary. That is, in every connected induced subgraph of a half-graph, the distances are the same as in the half-graph itself.[3]

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]

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]

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.[6] On the other hand, for any integer ${\displaystyle k}$, the graphs that do not have a ${\displaystyle 2k}$-vertex half graph as an induced subgraph obey a stronger version of the regularity lemma with no irregular pairs.[7]

Saharon Shelah's unstable formula theorem in model theory characterizes the stable theories (complete theories that have few types) by the nonexistence of countably infinite half graphs. Shelah defines a complete theory as having the order property if there exist a model ${\displaystyle M}$ of the theory, a formula ${\displaystyle \phi ({\bar {x}},{\bar {y}})}$ on two finite tuples of free variables ${\displaystyle {\bar {x}}}$ and ${\displaystyle {\bar {y}}}$, and a system of countably many values ${\displaystyle {\bar {x}}_{i}}$ and ${\displaystyle {\bar {y}}_{i}}$ for these variables such that the pairs ${\displaystyle {\bigl \{}({\bar {x}}_{i},{\bar {y}}_{i})\mid M\models \phi ({\bar {x}}_{i},{\bar {y}}_{j}){\bigr \}}}$ form the edges of a countable half graph on vertices ${\displaystyle {\bar {x}}_{i}}$ and ${\displaystyle {\bar {y}}_{i}}$. Intuitively, the existence of these half graphs allows one to construct infinite ordered sets within the model. The unstable formula theorem states that a complete theory is stable if and only if it does not have the order property.[8]