Skip to main content
Add proof for the case n=2
Source Link

I managed to prove theThe theorem is true for $n=2$ using a simple case-analysis. My

Proof. Denote the parts of the hypergraph by $X = \{x_1,x_2\}, Y = \{y_1,y_2\}, Z = \{z_1,z_2,z_3\}$. The sum near $x_1$ is 1/2, so the sum near either $(x_1,y_1)$ or $(x_1,y_2)$ or both must be at least 1/4; w.l.o.g. assume the sum near $(x_1,y_1)$ is at least 1/4. Similarly, the sum near $x_2$ is 1/2. The sum near $(x_2,y_1)$ is at most $1/4$, so the sum near $(x_2,y_2)$ must be at least 1/4. Now $H$ can be reduced into a bipartite graph: one side contains the two vertices $x_1 y_1$ and $x_2 y_2$, and the other size is $Z$. Each of $x_1 y_1$ and $x_2 y_2$ has at least one neighbor in $Z$ - since the weight near them is positive. Moreover, both vertices together must have at least two neighbors in $Z$ - since the total weight near them is 1/2 which is larger than 1/3. Therefore, by Hall's marriage theorem there is a matching of size $2$ in the reduced graph. It corresponds to a matching of size $2$ in the original hypergraph.

However, so far, my attempts to extend it to any $n$ failed:

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

The theorem is true for $n=2$.

Proof. Denote the parts of the hypergraph by $X = \{x_1,x_2\}, Y = \{y_1,y_2\}, Z = \{z_1,z_2,z_3\}$. The sum near $x_1$ is 1/2, so the sum near either $(x_1,y_1)$ or $(x_1,y_2)$ or both must be at least 1/4; w.l.o.g. assume the sum near $(x_1,y_1)$ is at least 1/4. Similarly, the sum near $x_2$ is 1/2. The sum near $(x_2,y_1)$ is at most $1/4$, so the sum near $(x_2,y_2)$ must be at least 1/4. Now $H$ can be reduced into a bipartite graph: one side contains the two vertices $x_1 y_1$ and $x_2 y_2$, and the other size is $Z$. Each of $x_1 y_1$ and $x_2 y_2$ has at least one neighbor in $Z$ - since the weight near them is positive. Moreover, both vertices together must have at least two neighbors in $Z$ - since the total weight near them is 1/2 which is larger than 1/3. Therefore, by Hall's marriage theorem there is a matching of size $2$ in the reduced graph. It corresponds to a matching of size $2$ in the original hypergraph.

However, so far, my attempts to extend it to any $n$ failed:

added 1 character in body
Source Link

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.

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.

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.

Source Link

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.