4
$\begingroup$

The following is classical theorem of Ore and Ryser, generalising famous Hall marriage theorem.

Assume that $n$ guys and $m$ girls live in a town, some guys like some girls. Three statements are equivalent:

(i) each guy may get one wife and one mistress (they do differ, but he should like both) so that all wifes are different and all mistresses are also different.

(ii) after removing any $k$ edges ($k=1,2,\dots$) in corresponding bipartite graph, at least $n-k/2$ guys may get wifes.

(iii) for each $k$ guys, (number of girls liked by at least one of them) plus (number of girls liked by at least two of them) is not less then $2k$.

It is easy to see that (ii) and (iii) are equivalent, and (i) implies both, so the interesting part is that (ii) implies (i).

One may look at this problem as follows. Consider the set $E$ of edges of our graph, call its subset independent, if no two edges of the subset have common endpoint. This is independence system, call it $M$, and its rank function $\rho$. Then consider new independent system $M\cup M$, in which independent set is a union of two sets, independent in $M$. Then (i) means that rank of $M\cup M$ equals $2n$ (it obviously can not be more), and (ii) means that

$$ 2 \rho(E\setminus A)+|A|\geq 2n $$

for any $A\subset E$. If $M$ was matroid, it would finish the proof by matroid union rank formula, but alas $M$ is (in general) not a matroid, but it is intersection of two matroids, one of them corresponds to "independent set of edges is the set of edges with different guys-endpoints", and another one to "independent set of edges is the set of edges with different girls-endpoints". Also, projection of $M$ onto guys and onto girls are ("transversal") matroids.

Now finally the question. Is there any general weaker, then being a matroid, condition on independence system, which is enjoyed by our $M$, and which shares the matroid union rank formula?

$\endgroup$

1 Answer 1

2
$\begingroup$

The concept of "strongly base orderable" matroids seems to fit the bill, see for example

http://lemon.cs.elte.hu/egres/open/Base_orderable_matroid

In particular, partition matroids are strongly base orderable and a "union of intersections" theorem was proven by Davies and McDiarmid.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.