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.

Definition

To define the half graph on $2n$ vertices $u_1,\dots u_n$ and $v_1,\dots v_n$, connect $u_i$ to $v_j$ by an edge whenever $i\le j$.

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

Properties

Distances

In a half graph, every two vertices are at distance one, two, or three. Any two vertices $u_i$ and $u_j$ are at distance two via a path through $v_n$, and any two vertices $v_i$ and $v_j$ are at distance two via a path through $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 $u_1$ and $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.

Matching

The half graph has a unique perfect matching. This is straightforward to see by induction: $u_n$ must be matched to its only neighbor, $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.

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.

Applications

Regularity

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 $k$ subsets, the number of irregular pairs will be at least proportional to $k$. Therefore, it is not possible to strengthen the regularity lemma to show the existence of a partition for which all pairs are regular. On the other hand, for any integer $k$, the graphs that do not have a $2k$-vertex half graph as an induced subgraph obey a stronger version of the regularity lemma with no irregular pairs.

Stability

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 $M$ of the theory, a formula $\phi(\bar x, \bar y)$ on two finite tuples of free variables $\bar x$ and $\bar y$, and a system of countably many values $\bar x_i$ and $\bar y_i$ for these variables such that the pairs $\bigl\$ form the edges of a countable half graph on vertices $\bar x_i$ and $\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.

Computational complexity

Under a form of the exponential time hypothesis, there is no fixed-parameter tractable algorithm for finding a half-graph of a given size in a larger bipartite graph, either as a subgraph or an induced subgraph, when parameterized by the size of the half-graph.

References

{{reflist, 30em, refs=

{{citation
, last1 = Agrawal , first1 = Akanksha
, last2 = Allumalla , first2 = Ravi Kiran
, last3 = Dhanekula , first3 = Varun Teja
, editor1-last = Golovach , editor1-first = Petr A.
, editor2-last = Zehavi , editor2-first = Meirav
, contribution = Refuting FPT algorithms for some parameterized problems under Gap-ETH
, doi = 10.4230/LIPIcs.IPEC.2021.2
, pages = 2:1–2:12
, publisher = Schloss Dagstuhl – Leibniz-Zentrum für Informatik
, series = LIPIcs
, title = 16th International Symposium on Parameterized and Exact Computation, IPEC 2021, September 8–10, 2021, Lisbon, Portugal
, volume = 214
, year = 2021, doi-access = free

{{citation
, last1 = Conlon , first1 = David , author1-link = David Conlon
, last2 = Fox , first2 = Jacob , author2-link = Jacob Fox
, arxiv = 1107.4829
, doi = 10.1007/s00039-012-0171-x
, issue = 5
, journal = Geometric and Functional Analysis
, mr = 2989432
, pages = 1191–1256
, title = Bounds for graph regularity and removal lemmas
, volume = 22
, year = 2012

{{citation
, last = Erdős , first = Paul , author-link = Paul Erdős
, editor1-last = Kölzow , editor1-first = D.
, editor2-last = Maharam-Stone , editor2-first = D.
, contribution = Some combinatorial, geometric and set theoretic problems in measure theory
, publisher = Springer
, series = Lecture Notes in Mathematics
, title = Measure Theory Oberwolfach 1983
, volume = 1089
, year = 1984

{{citation
, last1 = Erdős , first1 = Paul , author1-link = Paul Erdős
, last2 = Hajnal , first2 = András , author2-link = András Hajnal
, doi = 10.1016/0012-365X(85)90148-7
, journal = Discrete Mathematics
, mr = 786496
, pages = 281–285
, title = Chromatic number of finite and infinite graphs and hypergraphs
, url = https://users.renyi.hu/~p_erdos/1985-08.pdf
, volume = 53
, year = 1985, doi-access = free
. 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.

{{citation
, last = Godsil , first = C. D. , authorlink = Chris Godsil
, year = 1985
, doi = 10.1007/bf02579440
, issue = 1
, journal = Combinatorica
, pages = 33–39
, title = Inverses of trees
, volume = 5. See in particular Lemma 2.1.

{{citation, url=https://www.graphclasses.org/classes/gc_1324.html, title=Half graphs, work=Information System on Graph Classes and their Inclusions, access-date=2023-04-15

{{citation
, last1 = Malliaris , first1 = M. , author1-link = Maryanthe Malliaris
, last2 = Shelah , first2 = S. , author2-link = Saharon Shelah
, arxiv = 1102.3904
, doi = 10.1090/S0002-9947-2013-05820-5
, issue = 3
, journal = Transactions of the American Mathematical Society
, mr = 3145742
, pages = 1551–1585
, title = Regularity lemmas for stable graphs
, volume = 366
, year = 2014

{{citation
, last1 = Nešetřil , first1 = Jaroslav , author1-link = Jaroslav Nešetřil
, last2 = Shelah , first2 = Saharon , author2-link = Saharon Shelah
, issue = 6
, journal = European Journal of Combinatorics
, mr = 1995579
, pages = 649–663
, title = On the order of countable graphs
, doi = 10.1016/S0195-6698(03)00064-7
, volume = 24
, year = 2003, arxiv = math/0404319

{{citation
, last = Shelah , first = S. , author-link = Saharon Shelah
, edition = 2nd
, isbn = 0-444-70260-1
, mr = 1083551
, pages = 30–31
, publisher = North-Holland Publishing Co. , location = Amsterdam
, series = Studies in Logic and the Foundations of Mathematics
, title = Classification theory and the number of nonisomorphic models
, volume = 92
, year = 1990

Parametric families of graphs