Strongly maximal matchings

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A hypergraph is $H=(V,\mathcal E)$, with an arbitrary possibly infinite vertex set and a set of hyperedges. A matching $M\subseteq\mathcal E$ has pairwise disjoint edges. It is strongly maximal if, for every other matching $N$, \[|N\setminus M|\le |M\setminus N|,\] where the comparison is between cardinalities, including infinite ones. Bounded rank means that some fixed $k\in\mathbb N$ satisfies $|e|\le k$ for every $e\in\mathcal E$.

Statement recorded in the supplied source.

Must every bounded-rank hypergraph have a strongly maximal matching? [S2] This is the historical matching part of Conjecture 2.1 in [S2]. Theorem 1.2 of [S3] gives a 3-uniform counterexample, so that question has a negative answer.

Short English statement

Does a uniform finite bound on hyperedge size force a matching that cannot be improved by any competing matching, even through infinitely many changes?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3000084 (AMR-029-0084). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 R. Aharoni, Strongly maximal matchings and strongly minimal covers (2022), Definition 1.2 and Conjecture 2.1, pp.1--2. https://arxiv.org/pdf/2206.02576.
• S3 L. Hollom and B. Randall Shaw, Counterexamples to conjectures on strong maximality and minimality (2025), Introduction, Theorem 1.2, p.2. https://arxiv.org/pdf/2511.13709.