Counterexamples to conjectures on strong maximality and minimality
Lawrence Hollom, Benedict Randall Shaw · 2025
Read Counterexamples to conjectures on strong maximality and minimality by Lawrence Hollom, Benedict Randall Shaw (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-13709.txt.
Introduction
Lawrence Hollom and Benedict Randall Shaw give counterexamples to several conjectures on strong maximality and minimality in infinite graphs and hypergraphs. Strongly maximal matchings and strongly minimal covers were expected to exist broadly, under conjectures tied to names such as Aharoni and Tardos. Their constructions show those expectations fail in clean cases.
In particular, they build three-uniform hypergraphs with no strongly maximal matching and others with no strongly minimal cover. From the cover construction they derive a graph with no strongly minimal coloring. Refinements of the original problems are treated as well, so the paper closes a cluster of open questions rather than a single one.
Catalog record
| CREATOR | Lawrence Hollom, Benedict Randall Shaw |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-13709
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Counterexamples to conjectures on strong maximality and minimality Lawrence Hollom, Benedict Randall Shaw Abstract We provide counterexamples to several conjectures concerning strongly maximal and strongly minimal structures in infinite graphs and hypergraphs. In particular, we construct 3-uniform hypergraphs without strongly maximal matchings and without strongly minimal covers, and from our construction for covers we build a graph with no strongly minimal colouring. We also consider several refinements of these problems. Our results resolve conjectures and questions of Aharoni; Aharoni and Berger; Aharoni, Berger, Georgakopoulos, and Sprüssel; Aharoni and Korman; and Tardos. largesymbols”0C 1 Introduction Many problems in graph theory ask when one may find a certain object of the greatest possible size. For example, Hall’s theorem gives a condition for the existence of a matching which covers every vertex, and König’s theorem tells us that the largest matching and the smallest vertex-cover (that is, a set of vertices of the graph which meet every edge) have the same size. When moving to the infinite case, versions of these results concerning only cardinality tend to be weak, and easy to prove. For example, given Hall’s condition in an infinite bipartite graph, one can simply apply a greedy algorithm to construct a matching with the same cardinality as the vertex set of the graph. However, the fact that the object—a matching, in this case—attains the maximum possible size tells us very little about its structure: in contrast with the finite case, it may not even be maximal. However, although in fact we may show a maximal matching exists, even that may not capture adequately the notion of being a ‘largest’ object. One way around these issues is to strengthen our desired notion of ‘maximality’ to ‘strong maximality’, which informally means that we can make no local improvement to our object. More precisely, a strongly maximal matching of a graph G is a matching M such that, for every matching M^{\prime} of G , we have \lvert M\setminus M^{\prime}\rvert\geq\lvert M^{\prime}\setminus M\rvert . Similarly, a strongly minimal vertex-cover of G is a vertex-cover C such that, for every vertex-cover C^{\prime} of G , we have \lvert C\setminus C^{\prime}\rvert\leq\lvert C^{\prime}\setminus C\rvert . The notion of strong maximality more accurately captures our intuition of a ‘largest’ object. Returning to König’s theorem, it was proved by Aharoni [ 5 ] in 1984, confirming a conjecture of Erdős (see e.g. [ 11 ] ) that in any bipartite graph G one may find a strongly maximal matching M and a strongly minimal vertex-cover C , and furthermore M and C are orthogonal—that is, one may find a bijection between C and M such that the vertex of C is contained in the corresponding edge of M . In fact, strong maximality and minimality of these objects follows from orthogonality alone, much like in the finite case. Following on from this result, it is natural to then ask whether hypergraphs must also have strongly maximal matchings and strongly minimal covers. Here a hypergraph H comprises a vertex set V together with a set E of edges, each of which is a subset of V . We say that H is k - uniform if every edge has size k . Then a matching is a subset of E whose edges are pairwise disjoint; an edge-cover is a subset of E whose union is V ; and a vertex-cover is a set of vertices which has non-empty intersection with every edge of E . Indeed, Aharoni [ 6 , Problem 5.5] asked in 1991 whether every hypergraph with finite edges contains a strongly maximal matching, and in 1992, Aharoni and Korman [ 4 , Conjecture 5.4] conjectured that, in the absence of isolated vertices, there should also be a strongly minimal edge-cover. Erdős [ 9 ] expected the conjecture to be false and, indeed, counterexamples were found for both matchings and edge-covers by Ahlswede and Khachatrian [ 8 ] , and van der Zypen [ 12 ] respectively, in results which we shall return to later. Nevertheless, these conjectures were later refined by Aharoni, Berger, Georgakopoulos, and Sprüssel [ 1 , Conjecture 1.4] to the following. Conjecture 1.1 . In any hypergraph with finitely bounded size of edges and no isolated vertices there exist a strongly maximal matching and a strongly minimal edge-cover. Here the requirement that there be no isolated vertices is simply to ensure that there is any edge-cover at all. Our first two results show that both parts of 1.1 are false. Theorem 1.2 . There is a 3 -uniform hypergraph H_{1} with no strongly maximal matching. Theorem 1.3 . There is a 3 -uniform hypergraph H_{2} with no isolated vertices and no strongly minimal edge-cover. We remark here that, by taking a disjoint union of H_{1} and H_{2} , we obtain a 3-uniform hypergraph which has neither a strongly maximal matching not a strongly minimal edge-cover. Covers and matchings are not the only objects for which one might consider strong minimality and maximality. Indeed, Aharoni, Berger, Georgakopoulos, and Sprüssel [ 1 ] also highlighted the following problem. Conjecture 1.4 . In every graph there exists a strongly minimal cover of the vertex set by independent sets. The structure posited to exist by 1.4 is referred to by Aharoni and Berger in [ 3 ] as a strongly minimal colouring , in that such a strongly minimal cover would be a proper vertex-colouring of the graph satisfying a strongly minimal condition on the colour classes. Problems of this form were also considered in Aharoni and Berger’s seminal paper [ 2 ] proving Menger’s theorem for infinite graphs. Indeed, alongside 1.1 , they also conjectured that every flag complex —a hypergraph which is down-closed (every subset of an edge is an edge) and 2-determined (if all 2-element subsets of a set are edges, then so is that set)—has a strongly minimal edge-cover. We show that the above problem of flag complexes is equivalent to 1.4 , and thus deduce the following result. Theorem 1.5 . There is a graph G with no strongly minimal colouring. Aharoni and Berger also stated the following problem, attributed to Tardos (see [ 2 , Problem 10.4] ). Question 1.6 . Is it true that, in every hypergraph with finite edges, there exists a matching M such that no matching M^{\prime} exists for which \lvert M\setminus M^{\prime}\rvert=1 and \lvert M^{\prime}\setminus M\rvert=2 ? Our last result resolves 1.6 in the negative. Theorem 1.7 . There is a hypergraph H_{3} such that, for every matching M of H_{3} , there is a matching M^{\prime} of H_{3} with \lvert M\setminus M^{\prime}\rvert=1 and \lvert M^{\prime}\setminus M\rvert=2 . Finally, 1.1 was also repeated in [ 7 ] , where it was also conjectured that every hypergraph has a strongly minimal vertex-cover, but this is easily seen to be false, as shown in Section 3.4 . The constructions for Theorems 1.2 and 1.3 both begin with the counterexamples found for the case in which edges may have unbounded size, which are presented in Section 1.1 . Both constructions work by replacing the edges in the known counterexamples with a ‘gadget’, which simulates the large edges with only 3-edges and 2-edges, before the 2-edges are later replaced with 3-edges. This