Given a perfect fractional matching, does there exist a perfect matching with heavy edges?

Question

Let $G = (X\cup Y, E)$ be a bipartite graph in which $|X|=|Y|=n$. Suppose $G$ admits a perfect fractional matching, that is - a function assigning a non-negative weight to each edge, such that the sum of weights of edges near each vertex is exactly $1$.

It is known that such a $G$ always admits a perfect matching. One way to prove it is using Hall's marriage theorem: for each subset of $k$ vertices of $X$, the sum of weight near these vertices is $k$, so they must be adjacent to at least $k$ vertices of $Y$. Thus $G$ satisfies Hall's condition.

What is the largest $r(n)$ such that $G$ always admits a perfect matching in which the weight of every edge is at least $r(n)$?

An upper bound on $r(n)$ is $1/n$. It is given by the complete biartite graph and the fractional matching in which the weight of each edge is $1/n$.

A lower bound on $r(n)$ is $1/n(n-1)$. Proof: remove from $G$ all edges with a weight of less than $1/n(n-1)$. For each vertex $v$, we removed at most $n-1$ edges adjacent to $v$ (since at least one edge must remain). Hence, the weight near $v$ decreased by less than $1/n$, and the remaining weight is more than $1-1/n$. The weight near each subset of $k$ vertices of $X$ is now more than $k-k/n > k-1$, so again they must be adjacent to at least $k$ vertices of $Y$. Thus, the graph remaining after the removal still satisfies Hall's marriage condition.

What are better bounds for $r(n)$?

Answer 1

Interesting question. If I understand your definitions correctly, this fractional matching in $K_{3,3}$ should show that $r(3) \leq 1/4$. Here, heavy edges have weight $1/2$ in the fractional matching, while light edges have weight $1/4$:

Clearly there is no perfect matching that uses only the heavy edges, so a perfect matching must use edges of weight $1/4$. I haven't thought much more about it, but maybe this example can be generalized to higher $n$ to improve the upper bound.

---

Trying to keep the constructions in this answer and the computational evidence in the other answer, I think we can generalize this answer to get the upper bound $r(n) \leq 1/\left(\lfloor\frac{n+1}{2}\rfloor\lceil\frac{n+1}{2}\rceil\right)$, which the other answer suggests is probably the right value. When $n$ is even, say $n=2p$, we use the following fractional matching of $K_{n,n}$:

(Here, the boxes represent vertex sets of the given sizes, and the labels on the edges joining the boxes indicate the weights on all edges between those sets.) I believe it should be easy to verify that this a fractional matching, that $1/(p(p+1)) = 1/\left(\lfloor\frac{n+1}{2}\rfloor\lceil\frac{n+1}{2}\rceil\right)$ is the smallest of the nonzero weights, and that there is no perfect matching using only the blue and green edges.

When $n$ is odd, say $n = 2p+1$, I believe a similar construction also works:

I think it should be possible to prove a matching lower bound using LP duality: prior to choosing the values of the $x_{ij}$ variables, the only real choice to make in a vertex cover for the high-weight edges is how many vertices can be used in each part; once that's fixed, all remaining variables are continuous variables, and LP duality should be able to prove that no example with a smaller value of $r$ is possible for the fixed choice of vertex cover. Then it's just a matter of finding a good systematic way to generate dual solutions given the number of vertices of each part in the cover. I haven't thought much about that, but it seems doable.

Answer 2

OK, here's a more complete answer. A nice feature of this problem is that, using the Kőnig--Egerváry theorem, it can be naturally represented as a mixed integer linear program.

The main idea is: to enforce the constraint that there should be no perfect matching using only the edges of weight $> r$, we instead seek a size-$(n-1)$ vertex cover of just those edges. Kőnig--Egerváry guarantees that such a vertex cover exists if and only if there is no matching. Now we can express the problem as finding a fractional perfect matching $x$, a threshold $r$ as small as possible, and the size-$(n-1)$ vertex cover, represented by the integer variables $c_i$ for one partite set and $d_j$ for the other set:

minimize $r$

subject to:

$\sum_j x_{ij} = 1 \quad \forall i = 1, \ldots, n$,

$\sum_i x_{ij} = 1 \quad \forall j = 1, \ldots, n$,

$r - x_{ij} + c_i + d_j \geq 0 \quad \forall i,j$,

$\sum c_i + \sum d_j \leq n-1$,

$0 \leq x_{ij} \leq 1 \quad \forall i,j$,

$c_i \in \{0,1\} \quad \forall i$,

$d_j \in \{0,1\} \quad \forall j$.

Solving this MILP for small values of $n$ on my laptop gave the following (approximate) values, which support the conjecture that $r(n) = 1/\left(\lfloor \frac{n+1}{2}\rfloor\lceil\frac{n+1}{2}\rceil\right)$:

n=2 gives r=0.500000, conjectured value 1/2 = 0.500000
n=3 gives r=0.249999, conjectured value 1/4 = 0.250000
n=4 gives r=0.166666, conjectured value 1/6 = 0.166667
n=5 gives r=0.111111, conjectured value 1/9 = 0.111111
n=6 gives r=0.083333, conjectured value 1/12 = 0.083333
n=7 gives r=0.062500, conjectured value 1/16 = 0.062500
n=8 gives r=0.050000, conjectured value 1/20 = 0.050000
n=9 gives r=0.040000, conjectured value 1/25 = 0.040000
n=10 gives r=0.033333, conjectured value 1/30 = 0.033333
n=11 gives r=0.027778, conjectured value 1/36 = 0.027778
n=12 gives r=0.023809, conjectured value 1/42 = 0.023810
n=13 gives r=0.020408, conjectured value 1/49 = 0.020408
n=14 gives r=0.017857, conjectured value 1/56 = 0.017857
n=15 gives r=0.015625, conjectured value 1/64 = 0.015625
n=16 gives r=0.013889, conjectured value 1/72 = 0.013889
n=17 gives r=0.012345, conjectured value 1/81 = 0.012346
n=18 gives r=0.011111, conjectured value 1/90 = 0.011111
n=19 gives r=0.010000, conjectured value 1/100 = 0.010000

Answer 3

Here is an attempt to formally prove the conjecture of @GregoryJPuleo, namely:

$$r(n) = 1/\left(\lfloor \frac{n+1}{2}\rfloor\lceil\frac{n+1}{2}\rceil\right).$$

We remove from the graph all edges with a weight of less than $r$, and prove that the remaining graph satisfies Hall's marriage condition.

The proof is by contradiction. Let $X_k$ be a subset of $k$ vertices of $X$. Suppose that, after the removal, its set of neighbors is $Y_\ell$ and it contains $\ell\leq k-1$ vertices of $Y$. Before the removal, the sum of weights near $X_k$ was exactly $k$, and each vertex of $X_k$ had at most $n$ adjacent edges. For each vertex of $X_k$, we had removed at most $n-\ell$ edges to vertices outside $Y_\ell$, and the weight of each such edge is less than $r$; therefore the weight difference between $X_k$ and $Y_\ell$ decreased by less than $k\cdot (n-\ell)\cdot r \leq k\cdot (n-k+1)\cdot r $.

Consider the product $k\cdot (n-k+1)$ as $k$ ranges between $1$ and $n$. It is a product of two integers with a fixed sum $(n+1)$, therefore it is maximized when the two factors are equal up to at most $1$, i.e., when $k = \lfloor \frac{n+1}{2}\rfloor$. Therefore the decrease in weight near $X_k$ is strictly less than

$$\lfloor \frac{n+1}{2}\rfloor \cdot \lceil \frac{n+1}{2}\rceil \cdot r(n) = 1$$

Therefore, the total weight near $X_k$ is strictly more than $k-1$. But this means that $X_k$ must have at least $k$ neighbors in $Y$ - a contradiction.