Chapter 4: halls marriage theorem

Question 1

EXAMPLE: in a group of 7 men and 6 women

woman 1 knows men 1',2',3'
woman 2 knows men 2',3'
woman 3 knows men3',5',7'
woman 4 knows men1',2'
woman 5 knows men1',2',3'
woman 6 knows men 4',5',6'

can each find a husband from the man she knows?

Answer 1

this is impossible

e.g women 1,2,4 and 5 only know 3 Men between them (1’,2’,3’) so they can’t get married to different men they know

relates to LEMMA: for plausibility and full matching

ie iff for each subset of r women they know at least r men between them

Question 2

consider a job allocation problem
finite set of jobs and finite set of people

corresponds to counting rook polynomials

Answer 2

Finite set j of jobs
Finite set P of people
For each j ∈J, a subset C[j]⊆P of candidates = those qualified for job

corresponds to board with rows labelled J and columns labelled P with (j,p) is unblocked iff p∈C[j]

Given subset U ⊆J: a partial matching on U gives injective map m:U→ P with m(j)∈C[j] for all j

• m(j)∈C[j] means we assign j to person m(j) who is qualified to do j
• injective means we do not assign 2 different jobs to the same person

*rook polynomials to see if there is at least a full matching
a full matching is one such that map m with U=all J

Question 3

C[U] in job allocation

Answer 3

C[U]= ∪_{j∈U} C[j]

e.g. C[ {i,j,l}] = C[j] ∪C[k] ∪C[l]

C[U]={people qualified to do at least one of the jobs in U}

Question 4

A full matching for u, set of jobs PLAUSIBILITY definition

Answer 4

u is
*implausible if |C[u]| is LESS THAN |u|
barely plausible if |C[u]| = |u|
Very plausible if |C[u]| is MORE THAN |u|

*plausible if |C[u]| ≥ |u|

(so plausible if barely plausible or very plausible)

Question 5

LEMMA: for plausibility and full matching

Answer 5

if there is a full matching m: U→ P then every subset U ⊆J is plausible

proof: Suppose U={j_1,…,j_r}. Then m(j_i) ∈C[j_i] ⊆C[u] for all i, and m(j_1),..,m(j_r) are all different as m is injective, thus |C[u]| ≥ |u|

Question 6

COROLLARY:for plausibility and full matching

Answer 6

if there are any impossible/implausible sets, then the problem is not solvable

Question 7

EXAMPLE: is the problem solvable
                Pa Qui Ru Ste Tess
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
Artist       |x     x     
Baker      |       x   x             x
Courrier  |x     x
Dentist    |x     x   x      x     x
Electr''     |x     x

x means qualified

Answer 7

C[{A}]={P,Q} so {A} is very plausible

C[{B,D}]={P,Q,R,S,T} so {A} is very plausible

(candidates able to do at least one of the jobs)

C[{A,C}]={P,Q} so {A,C} is barely plausible

C[{A,C,E}]={P,Q} so {A,C,E} is implausible

thus the problem is not solvable

we only need to find one example such that it’s implausible (try out different jobs)

Question 8

halls marriage theorem

Answer 8

is every set of jobs is plausible then there exists a full matching

(converse of lemma)

if there is a full matching m: U→ P then every subset U ⊆J is plausible

• marriage version iff for every set of size r must have at least r men known
• proof by induction for number of jobs

Question 9

NEW ASSIGNMENT FROM PART ASSIGNMENT EXAMPLE

4 jobs and 4 people assigned

j_0 has not been assigned (to a person)
p_0 is qualified for j_0 but has already been assigned to j_1

p_1 is qualified for j_1 but has already been assigned to j_2

p_2 is qualified for j_2 but has already been assigned to j_3

p_3 is qualified for j_3 AND has NOT been given a job

Answer 9

by forming open zigzag

we have already
j_0-----------p_0
            /
j_1------------p_1
           /
j_2-----------p_2
          /
j_3-----------p_3

(/ mark arrows of solid line: person is assigned and qualified)

dotted line:person is qualified

new assignment:

j_0________>p_0

j_1________>p_1

j_2________>p_2

j_3________>p_3

Question 10

OPEN ZIGZAG

Answer 10

a sequence like prev example (j_0,..,j_n; p_0,..,p_n) where p_n has not been assigned a job is called an open zigzag. changing the assignment (as before) is called flipping

if we can find an open zig zag then we can flip it,which modifies and extends m (So It covers j as well as j)

Question 11

IS THERE ALWAYS AN OPEN ZIGZAG?

Answer 11

if we have a possible job allocation problem, a partial solution
m_1: J_1 → P
and an extra job
j_0 ∈ J\J_1
then we can always find an open zig zag and flip it to get a partial solution
m: J_1∪{j_0} → P

we can use this repeatedly for a full matching

Question 12

example:

J={A,B,C,D}
P={p,q,r,s}

C[A]={p,q,r,s}
C[B]={q,r,s}
C[C]={r,s}
C[D]={p}

Answer 12

For ABC make A→p, B→q,C→r but then D cannot be assigned without reassignment

p q r s
: \ : \ : \ :
D A B C

we can find open zig zag as plausible C[D] and flip for complete matching

A→q, B→r,C→s, D→p

could use rook polynomial board to visualise but this gave us a required solution

Question 13

job allocation with

|P| bigger than |J|

Answer 13

some people won’t be assigned a job

*we consider a subset T⊆P of people who are poor and really need to be assigned a job

Question 14

THEOREM 54’

addition for plausibility

Answer 14

suppose that every subset U⊆J is plausible

ie |C[u]| ≥ |u|.

suppose also that every u has
|C[u]∩T| ≥ |u| + |T| - |J|

then there is a full matching in which every person in T is assigned

(what we are looking for)

proof: by choosing a set not available to T..

Question 15

DEF Q[p]

Answer 15

in a job allocation problem as before for each person p put

Q[p]={jobs p can do}
={j∈J: p∈C[j] }

Question 16

Example: what are C[j]s and Q[p]s?

    p  q  r  s
A [  ][  ][  ][  ]
B [x][  ][  ][  ]
C [x][x][  ][  ]
D [  ][x][x][x]

x means unshaded

Answer 16

C[A]={p,q,r,s}
C[B]={q,r,s}
C[C]={r,s}
C[D]={p}
candidates able to do job_A_

Q[p]= {A,D}
Q[q]= {A,B}
Q[r]= {A,B,C}
Q[s]= {A,B,C}

jobs doable by candidate_p_

Question 17

PROP 55: full matching

relationship between C[j] and Q[p]

Answer 17

suppose there is a constant d bigger than 0 st

1) for all jobs j there are at least d candidates: |C[j]| ≥ d
2) each person p can do at most d jobs: |Q[p]| ≤ d

Then every set of jobs is plausible, so there is a full matching (*by halls thm).

special case if :|C[j]|= |Q[p]| then there is a full matching

Question 18

COROLLARY 56:

full matching

relationship between C[j] and Q[p]

and TALENTED PEOPLE

Answer 18

suppose
1)for all j |c[j]| = d
(every job can be done by d candidates)

2)for all p |Q[p]| ≤ d
(every person can do less than or equal to d jobs)

and put t= {p : |Q[p]| =d } ={talented people}.
(talented people are those who can do d jobs)

Then there is a full matching in which all in T get jobs.

by prop 55 we know there is a full matching but the talented people are the ones getting the jobs by thm 54’ addition for plausibility

ie if we have people who can do d jobs, where each job can be done by d candidates, and a full matching is possible then these talented people get jobs

Question 19

TRANSVERSAL VERSION

Answer 19

Suppose we have finite sets A_1,…, A_r

A distinct set of Representatives is a list a_1,…,a_r with all a_i’s different and a_i ∈ A_i

for example a family with one representative from each family only

for example A_1 is boys girl 1 knows, etc

ie for U={1,2,4,5} |C[U]| = 3 less than |U| :U isn’t plausible, so no full matching

Question 20

THM:

a TRANSVERSAL

VERSION

distinct set of Representatives if

Answer 20

there is a distinct set of Representatives if for any set {i_1,…,i_k} of indices we have

|A_{i_1} ∪…∪A_{i_k} | ≥ k

for any subset of the representatives union is at least k ie all different: iff for sets A_1,..,A_r any collection of r of the sets contain at least r elements

Question 21

EXAMPLE: Sets
A_1={1, 3}
A_2={2, 3}
A_3={1,3,4,5}
A_4={2,4,6}
A_5={1,5}
A_6={1,2}

marked in red 1

Answer 21

A_1={_1_, 3}
A_2={2, _3_}
A_3={1,3,_4_,5}
A_4={2,4,_6_}
A_5={1,_5_}
A_6={1,_2_}

marked in red 1

families: curlyA= {A_1,..,A_6}

have distinct representatives
(a transversal)

X={1,3,4,6,5,2} any order

a_1=1, a_2=3,…,a_6=2 gives a complete set of Representatives, each distinct value and not all values need be chosen

Question 22

EXAMPLE: Sets
A_1={1, 2,3}
A_2={2, 3}
A_3={3,5,7}
A_4={1,2}
A_5={1,2,3}
A_6={4,5,6}

marked in red 1

Answer 22

don’t have distinct representatives since for example 4 sets:

A_1, A_2, A_4, A_5
contain between them only three members
1,2,3

A_1∪A_2∪A_4∪A_5 ={1,2,3}

and we need the union of any are of those sets to contain at least are elements

Hence family curlyA has no transversal

Question 23

team version

Answer 23

suppose we have set J of jobs , set P of people

and for each job J we have a subset C[j]⊆P of candidates.

However, suppose we now need a team of people for each job, size m_j for job j

U⊆J is plausible if and only if

|C[U]| ≥ Σ_{u∈U} m_u

e.g {j_1,j_2,j_3} is plausible iff

number of candidates able to do any ONE of 3 jobs |C[j_1,j_2,j_3]| ≥ m_{j_1}+m_{j_2}+m_{j_3} sum of team sizes for each job

proof from allocation is plausible if and only if every subset U⊆J is plausible

Question 24

tournament definition

Answer 24

the tournament of employers consists of n Choose 2 games:
(n)
(2)

• each player plays each of the others once
• each game results in a win for one player

Question 25

tournament example
A B C D E play a tournament games and winners shown:

marked red = A*

Answer 25

AB AC AD* AE BC BD BE CD CE D*E

or winner→loser

↓ ↓ ↓
A → B → D → E → C
↑↑ ↑

(lines drawn between the players)

scores table:
A:3 B:2 C:2 D:2 E:1

scores seq
3221 always written in descending order

note that knowing A→B→D→E→C helps us draw
this is a winning line

Question 26

DEF winning line

Answer 26

winner→loser

↓ ↓ ↓
A → B → D → E → C
↑↑ ↑

(lines drawn between the players curved/cross each other from winner to loser)

a winning line is a sequence p_1,…,p_n containing each player exactly once, such that p_1 beats p_2, p_2 beats p_3,…,p_{n-1} beats p_n.

Question 27

LEMMA: winning line

Answer 27

For any tournament of employers, there exists and winning line.

proof by induction. Choose one player p* and use induction hypothesisp_1,..,p_{n-1} to show where p* goes if they beat :
p_1- beginning
no-one, last player
o/w let p_i be the last player in the sequence that beats p* so p* beats p_{i+1}
and
there is a wl
p_1,..,p_i,p*,p_{i+1},…,p_{n-1}

Question 28

LEMMA: nCk used for tournaments

Answer 28

For 0≤k≤n we have

n) (k) (n-k
(2) = (2) + k(n-k) + ( 2 )

Question 29

scores of tournaments of n players

consider a list of non negative integers

when can this be a list of scores for a tournament of n players?

FIRST CONDITION:

Answer 29

FIRST CONDITION:

each of the
(n)
(2)
games gives a score of 1 to one player and 0 to the other

therefore
s_1+..+s_n= total scores of all players= total number of games=
(n)
(2)

ASSUME this is the case

Question 30

sum of scores of tournament for a subset of players

Answer 30

FOR ANY SUBSET U⊆{1,…,n} we put s_u=Σ_{i∈u} s_i

e.g
s_{1,4,7}=s_1+s_4+s_7

we always have s_u + s_{u^c} =
(n)
(2)

Question 31

DEFINITION:
the list s is plausible if

of scores

Answer 31

the list s is plausible if and only if for all u we have

s_u ≥
(|u|)
( 2)

from first condition

Question 32

LEMMA:

the list s is plausible if

of scores

with LEMMA: nCk used for tournaments

Answer 32

if s is plausible then for all u we have
s_u ≤
(|u|)
( 2) + |u|(n-|u|)

In other words, if |u|=k then
s_u ≤
( k)
( 2) + k(n-k)

*reversible:so plausible if and only if for all u, |u|=k then
s_u ≤
( k)
( 2) + k(n-k)

Question 33

LEMMA:

Answer 33

if the numbers s_i are the scores from a tournament, then the list is plausible

ie
s_1+..+s_n= total scores of all players= total scores from games between members of u + total from games between u and u^c =
( k)
( 2) + a number between 0 and (n-k))

so 
( k)
( 2)
≤ s_u ≤
( k)
( 2)   +     k(n-k)

Question 34

THEOREM 68
LANDAU

*reversible

Answer 34

if the list s_1,..,s_n is plausible
(s_1+..+s_n= 
(n) 
(2)
)

Then there exists a tournament with scores s_1,..,s_n

Question 35

addendum: THEOREM 68

LANDAU

Answer 35

suppose that the numbers s_1,..,s_n are in decreasing order. Then for any u with |u|=k we have

s_{n-k+1} +…+s_n ≤ s_u ≤ s_1+…+s_k

therefore s is plausible if and only if for All K

s_1+…+s_k ≤
( k)
( 2) + k(n-k)

if and only if for All K

s_{n-k+1} +…+s_n ≥
(k)
(2)

(=last k s’s)

Question 36

SUMMARY FOR SCORES OF TOURNAMENTS AND EQUIVALENT STATEMENTS

CONDITIONS

Answer 36

For s_1,..,s_n in N with s_1+…s_n =
(n)
(2)
equivalent:

(1) There is a tournament of employers with scores s_1,..,s_n

(2) The sum of any k of the s_i is at least
(k)
(2)

(3) The sum of any k of the s_i is at most
(k)
(2) + k(n-k)

***ordered s_1 ≥… ≥s_n then
LAST k at least kC2
FIRST k at most kC2 + k(n-k)

Question 37

EXAMPLE:
S=532221
are scores of a tournament?

Answer 37

n=6
CHECK: s_1+…s_n =15 = 6C2

seems to satisfy conditions:
1  ≥ 1C2=0
2+1 = 3  ≥ 2C2=1
2+2+1=5  ≥ 3C2 = 3
....
5+...+1= 6C2

example of a tournament:

right against top
    1   2   3   4    5  6
1 [X][W][W][W][W][W]
2[ L][X ][ L][W][W][W]
3[ L][W][X][ L ][ L][W]
4[ L][ L][W][ X][ L][W]
5[ L][ L][W][W][ X][ L]
6[ L][ L][ L][ L][W][ X]

x means doesnt play
e.g player 5 lost against player 2

notice symmetric

Question 38

EXAMPLE:
S=4442111
are scores of a tournament?

Answer 38

n=7 but
s_1+..s_7= 17 not equal to 21= 7C2

or sum of last four: 1+1+1+2=5 less than 4C2 =6
violates condition

so cannot be a list of scores from a tournament

Question 39

EXAMPLE:
S=5444110
are scores of a tournament?

Answer 39

sum of last 3 is
2 which is less than 3C2 and thus not plausible

1,1,0 mean 3 games played between them and thus should share 3 wins

Question 40

EXAMPLE:
S=987654321
are scores of a tournament?

Answer 40

9 players n=9

scores for tournament in which they lower numbered player always wins i.e. 1 better than 2, 2 better than 3 etc

Question 41

EXAMPLE:***
For an odd number n=2m+1 we can imagine a tournament in which i beats j if and only if

j-i ∈{1,..,m} mod 2m+1

Answer 41

m=3

    1    2   3    4    5  6    7
1 [X][W][W ][W ][ L ][ L ][ L]
2[ L][X ][W ][W ][W][ L ][ L]
3[ L][ L ][X ][W ][W ][W][ L]
4[ L][ L ][ L ][ X ][W][W][W]
5[W][ L ][ L ][ L ][ X][ W][W]
6[W][W][ L ][ L ][ L ][ X][W]
7[W][W][W ][ L ][ L ][ L ][X]

This has scores m,…,m
(repeated n times)

because this is the score sequence from a tournament, it must satisfy the plausibility condition. We can see this more directly:

(sum of any k scores, with k≤n )

=km=
k [(n-1)/2]≥ kC2

Question 42

problem: construct a tournament with scores 7777722222

Answer 42

10 players

we can :
construct tournament with players 1-5 with scores 22222 by case m=2 of ***

and 6-10 with scores 22222.

Then consider a combo tournament with players 1,..,10 in which 1-5 always beat 6-10.