A Simple Condition for the Existence of Transversals

Publication date 16 February 2016

Abstract: Hall's Theorem is a basic result in Combinatorics which states that the obvious necesssary condition for a finite family of sets to have a transversal is also sufficient. We present a sufficient (but not necessary) condition on the sizes of the sets in the family and the sizes of their intersections so that a transversal exists. Using this, we prove that in a bipartite graph

G

(bipartition

A, B

), without 4-cycles, if

d e g (v) g e q s q r t 2 e | A |

for all

v i n A

, then

G

has a matching of size

| A |

.

This page was built for publication: A Simple Condition for the Existence of Transversals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6270548)