A combinatorics problem about perfect pairings

Question

While doing some problems in geometry I came with the following problem that can be stated in a purely combinatorial way:

Suppose we have a finite set $X$ partitioned into some (nonempty) subsets $A_1, \ldots , A_s$. A matching in $X$ is a way of grouping the elements of $X$ two by two (only allowing one element to not be matched to any other, in case $X$ has odd cardinality) such that if $x$ is matched to $y$ they cannot be in the same $A_j$.

My problem is stated as follows:

If $s \geq 3$, and the sum of the cardinalities of the two biggest $A_j$ is less than or equal to the sum of the rest, prove that there exists some $i$ such that $X \smallsetminus A_i$ has a matching (relative to the partition given by the $A_j$ for $j \neq i$).

I was wondering if there are similar problems in combinatorics, specially since the condition on the sum of the cardinalities of the biggest $A_j$ could be sharper (it comes from my problem in geometry); and if one can use some machinery to attack them, since I could not find anything similar browsing.

I have attempted a proof of it, which will be posted as a separate answer, but I am looking for other ways of proving it or of similar problems.

Answer 1

My solution is as follows: Suppose $X$ has cardinality $n$ and is partitioned by $A_1, A_2, \ldots , A_s$, ordered in decreasing cardinality. I claim that

$X$ has a matching if and only if $s \geq 2$ and $|A_1| \leq \lceil \frac{n}{2}\rceil$ (and therefore $|A_j| \leq \lceil \frac{n}{2}\rceil$ for all $j$).

Proof: The only if part is clear. For the if, I prove it by induction. If $n=2 , 3$ then this is clear. For general $n>3$, pair an element of $A_1$ with an element of $A_2$ and then remove these two points from the set. Our new $X$ will have cardinality $n-2$, and the new sets $A_1, A_2$ will have decreased in cardinality by $1$, and therefore they satisfy the inductive hypothesis. It only remains to check that $|A_3|\leq\lceil \frac{n}{2}\rceil-1$ but the other possibility is that $|A_3| = \lceil \frac{n}{2}\rceil$, which is impossible because then $$ n =|X| \geq |A_1|+|A_2|+|A_3| \geq 3\left\lceil \frac{n}{2}\right\rceil>n$$ a contradiction.

Now come to the main problem. We have $|A_3|+ \ldots + |A_s| \geq |A_1|+|A_2|$. Therefore, if we remove $|A_1|$, the biggest possible subset will be $A_2$ but $|A_2|<|A_3|+ \ldots + |A_s|$ so its cardinality cannot be more than the half.