Skip to main content
2 of 3
added 1 character in body

From fractional matching to integral matching in tripartite hypergraphs

Let $G = (X\cup Y, E)$ by a bipartite graph with $n = |X|\leq |Y|$. A fractional matching is a function assigning a non-negative weight to every edge in $E$, such that the sum of weights near each vertex is at most $1$. A symmetric fractional matching is a matching in which the total weight near every vertex of $X$ is the same (denote it by $w_X$) and the total weight near every vertex of $Y$ is the same (denote it by $w_Y$; note that $w_Y\leq w_X$).

Suppose that $G$ admits a symmetric fractional matching in which $w_X = 1$. Then $G$ admits an $X$-perfect matching (a matching in which all vertices of $X$ are matched). Two ways to see this are:

  1. It is well-known that, in bipartite graphs, the maximum matching size (denoted $\nu(G)$) equals the maximum fractional matching size (denoted $\nu^*(G)$). Here we have $\nu^*(G)=|X|\cdot w_X = n$, which implies $\nu(G)=n$.
  2. For every subset $X_k \subseteq X$ of size $k$, the sum of weights near vertices of $X_k$ is $k\cdot w_X = k$; for each subset $Y_k \subseteq Y$ of size $k$, the sum of weights near vertices of $Y_k$ is $k\cdot w_Y\leq k$. Hence, each such $X_k$ must have at least $k$ neighbors in $Y$. Hall's marriage theorem implies that an $X$-perfect matching exists.

I am looking for conditions under which this theorem holds for tripartite hypergrpahs. Let $H = (X\cup Y \cup Z, E)$ by a 3-partite hypergraph with $n = |X|\leq |Y|\leq |Z|$. Suppose that $H$ admits a fractional matching in which $w_X = 1$. The following example shows that $H$ need not have an $X$-perfect matching. Consider an hypergraph with the following edges:

$(x_1,y_1,z_1), (x_1,y_2,z_2), (x_2,y_2,z_1), (x_2,y_1,z_2)$

The fractional matching assigning a weight of $1/2$ to all edges is symmetric and has $w_X=w_Y=w_Z=1$. However, $H$ does not admit an $X$-perfect matching.

I would like to know whether this can be "fixed" by enlarging $Z$. In particular, I will be happy to prove the following theorem:

Wanted-Theorem 1. If $|X|=|Y|=n$ and $|Z|\geq 2n-1$, and $H$ admits a symmetric fractional matching with $w_X=w_Y=1$ (and $w_Z=n/(2n-1)$), then $H$ admits an $X$-perfect matching.

I managed to prove the theorem for $n=2$ using a simple case-analysis. My attempts to extend it to any $n$ failed:

  1. I first looked for an extension of the fact $\nu(H)=\nu^*(H)$ from bipartite graphs to tripartite hypergraphs. Indeed I found one by Füredi (1981): he proves that, in an $r$-partite graph, $\nu(H) \geq \nu^*(H)/(r-1)$. In particular, in tripartite hypergraphs $\nu(H) \geq \nu^*(H)/2$. But this is insufficient for the wanted theorem. Füredi shows that the factor $r-1$ is tight, but his example uses a hypergraph in which $|X|=|Y|=|Z|$, so hope is not lost yet.

  2. I also looked at various Hall-type theorems for hypergraphs, but I could not prove that the conditions of Wanted-Theorem 1 imply the sufficient conditions for any of them.

Any more ideas about how I can prove or disprove this? References to papers relating fractional matching to integral matching in hypergraphs are also welcome.