1 Introduction↩︎

A hypergraph \(H\) is a pair \((V,E)\), where \(V=V(H)\) is a non-empty finite set of vertices and \(E=E(H)\) is a family of subsets of \(V\) called edges. We always assume that the edges are non-empty and every vertex belongs to at least one edge, so that \(V=\bigcup E\). We often write edges without braces and commas, e.g., \(123\) instead of \(\{1,2,3\}\).

The rank of \(H\) is \(\max_{e \in E(H)} |e|\). If \(|e|=k\) for every \(e \in E(H)\), we say that \(H\) is \(k\)-uniform. The degree of a vertex \(v\) is \(|\{e \in E(H): v \in e\}|\). If every \(v \in V(H)\) has the same degree \(d\), we say that \(H\) is \(d\)-regular, or just regular without specifying the degree.

An edge cover in \(H\) is a subfamily \(E' \subseteq E(H)\) that covers the entire vertex set, i.e., \(V=\bigcup E'\). We will be interested in edge covers that are as small as possible. The edge covering number of \(H\) is \[\rho(H) = \min \{|E'|: E' \textrm{ is an edge cover in } H\}.\] The combinatorial optimization problem of determining \(\rho(H)\) is usually called the (unweighted) set cover (or covering) problem. When restricted to hypergraphs of rank \(k\), it is called the \(k\)-set cover problem. For \(k=2\), i.e., in the case of graphs, computing the edge covering number is easy: it is equivalent to finding the maximum size of a matching. But already for \(k=3\), the \(3\)-set cover problem is known to be NP-hard (e.g., by a reduction from the \(3\)-dimensional matching problem on Karp’s list in [1]). There is a large body of combinatorial opimization literature devoted to approximating the edge covering number; see [2] for a survey.

An efficient lower bound on the edge covering number is obtained by considering its linear programming relaxation. A fractional edge cover in \(H\) is a function \(f: E(H) \to \mathbb{R}_+\) that covers \(V(H)\) in the sense that \(\sum_{e \ni v} f(e) \ge 1\) for every vertex \(v \in V(H)\). Its size \(|f|\) is \(\sum_{e \in E(H)} f(e)\). The fractional edge covering number of \(H\) is \[\rho^*(H) = \min \{|f|: f \textrm{ is a fractional edge cover in } H\}.\] An edge cover is a \(\{0,1\}\)-valued fractional edge cover, hence \(\rho(H) \ge \rho^*(H)\). The ratio \(\rho(H)/\rho^*(H)\), measuring the relative distance between the integral solution and its fractional counterpart, is called the edge-cover integrality gap of \(H\). An upper bound on the integrality gap over a class of hypergraphs allows to control the quality of the \(\rho^*(H)\) approximation to \(\rho(H)\) for \(H\) in that class. The following classic upper bound due to Lovász [3] has had many applications in graph and hypergraph theory, combinatorial optimization, additive number theory, and more. (The original formulation of Lovász’s bound was in terms of the vertex-cover integrality gap for hypergraphs of a given maximum degree; the form we give here is equivalent by interchanging the roles of vertices and edges while keeping the incidence relation.)

Examples for large \(k\) are known that show that Lovász’s bound cannot be improved by a multiplicative constant (we cite below, in more precise form, such a result). However, Fujito and Okumura [4] have improved the bound by an additive constant: \[\frac{\rho(H)}{\rho^*(H)} \le \sum_{i=1}^k \frac{1}{i} - \frac{1}{6} \textrm{ \,\, for hypergraphs } H \textrm{ of rank } k \ge 2.\] This improvement is significant for small values of \(k\). For \(k=2\) it improves the bound from \(\frac{3}{2}\) to \(\frac{4}{3}\), which is best possible. Indeed, the triangle graph \(K_3\) has \(\rho(K_3)=2\) and \(\rho^*(K_3)=\frac{3}{2}\). For \(k=3\) it improves the bound from \(\frac{11}{6}\) to \(\frac{5}{3}\). As far as we know, the \(\frac{5}{3}\) bound is the best one known prior to this work. Here we focus on the \(k=3\) case, and establish the following best possible improvement.

Before showing the sharpness of this bound, we state two increasingly special cases of Theorem 2. A fractional edge cover \(f: E(H) \to \mathbb{R}_+\) is exact if it satisfies the covering constraints as equalities: \(\sum_{e \ni v} f(e) = 1\) for all \(v \in V(H)\). Suppose that \(H\) is a \(3\)-uniform hypergraph with \(|V|=n\), and \(f\) is a fractional edge cover in \(H\). Then \[|f| = \frac{1}{3} \sum_{v \in V(H)} \sum_{e \ni v} f(e) \ge \frac{1}{3} \sum_{v \in V(H)} 1 = \frac{n}{3},\] and equality holds if and only if \(f\) is exact. Thus, if \(H\) has an exact fractional edge cover, then \(\rho^*(H) = \frac{n}{3}\). Therefore, Theorem 2 immediately gives the following.

Next, suppose that \(H\) is a \(3\)-uniform, \(d\)-regular hypergraph. Then \(f: E(H) \to \mathbb{R}_+\) defined by \(f(e) = \frac{1}{d}\) for all \(e \in E(H)\) is an exact fractional edge cover in \(H\). We get the following special case of Corollary 1.

We proceed to give several examples of \(3\)-uniform, regular hypergraphs that attain equality in Corollary 2. This will show that Theorem 2 and its two corollaries are sharp.

Examples satisfying \(\rho(H) = \frac{n}{2}\) for arbitrarily large \(n\) can be built from any of the above small examples by taking disjoint copies. The following construction gives arbitrarily large connected examples of equality.

In a related paper, de A. Moreira and Kohayakawa [5] studied the ratio \(\rho(H)/\rho^*(H)\) for hypergraphs that are uniform and regular. They defined the function \[f(k) = \limsup_{n \to \infty} \max_H \frac{\rho(H)}{\rho^*(H)},\] where the maximum is taken over all \(k\)-uniform, regular hypergraphs on \(n\) vertices. Based on a probabilistic construction for the lower bound and on Lovász’s upper bound, they proved that for any large enough fixed \(k\) \[\ln k - 12 \ln\ln k \le f(k) \le 1 + \ln k.\] They showed that \(f(2) = \frac{4}{3}\), and posed the open problem of determining \(f(k)\) for all \(k \ge 3\). Our Corollary 2 together with the above examples of equality solve the case \(k=3\) of their problem: \(f(3) = \frac{3}{2}\).

The proof of Theorem 2 is quite intricate, and relies on the Gallai-Edmonds decomposition of graphs and some structural properties of factor-critical graphs. Those are recalled or developed in Section 2, and the proof itself appears in Section 3. It is worth mentioning that the proof of Fujito and Okumura’s [4] previous improvement to Lovász’s bound, establishing the \(\frac{5}{3}\) upper bound for \(k=3\), also used the Gallai-Edmonds decomposition. However, we apply it to a different graph associated with the hypergraph of rank \(3\), and use the decomposition in other ways than they did.

In Section 4 we present an application of Theorem 2 to a Gale-Shapley type stable marriage problem, where we consider triples instead of couples.

2 Preliminaries↩︎

Although Theorem 2 is about hypergraphs of rank \(3\), our proof will mostly be in terms of graphs that are associated with such hypergraphs. Here we introduce some terminology and notation for graphs, and recall or develop the main tools that we will use in the proof.

A graph \(G=(V,E)\) is a \(2\)-uniform hypergraph. A matching in \(G\) is a set \(M \subseteq E\) of pairwise disjoint edges. The set of vertices covered by the matching \(M\) is \(\bigcup M \subseteq V\). A maximum matching \(M\) is one that maximizes \(|M|\) among all matchings in \(G\). When \(|V|\) is even, a perfect matching \(M\) is one with \(\bigcup M = V\). When \(|V|\) is odd, a near-perfect matching \(M\) is one with \(|\bigcup M| = |V| - 1\).

Let \(G=(V,E)\) be a graph, and let \(U \subseteq V\). The induced subgraph of \(G\) on \(U\) is the graph \(G[U] = (U, E[U])\) where \(E[U]\) consists of all edges in \(E\) having both endpoints in \(U\). When \(U = V \setminus X\), we also write \(G[U]\) as \(G - X\). The contraction of \(X\) in \(G\) is the graph \(G/X\) obtained from \(G - X\) by adding a new vertex \(v_X\) and an edge \(uv_X\) for every \(u \in U\) such that \(uv \in E\) for at least one \(v \in X\).

Let \(G\) be a graph, and let \(O\) be an odd cycle in \(G\). We say that \(O\) is induced if it has no chords. If \(O\) is not induced, an odd shortening of \(O\) is a cycle \(O'\) obtained from \(O\) by partitioning its edge set into odd paths \(Q_1, Q_2, \ldots , Q_k\), where \(k \ge 3\) and each \(Q_i\) is either an edge of \(O\) or its endpoints form a chord, and replacing each of the latter \(Q_i\) by the corresponding chord. Thus, the length of \(O'\) is \(k\), which is necessarily odd. We will need the following simple lemma.

2.1 Factor-critical graphs↩︎

A graph \(G\) with an odd number of vertices is factor-critical if for every \(v \in V(G)\) there exists a near-perfect matching \(M\) in \(G\) such that \(\bigcup M = V(G) \setminus \{v\}\). Factor-critical graphs will play a central role in our proof of Theorem 2. We will need the following lemma, showing that this property can be preserved under contraction.

The next lemma allows us to decompose a factor-critical graph into an odd cycle of smaller factor-critical graphs.

2.2 The Gallai-Edmonds decomposition↩︎

Gallai [7], [8] and Edmonds [9] introduced a canonical decomposition that applies to any graph and can be used to describe the family of maximum matchings in it. We recall here the definition of this decomposition and some of its properties (see [10]).

Let \(G\) be a graph. We call a vertex \(v \in V(G)\) dispensable in \(G\) if there is a maximum matching \(M\) in \(G\) with \(v \notin \bigcup M\). We decompose \(V(G)\) into three (possibly empty) parts as follows: \[\begin{align} D & = & \{ v \in V(G): v \textrm{ is dispensable in } G\} \\ A & = & \{ u \in V(G) \setminus D: u \textrm{ is adjacent to at least one vertex in } D\} \\ C & = & V(G) \setminus (D \cup A) \end{align}\] If \(D \ne \emptyset\), we further decompose \(D\) into the vertex sets \(D_1, D_2, \ldots , D_r\) of the connected components of \(G[D]\). If \(D = \emptyset\) set \(r=0\).

We now list, for later use, a few immediate consequences of Theorem 3. In each of them, we refer to the Gallai-Edmonds decomposition of \(G\) as defined above.

In addition to what we proved in the previous subsection, we will need another fact about the behavior of factor-critical graphs under contraction. Its proof uses the Gallai-Edmonds decomposition.

2.3 Matchings in bipartite graphs↩︎

We recall here some facts about matchings in bipartite graphs. Let \(G\) be a bipartite graph with bipartition \((X, Y)\). For \(S \subseteq X\) we denote by \(N(S) \subseteq Y\) the set of vertices having at least one neighbor in \(S\). We say that a set \(U \subseteq V(G)\) is matchable if there exists a matching \(M\) in \(G\) with \(U \subseteq \bigcup M\). Hall’s theorem says that \(X\) is matchable if and only if \(|N(S)| \ge |S|\) for every \(S \subseteq X\). We will need the following well-known generalization of this theorem, attributed to Ore [11]. Define the deficiency of \(G\) with respect to \(X\) to be \[\mathrm{def}_X(G) = \max \{|S| - |N(S)|: S \subseteq X\}.\]

We will also use a result of Mendelsohn and Dulmage [12] allowing to combine matchability of subsets of different sides.

3 Proof of Theorem 2↩︎

Let \(H = (V, E)\) be a hypergraph of rank \(3\). We use the notation \[E_i = \{ e \in E: |e| = i\}, \,\, i = 1,2,3\] to refer to the edges of each possible size. We also define the shadow of \(E_3\): \[\partial E_3 = \{ e \setminus \{v\}: v \in e \in E_3\}.\] This is the family of subsets of size \(2\) of edges of size \(3\). We will consider the following graph associated with \(H\): \[G_H = (V, E_2 \cup \partial E_3).\] For a function \(f: E \to \mathbb{R}_+\) we write \[|f|_- = \sum_{e \in E_1 \cup E_2} f(e).\] This is the total weight assigned by \(f\) to edges of size less than \(3\). We will deduce Theorem 2 from the following proposition.

Note that condition (a) implies that \(|V|\) is odd. By taking a near-perfect matching in \(G_H\) and one additional edge covering the missing vertex, we can cover \(V\) by \(\frac{|V|-1}{2} + 1\) edges of \(G_H\). Since every edge of \(G_H\) is either an edge of \(H\) or is contained in one, it immediately follows that \(\rho(H) \le \frac{|V|-1}{2} + 1\). Our task in proving Proposition 6 is ‘just’ to save \(1\) in this upper bound, by using edges of size \(3\) and the full power of the assumptions.

In Subsection 3.1 we will show how Theorem 2 follows from Proposition 6. Then, in the next two subsections, we will prove Proposition 6.

3.1 Proof of Theorem 2 from Proposition 6↩︎

Let \(f: E \to \mathbb{R}_+\) be a fractional edge cover. For \(v \in V\) we write \[|f|_{v^+} = \sum_{e \ni v} f(e) - 1.\] Bearing in mind that \(\sum_{e \ni v} f(e) \ge 1\) for every \(v\), we think of \(|f|_{v^+}\) as the extra coverage of \(f\) at the vertex \(v\). We further write \[|f|_+ = \sum_{v \in V} |f|_{v^+}.\] This is the total extra coverage of \(f\). Note that \(f\) is exact if and only if \(|f|_+ = 0\).

We first observe that if Proposition 6 is true, then it remains true when condition (b) is relaxed to: \[(b')\,\, H\,\, has\,\, a\,\, fractional\,\, edge\,\, cover\,\, f: E \to \mathbb{R}_+\,\, such\,\, that\,\, |f|_- + |f|_+ < 1.\] Indeed, assume that \(f\) satisfies \(|f|_- + |f|_+ < 1\). For a vertex \(v\) with \(|f|_{v^+} > 0\), we reassign a total weight of \(|f|_{v^+}\) from edges \(e \in E_3\) containing \(v\) to the corresponding \(e \setminus \{v\}\). This reduces \(|f|_+\) by \(|f|_{v^+}\) while increasing \(|f|_-\) by the same amount, thus preserving \(|f|_- + |f|_+\). Repeating this for every \(v\) with \(|f|_{v^+} > 0\), we end up with a modified function \(\tilde{f}\) such that \(|\tilde{f}|_- = |f|_- + |f|_+ < 1\) and \(|\tilde{f}|_+ = 0\). In the course of doing this, we may have created edges of size \(2\) that were not in \(H\), so let \(\tilde{H}\) be the hypergraph obtained by adding those edges to \(H\). Now \(\tilde{f}\) is an exact fractional edge cover in \(\tilde{H}\) satisfying condition (b). Note that \(G_{\tilde{H}} = G_H\), so condition (a) still holds. Proposition 6 implies that \(\rho(\tilde{H}) \le \frac{|V|-1}{2}\). Because every edge of \(\tilde{H}\) is contained in an edge of \(H\), we conclude that \(\rho(H) \le \frac{|V|-1}{2}\) as desired.

Assuming Proposition 6, we proceed to prove Theorem 2. Let \(H = (V, E)\) be a hypergraph of rank \(3\), and let \(f: E \to \mathbb{R}_+\) be a fractional edge cover in \(H\). We have to prove that \(\rho(H) \le \frac{3}{2} |f|\).

We first prove this in the special case when \(H\) is \(3\)-uniform. Consider the graph \(G_H\) associated with \(H\), which is \((V, \partial E)\) in this case. Let \(D = D_1 \cup D_2 \cup \cdots \cup D_r\), \(A\), \(C\) be its Gallai-Edmonds decomposition. For each \(i=1,2, \ldots , r\) we consider a graph and a hypergraph defined on the vertex set \(D_i\). The graph is \(G_H[D_i]\), it is factor-critical by Theorem 3(a). The hypergraph is \(H_{D_i}\), the restriction of \(H\) to \(D_i\), having the edge set \[\label{eq:rest} E(H_{D_i}) = \{ e \cap D_i: e \in E, e\cap D_i \ne \emptyset\}.\tag{1}\] Observe that \(G_{H_{D_i}} = G_H[D_i]\). We also define \(f_i: E(H_{D_i}) \to \mathbb{R}_+\) by \[\label{eq:frest} f_i(e') = \sum \{f(e): e \in E, e \cap D_i = e'\}.\tag{2}\] Note that \(f_i\) is a fractional edge cover in \(H_{D_i}\), and \(|f_i|_{v^+} = |f|_{v^+}\) for every \(v \in D_i\). Observe also that while \(|f|_- = 0\) by the assumption that \(H\) is \(3\)-uniform, \(|f_i|_-\) may be positive: it is given by \[\label{eq:minus} |f_i|_- = \sum \{ f(e): e \in E, e \cap D_i \ne \emptyset ,e \setminus D_i \ne \emptyset \}.\tag{3}\] We distinguish between those \(D_i\) for which \(|f_i|_- + |f_i|_+\) is high (at least \(1\)) and those for which it is low (less than \(1\)). We assume w.l.o.g.that \[\begin{align} |f_i|_- + |f_i|_+ \ge 1\,\, & \textrm{for} & 1 \le i \le h, \\ |f_i|_- + |f_i|_+ < 1\,\, & \textrm{for} & h < i \le r, \end{align}\] where \(0 \le h \le r\). For every \(h < i \le r\) we can apply Proposition 6 in its generalized form (with conditions (a) and (b’)) to conclude that \(\rho(H_{D_i}) \le \frac{|D_i|-1}{2}\).

In order to handle \(D_1, D_2, \ldots , D_h\), we consider the corresponding vertices \(1, 2, \ldots , h\) in the bipartite graph \(\Gamma_{G_H}\) defined in Corollary 4. We claim that for every \(S \subseteq \{1,2, \ldots , h\}\) we have \[\label{eq:def} |S| - |N(S)| \le |f|_+,\tag{4}\] where \(N(S) \subseteq A\) is the set of neighbors of vertices of \(S\) in \(\Gamma_{G_H}\). Indeed, given \(i \in S\), for every \(e \in E\) such that \(e \cap D_i \ne \emptyset\), we have \(e \setminus D_i \subseteq N(S)\) by Corollary 3 and the definition of \(\Gamma_{G_H}\). It follows from (3 ) that each \(i \in S\) contributes at least \(|f_i|_-\) to the sum \(\sum_{u \in N(S)} \sum_{e \ni u} f(e)\). Adding up these contributions we get \[\sum_{i \in S} |f_i|_- \le \sum_{u \in N(S)} \sum_{e \ni u} f(e) = \sum_{u \in N(S)} (1 + |f|_{u^+}) = |N(S)| + \sum_{u \in N(S)} |f|_{u^+}.\] Furthermore, \[\sum_{i \in S} |f_i|_+ = \sum_{i \in S} \sum_{v \in D_i} |f_i|_{v^+} = \sum_{v \in \bigcup _{i \in S} D_i} |f|_{v^+}.\] We conclude that \[|S| \le \sum_{i \in S} (|f_i|_- + |f_i|_+) \le |N(S)| + \sum_{u \in N(S)} |f|_{u^+} +\sum_{v \in \bigcup_{i \in S} D_i} |f|_{v^+} \le |N(S)| + |f|_+,\] proving inequality (4 ).

Since (4 ) holds for every \(S \subseteq \{1,2, \ldots , h\}\), it follows from Theorem 4 that \(\{1,2, \ldots , h\}\) has a subset \(B\) of size at least \(h - |f|_+\) that is matchable in \(\Gamma_{G_H}\). We also know from Corollary 4 that \(A\) is matchable in \(\Gamma_{G_H}\). Using Theorem 5 we obtain a matching \(M\) in \(\Gamma_{G_H}\) such that \(A \cup B \subseteq \bigcup M\). Let \(I \subseteq \{1,2, \ldots , r\}\) be the set of vertices on this side that are covered by \(M\), and let \(I^c = \{1,2, \ldots , r\} \setminus I\). As \(B \subseteq I\), we have \(|I^c \cap \{1,2, \ldots , h\}| \le |f|_+\).

Returning from \(\Gamma_{G_H}\) to \(G_H\) itself, we can replace each edge \(iu\) in \(M\) by an edge \(v_iu\) of \(G_H\), where \(v_i\) is an arbitrarily chosen neighbor of \(u\) in \(D_i\). Let \(M'\) be the obtained matching in \(G_H\). By adding to \(M'\) a perfect matching of \(G_H[D_i] - \{v_i\}\) for each \(i \in I\), and a perfect matching of \(G_H[C]\), we get a matching \(M''\) in \(G_H\) that covers \(V \setminus \bigcup_{i \in I^c} D_i\).

Now, we can find an edge cover in \(H\) as follows. We replace each edge in \(M''\) by an edge of \(H\) containing it. This uses \(\frac{1}{2} |V \setminus \bigcup_{i \in I^c} D_i|\) edges. For each \(i \in I^c \cap \{1,2, \ldots , h\}\) there are \(\frac{|D_i|-1}{2} + 1\) edges of \(G_H\) that cover \(D_i\), and we replace them by edges of \(H\) containing them. This uses at most \(\sum_{i \in I^c \cap \{1,2, \ldots , h\}} \frac{|D_i|+1}{2}\) edges. For each \(i \in I^c \setminus \{1,2, \ldots , h\}\) there are \(\frac{|D_i|-1}{2}\) edges of \(H_{D_i}\) that cover \(D_i\) (as shown above), and we replace them by edges of \(H\) that contain them. This uses \(\sum_{i \in I^c \setminus \{1,2, \ldots , h\}} \frac{|D_i|-1}{2}\) edges. Summing up, this gives \[\begin{align} \rho(H) & \le & \frac{1}{2} |V \setminus \bigcup _{i \in I^c} D_i| + \sum_{i \in I^c \cap \{1,2, \ldots , h\}} \frac{|D_i|+1}{2} + \sum _{i \in I^c \setminus \{1,2, \ldots , h\}} \frac{|D_i|-1}{2} \\ & = & \frac{1}{2} \bigl( |V| + |I^c \cap \{1,2, \ldots , h\}| - |I^c \setminus \{1,2, \ldots , h\}|\bigr) \\ & \le & \frac{1}{2}(|V| + |f|_+) \\ & = & \frac{1}{2} \sum_{v \in V} (1 + |f|_{v^+}) \\ & = & \frac{1}{2} \sum_{v \in V} \sum_{e \ni v} f(e) \\ & = & \frac{1}{2} \sum_{e \in E} 3f(e) \\ & = & \frac{3}{2} |f|. \end{align}\] This completes the proof of Theorem 2 from Proposition 6 in the case of \(3\)-uniform hypergraphs.

We treat the general rank \(3\) case by reducing it to the \(3\)-uniform case. Let \(H = (V, E)\) and a fractional edge cover \(f: E \to \mathbb{R}_+\) be given. If there are two edges \(e \subsetneq e'\) in \(E\), we reassign any weight on \(e\) to \(e'\). Doing this for all such pairs, and removing from \(E\) any edge with weight \(0\), we may assume that there is no containment among edges in \(E\), and all of them have positive weight. If there is a singleton edge \(\{v\}\), then it is the only one containing \(v\), so its weight must be \(1\) (or more). We remove the vertex \(v\) and the edge \(\{v\}\), find a good edge cover in the remaining hypergraph, and add \(\{v\}\) to get a good cover in \(H\). Thus, we may assume that there is no singleton edge and there is at least one edge of size \(2\) (otherwise \(H\) is \(3\)-uniform).

Let \(m > 0\) be the total weight of the edges of size \(2\), and let \(k\) be an integer so that \(km \ge 1\). We form a new \(3\)-uniform hypergraph \(kH\) on the vertex set \(\bigcup _{i=1}^k V_i \cup \{w\}\), where each \(V_i\) is a disjoint copy of \(V\), and \(w\) is a new vertex. In each \(V_i\) we have copies of all edges of \(H\) of size \(3\), with their original weight. For each edge \(uv\) of size \(2\) in \(H\), we place \(k\) edges \(u_iv_iw\) where \(u_iv_i\) is its copy in \(V_i\), and assign to each of them the weight of \(uv\). Let \(kf\) be the resulting weight function on \(E(kH)\). Clearly, \(kf\) is a fractional edge cover in \(kH\), and \(|kf| = k|f|\). Also \(\rho(kH) \ge k\rho(H)\). Applying Theorem 2 to \(kH\) gives \(\rho(kH) \le \frac{3}{2} |kf|\). We deduce that \(k\rho(H) \le \frac{3}{2} k|f|\) and therefore \(\rho(H) \le \frac{3}{2} |f|\) as required.

3.2 The structure of a minimal counterexample to Proposition 6↩︎

In view of the previous subsection, it remains to prove Proposition 6. Assuming that it is false, we consider a counterexample \(H = (V, E)\) with \(|V|\) as small as possible. In this subsection we prove Lemma 5. Roughly speaking, it identifies a subgraph of \(G_H\) which is already factor-critical, and can be constructed in a particular way. Then, in the next subsection, we will obtain a contradiction by showing that such a structured counterexample cannot exist.

3.3 No such structured counterexample to Proposition 6 exists↩︎

We begin this subsection with some terminology and notation. An edge-ordered graph \(G_<\) is a graph \(G = (V, E)\) equipped with a linear order \(<\) on its edge set \(E\). If \(e_1 < e_2\) we think of \(e_1\) as having appeared before \(e_2\). For \(e \in E\), we denote by \(G^{(e)} = (V, E^{(e)})\) the subgraph of \(G\) formed before \(e\), i.e., \(E^{(e)} = \{ e' \in E: e' < e\}\).

Let \(V\) be a vertex set and let \(G\) and \(H\) be a graph and a \(3\)-uniform hypergraph, respectively, on \(V\). A family of disjoint edges, one of which is in \(E(H)\) and the others in \(E(G)\), whose union is \(U \subseteq V\) will be called a \(G!H\) cover of \(U\). Note that the number of edges in a \(G!H\) cover of \(U\) is \(\frac{|U|-1}{2}\). We will say that \(U\) is \(G!H\) coverable if such a family exists.

The following lemma will serve to prove that a counterexample to Proposition 6, structured as in Lemma 5, cannot exist.

We first show how Lemma 5 and Lemma 6 combine to prove Proposition 6.

 Assume, for the sake of contradiction, that Proposition 6 is false. Then it has a minimal counterexample \(H = (V, E)\). By Lemma 5 there exists a vertex \(x \in V\) and there is a sequence \(G^{(1)}, G^{(2)}, \ldots , G^{(t)}\) of subgraphs of \(G_H\) satisfying (a), (b) and (c) in that lemma.

We are going to apply Lemma 6 to the graph \(G^{(t)}\), which is factor-critical by (b), equipped with a suitable order \(<\) on \(E^{(t)}\), and the hypergraph \((V, E_3)\). The order \(<\) corresponds to the construction of \(G^{(t)}\): the edges in (a), namely \(E^{(1)} = \{e \in E_2: x \in e\} \cup \partial E_3\) come first (in arbitrary order) and then, if \(t > 1\), come the edges \(e_1, e_2, \ldots , e_{t-1}\) added in (c), in this order. Every edge in \(E_3\) contains three edges of \(\partial E_3\), hence of \(G^{(t)}\). The fact that, for the vertex \(x\) given by Lemma 5, every edge \(e \in E^{(t)}\) satisfies condition (\(\alpha\)), (\(\beta\)) or (\(\gamma\)) in Lemma 6 follows from the construction. Indeed, if \(e\) fails to satisfy (\(\alpha\)) or (\(\beta\)), then \(e = e_k\) for some \(1 \le k < t\). But then the graph \(G^{(e)}\) in the notation of Lemma 6 is exactly \(G^{(k)}\) in the construction of Lemma 5, and condition (\(\gamma\)) for \(e\) follows from condition (c) of the construction.

Thus, all the requirements in Lemma 6 hold. The lemma guarantees the existence of a family of \(\frac{|V|-1}{2}\) edges covering \(V\), one of which is in \(E_3\) and the others in \(E^{(t)}\). Every edge in \(E^{(t)}\) is in \(E(G_H)\), hence contained in an edge of \(H\). Replacing those edges by edges of \(H\) containing them, we obtain an edge cover in \(H\) of size \(\frac{|V|-1}{2}\). This contradicts our choice of \(H\) as a counterexample to Proposition 6. 0◻

It remains to prove Lemma 6. The proof will be by induction on \(|V|\), using contraction in the induction step. The following claim will be useful in this context, and we start with its statement and proof.

 Let \(V\), \(G_<\), \(H\), and \(x \in V\) be as in the statement of the lemma. As \(G\) is factor-critical and \(|V| > 1\), let \(U_1, U_2, \ldots , U_{2k+1}\) be a partition of \(V\) as in Lemma 3. We first treat the special case in which both of the following hold:

• Every edge \(e \in E(G)\) satisfies condition (\(\alpha\)) or (\(\beta\)) in Lemma 6.

• Every \(U_i\), except possibly the one containing \(x\), is a singleton.

In this special case, we prove the lemma by explicitly constructing a \(G!H\) cover of \(V\).

Assume w.l.o.g.that \(x \in U_1\). Let \(U_i = \{v_i\}\) for \(i=2,3, \ldots , 2k+1\). Consider the edge \(v_2v_3 \in E(G)\). Because it does not contain \(x\), it must satisfy condition (\(\beta\)). Thus, there exists a vertex \(u\) such that \(v_2v_3u \in E(H)\). Suppose first that \(u = v_i\) for some \(5 \le i \le 2k+1\). Since \(v_2v_3u\) must contain at least two edges of \(G\), either \(v_2u\) or \(v_3u\) is in \(E(G)\). In either case, we get an edge between two non-cyclically adjacent \(U_i\)’s, contradicting the structure described in Lemma 3. It follows that \(u = v_4\) or \(u \in U_1\).

If \(u = v_4\) we obtain a \(G!H\) cover of \(V\) by taking \(v_2v_3u\), \(v_5v_6, \ldots , v_{2k-1}v_{2k}\), \(v_{2k+1}v\) for some \(v \in U_1\), and a perfect matching in \(G[U_1] - \{v\}\). If \(u \in U_1\) we use \(v_2v_3u\), \(v_4v_5, \ldots , v_{2k}v_{2k+1}\), and a perfect matching in \(G[U_1] - \{u\}\). This proves the lemma in the special case.

When the special case does not hold, there are two possibilities.

Possibility 1. Every edge \(e \in E(G)\) satisfies condition (\(\alpha\)) or (\(\beta\)) in Lemma 6, and there exists a \(U_i\) such that \(x \notin U_i\) and \(|U_i| > 1\).

Possibility 2. There exists an edge \(e \in E(G)\) that satisfies only condition (\(\gamma\)) in Lemma 6.

We will handle these possibilities by induction on \(|V|\). We begin with a general description of the argument, which is valid for both possibilities. Later on, we will fill in the details, some of which differ between the two possibilities.

We assume, for the sake of contradiction, that \(V\) is not \(G!H\) coverable. We choose an induced odd cycle \(O\) in \(G\) so that the following conditions hold: \[\label{eq:noxo} x \notin V(O).\tag{9}\] \[\label{eq:osh} E(O) \subseteq \partial E(H).\tag{10}\] \[\label{eq:cfc} G/V(O) \textrm{ is factor-critical}.\tag{11}\] The particular way we choose such \(O\) will be explained later. For ease of notation, we write \(G' = (V', E')\) for the contracted graph \(G/V(O)\), and denote the vertex formed in the contraction by \(v_O \in V'\).

We also define a \(3\)-uniform hypergraph \(H'\) on \(V'\). It coincides with \(H\) on \(V' \setminus \{v_O\}\), and the edges containing \(v_O\) are those \(\{u_1, u_2, v_O\}\) satisfying:

• \(V(O) \cup \{u_1, u_2\}\) is \(G!H\) coverable.

• \(\{ u_1, u_2, v_O\}\) contains at least two edges of \(G'\).

Suppose for the moment that \(V'\), \(G'_<\) (with a suitable order \(<\) on \(E'\)), \(H'\), and \(x \in V'\) satisfy the assumptions of Lemma 6. Since \(|V'| < |V|\) (because the contraction collapses at least three vertices into one), the induction hypothesis provides a \(G'!H'\) cover of \(V'\). From it, we can construct a \(G!H\) cover of \(V\) as follows. If \(v_O\) belongs to the \(H'\) edge in the cover of \(V'\), we replace that edge \(u_1u_2v_O\) by a \(G!H\) cover of \(V(O) \cup \{u_1, u_2\}\). If \(v_O\) belongs to a \(G'\) edge in the cover of \(V'\), say \(uv_O\), we replace it by \(uv\) for some \(v \in V(O)\) and add a perfect matching in \(O - \{v\}\). In either case, \(V\) turns out to be \(G!H\) coverable and we are done.

Thus, it remains to indicate our choice of an induced odd cycle \(O\) in \(G\) so that (9 ), (10 ) and (11 ) are satisfied, and to verify that under this choice, with a suitable order on \(E'\), the assumptions of Lemma 6 hold for \(V'\), \(G'_<\), \(H'\), and \(x \in V'\). We start with verifying the assumptions, which for the most part depends only on (9 ), (10 ) and (11 ).

First, \(|V'| > 1\) because \(\{x, v_O\} \subseteq V'\). \(G'\) is factor-critical by (11 ), and \(H'\) is \(3\)-uniform by definition. The property that an edge of \(H'\) contains at least two edges of \(G'\) is inherited from the same property of \(H\) with respect to \(G\) when the edge of \(H'\) does not contain \(v_O\); and it is part of the definition of \(H'\) when the edge of \(H'\) contains \(v_O\).

For an edge \(e\) of \(G\) that is not contained in \(V(O)\), let us denote by \(e'\) the corresponding edge of \(G'\). That is, \(e' = e\) if \(e\) is disjoint from \(V(O)\), and \(e' = uv_O\) if \(e = uv\) for some \(u \notin V(O)\), \(v \in V(O)\).

Using the fact that \(e \in E(G)\) satisfies (\(\alpha\)), (\(\beta\)) or (\(\gamma\)) in the statement of the lemma, we would like to show that the same is true for \(e' \in E(G')\) with respect to \(H'\). Regarding condition (\(\alpha\)), this is immediate: \[\label{eq:con1} x \in e \,\,\Longrightarrow\,\, x \in e'.\tag{12}\] Indeed, by (9 ) \(x \notin V(O)\), so this follows from the definition of the contraction. For condition (\(\beta\)) the argument is more involved, and we start by showing the following: \[\label{eq:shad} e = uv,\, u \notin V(O),\, v \in V(O)\,\,\Longrightarrow\,\, e' \in \partial E(H').\tag{13}\] Note that for such \(e\), we assert that \(e'\) satisfies (\(\beta\)) regardless of whether or not \(e\) satisfies it. The proof is an application of Claim 14. First, we verify that \(G\), \(H\), and \(O\) satisfy all the assumptions of Claim 14. The only assumption that requires some checking is that \(V(O)\) is not \(G!H\) coverable. Suppose it is. Because \(G'\) is factor-critical by (11 ), we know that \(G - V(O)\) has a perfect matching \(M\). Adding \(M\) to a \(G!H\) cover of \(V(O)\) gives a \(G!H\) cover of \(V\), contradicting our assumption that \(V\) is not \(G!H\) coverable.

Thus we can apply Claim 14 with the given edge \(e = uv\) in the role of \(u_1v_1\). We get another edge \(u_2v_2 \in E(G)\) such that \(u_2 \notin V(O)\), \(v_2 \in V(O)\), \(u_2 \ne u_1\), and \(V(O) \cup \{u_1, u_2\}\) is \(G!H\) coverable. By the definition of \(H'\) we obtain that \(u_1u_2v_O \in E(H')\); indeed, the second requirement in the definition holds because both \(u_1v_O\) and \(u_2v_O\) are edges of \(G'\) obtained by contracting \(u_1v_1\) and \(u_2v_2\), respectively. Thus \(e' = uv_O\), being contained in \(u_1u_2v_O\) (recall that \(u = u_1\)), satisfies \(e' \in \partial E(H')\), which proves (13 ).

Next, we prove: \[\label{eq:con2} e \nsubseteq V(O),\, e \in \partial E(H)\,\,\Longrightarrow\,\, e' \in \partial E(H').\tag{14}\] In view of (13 ), it remains to prove this implication for edges \(e\) disjoint from \(V(O)\). Then we have \(e = u_1u_2\) with \(u_1, u_2 \notin V(O)\), and \(e' = e\). By assumption, there exists a vertex \(y \in V\) such that \(u_1u_2y \in E(H)\). If \(y \notin V(O)\) then \(u_1u_2y \in E(H')\) and we are done. If \(y \in V(O)\) then we claim that \(u_1u_2v_O \in E(H')\). Indeed, \(V(O) \cup \{u_1, u_2\}\) is \(G!H\) coverable, by taking \(u_1u_2y\) and a perfect matching in \(O - \{y\}\). Moreover, since \(u_1u_2y\) contains at least two edges of \(G\), \(u_1u_2v_O\) contains at least two edges of \(G'\). Thus, by the definition of \(H'\), \(u_1u_2v_O \in E(H')\). As it contains \(e' = u_1u_2\), this confirms that \(e' \in \partial E(H')\).

So far we have seen that if \(e\) satisfies condition (\(\alpha\)), respectively (\(\beta\)), then so does \(e'\). We leave condition (\(\gamma\)) for later, and proceed to handle Possibility 1. In this case, every edge of \(G\) satisfies (\(\alpha\)) or (\(\beta\)), so by the above every edge of \(G'\) satisfies (\(\alpha\)) or (\(\beta\)). Thus, the assumptions of Lemma 6 hold for \(V'\), \(G'_<\), \(H'\), and \(x \in V'\) regardless of the order \(<\) (which is only relevant to condition (\(\gamma\))). To complete the proof in this case, we just show that an induced odd cycle \(O\) in \(G\) can be chosen so that (9 ), (10 ) and (11 ) are satisfied.

By the assumption of Possibility 1, we can find a part \(U_i\) in the partition of \(V\) provided by Lemma 3 so that \(x \notin U_i\) and \(|U_i| > 1\). As \(G[U_i]\) is factor-critical, Lemma 2 guarantees the existence of an induced odd cycle \(O\) in \(G[U_i]\) such that \(G[U_i]/V(O)\) is factor-critical. We claim that such \(O\) satisfies (9 ), (10 ) and (11 ). Indeed, (9 ) holds by the choice of \(U_i\). Since every edge of \(G\) satisfies (\(\alpha\)) or (\(\beta\)), but the edges of \(O\) do not satisfy (\(\alpha\)), all of them satisfy (\(\beta\)) and (10 ) holds. To verify (11 ), it suffices to check that \(G/V(O)\) admits a partition as described in Lemma 3. Indeed, taking the partition \(U_1, U_2, \ldots , U_{2k+1}\) corresponding to \(G\) and replacing the \(U_i\) that contains \(V(O)\) by \(\bigl( U_i \setminus V(O) \bigr) \cup \{v_O\}\) yields such a partition for \(G/V(O)\). This completes the inductive proof of the lemma in the case when Possibility 1 holds.

From now on, we assume that Possibility 2 holds. Thus, there exists an edge \(e \in E(G)\) that satisfies only condition (\(\gamma\)) in the lemma. We denote by \(\bar{e}\) the first such edge according to the order \(<\) on \(E(G)\), and consider the Gallai-Edmonds decomposition of \(G^{(\bar{e})}\), namely \(D^{(\bar{e})} = D_1^{(\bar{e})} \cup D_2^{(\bar{e})} \cup \cdots \cup D_{r^{(\bar{e})}}^{(\bar{e})}\), \(A^{(\bar{e})}\), \(C^{(\bar{e})}\). By condition (\(\gamma\)), we know that \(|A^{(\bar{e})}| = r^{(\bar{e})} - 1 \ge 1\), and there is a component \(D_{j^{(\bar{e})}}^{(\bar{e})}\) such that \(|D_{j^{(\bar{e})}}^{(\bar{e})}| \ge 3\), \(x \notin D_{j^{(\bar{e})}}^{(\bar{e})}\), and \(\bar{e}\) has one endpoint in \(D_{j^{(\bar{e})}}^{(\bar{e})}\) and the other outside it.

We first prove: \[\label{eq:stay} \bar{e} \le e \,\,\Longrightarrow\,\, D_{j^{(\bar{e})}}^{(\bar{e})} \subseteq D_k^{(e)} \textrm{ for some } 1 \le k \le r^{(e)}.\tag{15}\] Indeed, as \(|A^{(\bar{e})}| = r^{(\bar{e})} - 1\), for every vertex in \(D^{(\bar{e})}\) there is a near-perfect matching in \(G^{(\bar{e})}\), hence also in \(G^{(e)}\), avoiding that vertex. This implies that \(D^{(\bar{e})} \subseteq D^{(e)}\), and because vertices in the same component of \(D^{(\bar{e})}\) are still connected in \(G^{(e)}\), they must lie in the same component of \(D^{(e)}\), proving (15 ).

As \(G^{(\bar{e})}[D_{j^{(\bar{e})}}^{(\bar{e})}]\) is factor-critical, we can find by Lemma 2 an induced odd cycle \(\bar{O}\) in it such that \(G^{(\bar{e})}[D_{j^{(\bar{e})}}^{(\bar{e})}]/V(\bar{O})\) is factor-critical. Note that \(\bar{O}\) is induced in \(G^{(\bar{e})}\) but is not necessarily induced in \(G\). If it is, we take \(O = \bar{O}\) in our proof. If it is not, then using Lemma 1, we take \(O\) to be an odd shortening of \(\bar{O}\) which is induced in \(G\). We proceed to verify that \(O\) has the required properties.

Since \(x \notin D_{j^{(\bar{e})}}^{(\bar{e})}\), (9 ) holds. To check (10 ), we note that the edges of \(O\) are either edges of \(\bar{O}\) or chords of \(\bar{O}\). In the former case, as \(\bar{O}\) lies in \(G^{(\bar{e})}\), they must satisfy (\(\alpha\)) or (\(\beta\)) by the minimality of \(\bar{e}\). But (\(\alpha\)) is already excluded, so these edges satisfy (\(\beta\)): they are in \(\partial E(H)\). In the latter case, if \(e\) is a chord of \(\bar{O}\) then \(e \in E(G) \setminus E(G^{(\bar{e})})\), hence \(\bar{e} \le e\). It follows from (15 ) that \(e \subseteq D_k^{(e)}\) for some \(1 \le k \le r^{(e)}\). Thus \(e\) does not satisfy condition (\(\gamma\)), and because (\(\alpha\)) is excluded, we deduce that \(e\) satisfies (\(\beta\)). This concludes the verification of (10 ).

In order to check (11 ), we first show: \[\label{eq:pm} G^{(\bar{e})}[D_{j^{(\bar{e})}}^{(\bar{e})} \setminus V(O)] \textrm{ has a perfect matching}.\tag{16}\] Indeed, because \(G^{(\bar{e})}[D_{j^{(\bar{e})}}^{(\bar{e})}]/V(\bar{O})\) is factor-critical, there is a perfect matching of \(D_{j^{(\bar{e})}}^{(\bar{e})} \setminus V(\bar{O})\) in \(G^{(\bar{e})}\). If \(O = \bar{O}\) this is exactly what we need. If \(O\) is an odd shortening of \(\bar{O}\) formed upon replacing the odd paths \(Q_1, Q_2, \ldots , Q_{\ell}\) by chords, we just need to add perfect matchings of the internal vertices of these odd paths. This proves (16 ).

To verify (11 ), it suffices by Lemma 4 to show that \(G - V(O)\) has a perfect matching. We show that already \(G^{(\bar{e})} - V(O)\) has one, and do this in two parts: \(V \setminus D_{j^{(\bar{e})}}^{(\bar{e})}\) has a perfect matching in \(G^{(\bar{e})}\) due to the Gallai-Edmonds decomposition having \(|A^{(\bar{e})}| = r^{(\bar{e})} - 1\), and \(D_{j^{(\bar{e})}}^{(\bar{e})} \setminus V(O)\) has a perfect matching in \(G^{(\bar{e})}\) by (16 ). This completes the proof that \(O\) satisfies (9 ), (10 ) and (11 ).

We now define an order on \(E' = E\bigl(G/V(O)\bigr)\). For this purpose, we write each edge in \(E'\) as \(e'\), where \(e\) is the first edge of \(G\) whose contraction gives this \(e'\). We use the given order on \(E(G)\) to order \(E'\): \[e'_1 < e'_2\,\, \Longleftrightarrow\,\,e_1 < e_2.\] Note that under this definition of the order on \(E'\), contraction and taking the subgraph of preceding edges commute: \(G'^{(e')} = G^{(e)}/V(O)\).

It remains to complete the verification that the assumptions of the lemma hold for \(V'\), \(G'_<\), \(H'\), and \(x \in V'\); this will allow the inductive argument to take care of Possibility 2. Every edge \(e\) of \(G\) is known to satisfy (\(\alpha\)), (\(\beta\)) or (\(\gamma\)), and we have already shown in (12 ) and (14 ) that if it satisfies (\(\alpha\)) or (\(\beta\)) then so does \(e'\). Thus, we may assume that \(e \in E(G)\) satisfies only condition (\(\gamma\)). By the choice of \(\bar{e}\), we have \(\bar{e} \le e\). If \(e\) has one vertex in \(V(O)\) and the other outside it, then by (13 ) \(e'\) satisfies (\(\beta\)). Thus, we may assume that \(e \cap V(O) = \emptyset\) and therefore \(e' = e\).

We will show that in this case \(e'\) satisfies (\(\gamma\)). For this we need to describe the Gallai-Edmonds decomposition of \(G'^{(e')} = G^{(e)}/V(O)\). As \(\bar{e} \le e\), we know from (15 ) that \(V(O) \subseteq D_{j^{(\bar{e})}}^{(\bar{e})} \subseteq D_k^{(e)}\) for some \(1 \le k \le r^{(e)}\). We claim that the Gallai-Edmonds decomposition of \(G^{(e)}/V(O)\) is obtained from that of \(G^{(e)}\) upon replacing \(D_k^{(e)}\) by \(\bigl( D_k^{(e)} \setminus V(O)\bigr) \cup \{v_O\}\). To check this, we only need to verify that \(G^{(e)}[D_k^{(e)}]/V(O)\) is factor-critical (the other structural requirements are not affected by the contraction). As \(G^{(e)}[D_k^{(e)}]\) is factor-critical, by Lemma 4 it suffices to show that \(D_k^{(e)} \setminus V(O)\) has a perfect matching in \(G^{(e)}\). In fact, we show below that it has a perfect matching already in \(G^{(\bar{e})}\), which is a subgraph of \(G^{(e)}\).

Indeed, let \(M\) be a near-perfect matching in \(G^{(\bar{e})}\) that misses a vertex \(v \in D_{j^{(\bar{e})}}^{(\bar{e})}\). By Corollary 5, \(M\) has a subset \(M'\) with \(\bigcup M' = D_{j^{(\bar{e})}}^{(\bar{e})} \setminus \{v\}\). Another application of this corollary, when viewing \(M\) as a near-perfect matching in \(G^{(e)}\), shows that \(M\) has a subset \(M''\) with \(\bigcup M'' = D_k^{(e)} \setminus \{v\}\). Thus \(\bigcup (M'' \setminus M') = D_k^{(e)} \setminus D_{j^{(\bar{e})}}^{(\bar{e})}\). Adding to \(M'' \setminus M'\) a perfect matching in \(G^{(\bar{e})}[D_{j^{(\bar{e})}}^{(\bar{e})} \setminus V(O)]\) which exists by (16 ), we obtain a perfect matching of \(D_k^{(e)} \setminus V(O)\) in \(G^{(\bar{e})}\), as promised. This confirms that \(G^{(e)}[D_k^{(e)}]/V(O)\) is factor-critical, and therefore the Gallai-Edmonds decomposition of \(G'^{(e')}\) is as described above.

We know that \(e\) satisfies condition (\(\gamma\)) with respect to the decomposition of \(G^{(e)}\), and \(e' = e\). In order to verify that \(e'\) satisfies (\(\gamma\)) with respect to the decomposition of \(G'^{(e')}\), we only need to check that after contracting \(D_k^{(e)}\) to \(\bigl( D_k^{(e)} \setminus V(O)\bigr) \cup \{v_O\}\), the \(j(e)\) component still has more than one vertex. If \(j(e) \ne k\) there is nothing to prove. If \(j(e) = k\) then, after contraction, this component still contains one vertex of \(e\) (which is disjoint from \(V(O)\)), as well as \(v_O\). So indeed \(e'\) satisfies condition (\(\gamma\)).

This completes the argument that under Possibility 2, every edge in \(E(G')\) satisfies (\(\alpha\)), (\(\beta\)) or (\(\gamma\)). Thus, the inductive proof of the lemma works for both possibilities. This ends the proof of Lemma 6, hence also of Proposition 6 and Theorem 2. 0◻

4 A Gale-Shapley type theorem for triples↩︎

The well-known stable matching theorem of Gale and Shapley [13] can be formulated in terms of bipartite graphs as follows. Consider a bipartite graph \(G = (V, E)\), where every vertex \(v\) has a linear order \(\succeq_v\) on the set \(E_v\) of edges incident to \(v\). Here \(vx \succeq_v vy\) means that \(v\) prefers to be matched to \(x\) than to \(y\) (or \(x=y\)). A matching \(M\) in \(G\) dominates an edge \(e = uv \in E\) if either \(u\) or \(v\) has an edge incident to it in \(M\) that it weakly prefers to \(e\). A matching is stable if it dominates every edge in \(E\). The stable matching theorem says that every bipartite graph, with any system of preferences as above, has a stable matching. This theorem and related ones have been much studied and widely applied in practice, e.g., to job markets, school assignments, and matching of organ donors to patients.

One direction of study is to allow the sets that can be formed (the edges) to be larger, not just couples. This is modeled by a hypergraph \(H = (V, E)\) and a preference system \(\bigl( \succeq_v\bigr)_{v \in V}\), where each \(\succeq_v\) is a linear order on \(E_v\), the set of edges in \(E\) that contain \(v\). A set of edges \(\{e_1, e_2, \ldots , e_m\} \subseteq E\) dominates an edge \(e \in E\) at a vertex \(v \in e\) if for some \(1 \le i \le m\) we have \(v \in e_i\) and \(e_i \succeq_v e\). We say that \(\{e_1, e_2, \ldots , e_m\}\) is stable if it dominates every edge \(e \in E\) at some \(v \in e\).

When \(H\) is a bipartite graph, this coincides with the standard model described above, and a stable matching is guaranteed to exist. Beyond bipartite graphs, however, this is no longer true. Simple examples without a stable matching are known already for non-bipartite graphs (“the roommates problem" [13]) and for \(3\)-partite hypergraphs (”threesome matchings" [14]).

One way to regain existence is to relax the notion of matching to its fractional version. A fractional matching in \(H = (V, E)\) is a function \(f: E \to \mathbb{R}_+\) that satisfies \(\sum_{e \ni v} f(e) \le 1\) for every vertex \(v \in V\). Note that these inequalities are opposite to those required for a fractional edge cover. We say that a vertex \(v\) is saturated by \(f\) if \(\sum_{e \ni v} f(e) = 1\). Given a preference system for \(H\), a fractional matching \(f\) in \(H\) dominates an edge \(e \in E\) at a vertex \(v \in e\) if \[\sum \{ f(e'): e' \in E_v, e' \succeq_v e\} = 1.\] Observe that this requires \(v\) to be saturated by \(f\), and all edges \(e' \in E_v\) with \(f(e') > 0\) to be weakly preferred to \(e\) by \(v\). We say that \(f\) is stable if it dominates every edge \(e \in E\) at some \(v \in e\). Note that if \(f\) is \(\{0,1\}\)-valued, this means that the \(1\)-valued edges form a stable matching. The following theorem of Aharoni and Fleiner [15] guarantees the existence of a stable fractional matching (in the special case of graphs, this is implicit in an earlier result of Tan [16]).

Here we propose another relaxation of the notion of stable matching. Instead of looking at matchings, we consider arbitrary sets of edges, and want to guarantee the existence of a stable one whose size is small (in terms of the number of vertices and the edge size). We will obtain such a result for \(3\)-uniform hypergraphs by combining Theorem 15 and Corollary 1.

More precisely, we need a slight generalization of Corollary 1, which may be of independent interest. In the corollary, we assumed the existence of an exact fractional edge cover, which is the same as a fractional matching which saturates all the vertices. The following proposition is an adaptation of the corollary that handles fractional matchings which may not saturate all the vertices.

We are now ready to state and prove the main result of this section.

The following example shows that Theorem 17 is sharp.

We remark that the analog of Theorem 17 for graphs holds with the sharp bound \(m \le \frac{2}{3}|V|\). This can be deduced quite easily from Tan [16]. We omit the details.

Acknowledgments↩︎

We are grateful to Ron Aharoni and He Guo for helpful discussions and correspondence.

References↩︎

---

1. University of Haifa, berger@math.haifa.ac.il↩︎

2. Technion–Israel Institute of Technology, holzman@technion.ac.il↩︎