Three tools that punch above their weight. Matching in bipartite graphs solves assignment problems. Ramsey theory guarantees that sufficiently large structures contain unavoidable order. Generating functions encode sequences as polynomials, turning recurrence-solving into algebra.
Matching in bipartite graphs
A matching is a set of edges with no shared vertices. In a bipartite graph (vertices split into two groups, edges only between groups), Hall's theorem says a perfect matching exists if and only if every subset S of one side has at least |S| neighbors on the other side.
Scheme
; Bipartite graph: left = (1 2 3), right = (a b c); Edges: 1-a, 1-b, 2-a, 2-c, 3-b, 3-c
(define edges '((1 a) (1 b) (2 a) (2 c) (3 b) (3 c)))
; Neighbors of a vertex
(define (neighbors v)
(map cadr (filter (lambda (e) (equal? (car e) v)) edges)))
; Check Hall's condition for all subsets of left side; For each subset S, |N(S)| >= |S|
(define left '(123))
; Powerset (excluding empty set)
(define (powerset lst)
(if (null? lst) '(())
(let ((rest (powerset (cdr lst))))
(append rest
(map (lambda (s) (cons (car lst) s)) rest)))))
(define (unique lst)
(cond ((null? lst) '())
((member (car lst) (cdr lst)) (unique (cdr lst)))
(else (cons (car lst) (unique (cdr lst))))))
(define (neighborhood subset)
(unique (apply append (map neighbors subset))))
(define subsets (filter (lambda (s) (not (null? s))) (powerset left)))
(display "Hall's condition check:") (newline)
(for-each (lambda (s)
(let ((ns (neighborhood s)))
(display " S=") (display s)
(display " N(S)=") (display ns)
(display " |N(S)|>=|S|? ") (display (>= (length ns) (length s)))
(newline)))
subsets)
Python
fromitertoolsimport combinations
edges = [(1,'a'),(1,'b'),(2,'a'),(2,'c'),(3,'b'),(3,'c')]
left = [1, 2, 3]
nbrs = lambda v: {b for a,b in edges if a == v}
print("Hall's condition:")
for size inrange(1, len(left)+1):
for s in combinations(left, size):
ns = set().union(*(nbrs(v) for v in s))
print(f" S={s} N(S)={ns} |N(S)|>={len(s)}? {len(ns)>=len(s)}")
Ramsey theory
R(s,t) is the smallest n such that any 2-coloring of K_n's edges contains a red K_s or a blue K_t. R(3,3) = 6: among any 6 people, three are mutual friends or three are mutual strangers. The exact values grow very fast. R(5,5) is still unknown.
Scheme
; Verify R(3,3) = 6 by exhaustive check on K5.; Show K5 CAN be 2-colored without a monochromatic triangle.; K5 edges
(define k5-edges
'((01) (02) (03) (04) (12) (13) (14) (23) (24) (34)))
; Color assignment: edges of a cycle get red, diagonals get blue.; Cycle: 0-1, 1-2, 2-3, 3-4, 4-0
(define red '((01) (12) (23) (34) (04)))
(define (is-red? e)
(or (member e red)
(member (list (cadr e) (car e)) red)))
; Check for monochromatic triangle
(define (triangle? a b c color?)
(and (color? (list a b)) (color? (list b c)) (color? (list a c))))
(define verts '(01234))
(define (has-mono-triangle? color?)
(let loop ((triples '()))
; Generate all triples
(let check ((i 0))
(if (>= i 3) #f
(let check-j ((j (+ i 1)))
(if (>= j 4) (check (+ i 1))
(let check-k ((k (+ j 1)))
(if (>= k 5) (check-j (+ j 1))
(if (triangle? i j k color?)
#t
(check-k (+ k 1)))))))))))
(display "Red triangle in K5? ")
(display (has-mono-triangle? is-red?)) (newline)
(display "Blue triangle in K5? ")
(display (has-mono-triangle? (lambda (e) (not (is-red? e))))) (newline)
(display "R(3,3) > 5: K5 can be 2-colored without mono triangle") (newline)
; Known small Ramsey numbers
(display "R(3,3) = 6") (newline)
(display "R(3,4) = 9") (newline)
(display "R(4,4) = 18")
Python
fromitertoolsimport combinations
# K5 cycle coloring: no monochromatic triangle
red = {(0,1),(1,2),(2,3),(3,4),(0,4)}
is_red = lambda a,b: (min(a,b),max(a,b)) in red
def has_mono(color_fn):
returnany(
all(color_fn(a,b) for a,b in combinations(tri, 2))
for tri in combinations(range(5), 3)
)
print(f"Red triangle? {has_mono(is_red)}")
print(f"Blue triangle? {has_mono(lambda a,b: not is_red(a,b))}")
print("R(3,3) > 5 confirmed. R(3,3) = 6.")
Generating functions
The generating function of a sequence a_0, a_1, a_2, ... is the formal power series A(x) = a_0 + a_1*x + a_2*x^2 + .... Adding sequences adds their generating functions. Multiplication corresponds to convolution. Solving a recurrence becomes solving an algebraic equation.
Scheme
; Represent polynomials as lists of coefficients: (a0 a1 a2 ...); Polynomial addition
(define (poly-add a b)
(cond ((null? a) b)
((null? b) a)
(else (cons (+ (car a) (car b))
(poly-add (cdr a) (cdr b))))))
; Polynomial multiplication (convolution)
(define (poly-mul a b)
(if (null? a) '()
(poly-add
(map (lambda (bi) (* (car a) bi)) b)
(cons 0 (poly-mul (cdr a) b)))))
; GF for Fibonacci: F(x) = x / (1 - x - x^2); Approximate by multiplying: (1 + x + x^2 + ...)*(x); Better: just compute coefficients from the recurrence
(define (fib-coeffs n)
(let loop ((i 0) (a 0) (b 1) (result '()))
(if (> i n) (reverse result)
(loop (+ i 1) b (+ a b) (cons a result)))))
(display "Fibonacci GF coefficients (first 10):") (newline)
(display (fib-coeffs 9)) (newline)
; Product of GFs = convolution of sequences; (1 + x)^3 = 1 + 3x + 3x^2 + x^3
(define one-plus-x '(11))
(define squared (poly-mul one-plus-x one-plus-x))
(define cubed (poly-mul squared one-plus-x))
(display "(1+x)^3 = ") (display cubed) (newline)
; Should be (1 3 3 1) = binomial coefficients C(3,k); (1+x)^4
(display "(1+x)^4 = ") (display (poly-mul cubed one-plus-x))
Levin's chapter 5 is a sampler of three deep topics. The matching verification uses Hall's condition but does not implement an augmenting-path algorithm. Ramsey theory is demonstrated by example (R(3,3) = 6) because exact computation of larger Ramsey numbers is intractable. Generating functions are represented as coefficient lists; the formal power series operations (addition, multiplication) are polynomial arithmetic. The connection between convolution and sequence multiplication ties everything together.
Hall's marriage theorem