Chapter 4: halls marriage theorem Flashcards
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?
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
consider a job allocation problem
finite set of jobs and finite set of people
corresponds to counting rook polynomials
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
C[U] in job allocation
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}
A full matching for u, set of jobs PLAUSIBILITY definition
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)
LEMMA: for plausibility and full matching
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|
COROLLARY:for plausibility and full matching
if there are any impossible/implausible sets, then the problem is not solvable
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
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)
halls marriage theorem
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
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
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
OPEN ZIGZAG
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)
IS THERE ALWAYS AN OPEN ZIGZAG?
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
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}
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
job allocation with
|P| bigger than |J|
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
THEOREM 54’
addition for plausibility
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..
DEF Q[p]
in a job allocation problem as before for each person p put
Q[p]={jobs p can do}
={j∈J: p∈C[j] }
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
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_
PROP 55: full matching
relationship between C[j] and Q[p]
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
COROLLARY 56:
full matching
relationship between C[j] and Q[p]
and TALENTED PEOPLE
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
TRANSVERSAL VERSION
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
THM:
a TRANSVERSAL
VERSION
distinct set of Representatives if
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
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
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
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
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
team version
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
tournament definition
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
tournament example
A B C D E play a tournament games and winners shown:
marked red = A*
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
DEF winning line
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.
LEMMA: winning line
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}
LEMMA: nCk used for tournaments
For 0≤k≤n we have
n) (k) (n-k
(2) = (2) + k(n-k) + ( 2 )
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:
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
sum of scores of tournament for a subset of players
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)
DEFINITION:
the list s is plausible if
of scores
the list s is plausible if and only if for all u we have
s_u ≥
(|u|)
( 2)
from first condition
LEMMA:
the list s is plausible if
of scores
with LEMMA: nCk used for tournaments
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)
LEMMA:
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)
THEOREM 68
LANDAU
*reversible
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
addendum: THEOREM 68
LANDAU
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)
SUMMARY FOR SCORES OF TOURNAMENTS AND EQUIVALENT STATEMENTS
CONDITIONS
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)
EXAMPLE:
S=532221
are scores of a tournament?
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
EXAMPLE:
S=4442111
are scores of a tournament?
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
EXAMPLE:
S=5444110
are scores of a tournament?
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
EXAMPLE:
S=987654321
are scores of a tournament?
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
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
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
problem: construct a tournament with scores 7777722222
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.
