Hall's marriage theorem

A matching saturating the left side exists exactly when every subset \(S\) satisfies \(|N(S)| \ge |S|\). Checked exhaustively and cross-checked against the matching. When it fails the VIOLATING SET is returned: Hall's theorem is most useful as a certificate of impossibility, and a bare FALSE is not one.

Usage

morie_hall_condition(left_n, right_n, edges)

Arguments

left_n, right_n

Side sizes.

edges

List of (left, right) pairs, numbered from 1.

Value

A list with holds, violating_set, deficiency, matching_size, agrees_with_matching, warnings.

References

Hall P (1935) J London Math Soc 10:26-30.

Examples

morie_hall_condition(3, 2, list(c(1, 1), c(2, 1), c(3, 2)))
#> $holds
#> [1] FALSE
#> 
#> $violating_set
#> [1] 1 2
#> 
#> $deficiency
#> [1] 1
#> 
#> $matching_size
#> [1] 2
#> 
#> $perfect_on_left
#> [1] FALSE
#> 
#> $agrees_with_matching
#> [1] TRUE
#> 
#> $n
#> [1] 5
#> 
#> $warnings
#> character(0)
#> 
#> $method
#> [1] "Hall's marriage theorem (Hall 1935)"
#>