Case Study: Building a Tiny LP Solver and a Probabilistic-Method Lab

DataField.Dev

Case Study: Building a Tiny LP Solver and a Probabilistic-Method Lab

"The best way to understand a theorem is to build the smallest machine that obeys it."

Executive Summary

This is a build-heavy counterpart to the audit in Case Study 1. Instead of measuring a system against the laws, you will construct two small machines that embody the laws — and the construction is where the understanding lives. First you will build a from-scratch linear-program solver that finds the optimum by enumerating the corners of the feasible region (the conceptual core of the simplex algorithm, §40.1), use it on a real allocation problem, and then build a dual checker that produces an optimality certificate via weak duality. Second you will build a probabilistic-method lab (§40.3): a verifier for monochromatic triangles, a brute-force confirmation that $R(3,3) = 6$, and an experiment that confronts Erdős's existence theorem with the uncomfortable fact that it tells you a good coloring exists while pointing to none. Everything is built from primitives you already wrote across the book — itertools.combinations, simple arithmetic — with no external solver.

The throughline: in §40.1 and §40.3 the proofs are short but abstract. Building the machines that obey them is how you convert "I followed the proof" into "I can wield the idea."

Skills applied

Building an LP solver by corner enumeration; understanding why optima sit at corners (§40.1).
Building a weak-duality checker that certifies optimality, not just reports it (§40.1).
Building a monochromatic-triangle verifier and confirming $R(3,3) = 6$ by construction (§40.3).
Building a Monte-Carlo lab around Erdős's bound and articulating existence-without-construction (§40.3).

Background

The scenario

Tier 3 — a constructed teaching scenario. You are the engineer on a small operations team. Two tasks land in the same sprint, and you decide to build minimal, correct, explainable tools rather than reach for a heavyweight library — partly to ship, partly because you want to understand what the library would do.

The allocation task. A workshop assembles two products from shared labor and material and wants the profit-maximizing mix. You want a tool that returns the optimum and a proof that it is optimal — a number a skeptic cannot argue with.
The "unavoidable structure" task. A scheduling colleague half-jokingly insists that "in any group of six people, three are mutual friends or three are mutual strangers — and I can't picture why." You decide to build a tiny lab that (a) checks this claim exhaustively, (b) shows it fails at five, and (c) lets you play with the famous probabilistic-method argument that good colorings of large graphs exist even though nobody can draw one.

Why this matters

A library hands you an answer; a built-from-scratch tool hands you understanding plus a certificate. The LP solver here is small enough to read in one sitting, yet it computes exactly what an industrial solver computes for two variables — and the duality checker adds something most beginners never see: a proof that the answer is optimal. The Ramsey lab, meanwhile, makes the most counterintuitive idea in the chapter — proving existence without construction — something you can run, watch, and feel the bite of. This is theme four (computation and proof are complementary) built with your own hands.

Phase 1: Build the LP solver (corner enumeration)

The foundational fact of §40.1 is that an LP optimum, if it exists, sits at a corner (vertex) of the feasible polygon. A corner is where two constraint boundaries cross. So the algorithm is: intersect every pair of constraints, keep the intersections that are feasible (satisfy all constraints), and return the one with the best objective. For $m$ constraints there are only $\binom{m}{2}$ candidate corners — finite and small — which is exactly how the search becomes tractable.

We will solve the workshop LP of §40.1:

$$\text{maximize } 3x + 5y \quad \text{s.t.} \quad x + 2y \le 14, \quad 2x + y \le 10, \quad x, y \ge 0.$$

from itertools import combinations

# Constraint (a, b, c) means a*x + b*y <= c. Encode x>=0, y>=0 as -x<=0, -y<=0.
cons = [(1, 2, 14), (2, 1, 10), (-1, 0, 0), (0, -1, 0)]
obj = (3, 5)   # maximize 3x + 5y

def intersect(c1, c2):
    (a1, b1, r1), (a2, b2, r2) = c1, c2
    det = a1 * b2 - a2 * b1
    if det == 0:
        return None                       # parallel boundaries: no unique corner
    x = (r1 * b2 - r2 * b1) / det
    y = (a1 * r2 - a2 * r1) / det
    return (x, y)

def feasible(p):
    x, y = p
    return all(a * x + b * y <= c + 1e-9 for a, b, c in cons)

def solve_lp():
    best = None
    for c1, c2 in combinations(cons, 2):  # each corner = intersection of two boundaries
        p = intersect(c1, c2)
        if p and feasible(p):
            val = obj[0] * p[0] + obj[1] * p[1]
            if best is None or val > best[0]:
                best = (val, p)
    return best

print(solve_lp())
# Expected output:
# (36.0, (2.0, 6.0))

Hand-derived check. The two non-trivial corners come from intersecting the binding constraints. From $x + 2y = 14$ and $2x + y = 10$: substitute $y = 10 - 2x$ into the first, $x + 2(10 - 2x) = 14 \Rightarrow -3x = -6 \Rightarrow x = 2$, so $y = 6$, objective $3(2) + 5(6) = 36$. The other feasible corners $(0,0), (5,0), (0,7)$ give $0, 15, 35$. The solver's (36.0, (2.0, 6.0)) matches the chapter's hand-computation exactly — our machine obeys the theory.

🔄 Check Your Understanding Why does the solver only check intersections of pairs of constraints — why not also test the midpoints of edges or the centroid of the polygon?

Answer

Because of the corner theorem (§40.1): a linear objective is extremized at a vertex of the feasible polytope, never strictly inside an edge or the interior. From any non-corner point you can slide along the objective's gradient and improve until a second constraint stops you — i.e., until you reach a corner. So the finite set of pairwise intersections provably contains the optimum; midpoints and centroids can only tie a corner, never beat one.

Phase 2: Build the optimality certificate (weak duality)

A solver that returns 36 is useful; a solver that proves 36 is optimal is trustworthy. Section 40.1's weak duality gives the tool: for any primal-feasible $(x,y)$ and any dual-feasible $(u,v)$, $3x + 5y \le 14u + 10v$. So if we can exhibit a dual-feasible $(u,v)$ whose objective equals our primal value, that dual point is a certificate: it proves no primal solution can exceed our value.

The dual of the workshop LP (derived in §40.1) is

$$\text{minimize } 14u + 10v \quad \text{s.t.} \quad u + 2v \ge 3, \quad 2u + v \ge 5, \quad u, v \ge 0.$$

We build a checker. We do not need to solve the dual from scratch — we only need to verify a proposed dual point. (Verifying is cheaper than solving; that asymmetry is the whole idea behind certificates, and echoes the verification-vs-solution theme of Chapter 37.)

def dual_feasible(u, v):
    return u + 2 * v >= 3 - 1e-9 and 2 * u + v >= 5 - 1e-9 and u >= -1e-9 and v >= -1e-9

def dual_objective(u, v):
    return 14 * u + 10 * v

def certify(primal_val, u, v):
    """Return True if (u,v) is a dual-feasible certificate that primal_val is optimal."""
    return dual_feasible(u, v) and abs(dual_objective(u, v) - primal_val) < 1e-9

# The optimal dual prices from 40.1: u = 7/3 (labor), v = 1/3 (material).
u, v = 7/3, 1/3
print(round(dual_objective(u, v), 3))
print(certify(36.0, u, v))
# Expected output:
# 36.0
# True

Hand-derived check. Dual objective $14(7/3) + 10(1/3) = 98/3 + 10/3 = 108/3 = 36$. Dual feasibility: $u + 2v = 7/3 + 2/3 = 3 \ge 3$ ✓ and $2u + v = 14/3 + 1/3 = 5 \ge 5$ ✓, both binding; $u, v > 0$ ✓. So certify(36.0, 7/3, 1/3) returns True: the dual point proves the primal optimum is $\le 36$, and since our solver found a primal point achieving $36$, the two squeeze the optimum to exactly $36$.

💡 Intuition: A certificate flips the burden of proof. Without it, "36 is optimal" is a claim you ask the reader to trust. With it, you hand over a single dual point and say: check these two inequalities and this one equation yourself; if they hold, 36 is provably the best possible. That is the difference between "it passed my search" and "here is why nothing beats it" — theme two of the book.

🔗 Connection: This is the same shape as the max-flow min-cut theorem (Chapter 34): exhibit a flow and a cut of equal value, and each certifies the other is optimal. You have now built, in miniature, the certificate machinery behind one of the deepest theorems you proved.

Phase 3: Build the monochromatic-triangle verifier and confirm R(3,3) = 6

Switch tasks. We build the Ramsey lab, starting with the core verifier from §40.3: given a 2-coloring of $K_n$, does a monochromatic triangle exist? A triangle is any 3-subset of vertices; it is monochromatic if its three edges share a color.

from itertools import combinations

def has_mono_triangle(n, color):
    """color(i, j) -> 'R' or 'B' for edge {i, j}. True iff a mono triangle exists."""
    for a, b, c in combinations(range(n), 3):
        if color(a, b) == color(b, c) == color(a, c):
            return True
    return False

# The K5 coloring that AVOIDS a mono triangle: the pentagon + pentagram.
# Red iff the two endpoints differ by 1 or 4 (mod 5); blue otherwise.
def c5(i, j):
    return 'R' if (i - j) % 5 in (1, 4) else 'B'

print(has_mono_triangle(5, c5))   # K5 with this coloring avoids it -> witnesses R(3,3) > 5
print(has_mono_triangle(6, c5))   # extend the SAME rule to 6 vertices -> now forced
# Expected output:
# False
# True

Hand-derived check (the $n=5$ case). Under c5, vertex 0 is red to 1 and 4, blue to 2 and 3. Take any triangle, say $\{0,1,2\}$: edge $01$ is red ($|0-1|=1$), edge $12$ is red, edge $02$ is blue ($|0-2|=2$) — not monochromatic. Checking all $\binom{5}{3}=10$ triangles (the pentagon-plus-pentagram structure guarantees it) yields no monochromatic one, so has_mono_triangle(5, c5) is False. This is a construction proving $R(3,3) > 5$: five people can avoid the pattern.

To confirm the matching upper bound $R(3,3) \le 6$ — that every coloring of $K_6$ has a monochromatic triangle — we would brute-force all $2^{\binom{6}{2}} = 2^{15} = 32768$ colorings and verify each contains one. We do not run code in this book, but we can state the loop and reason about its output: by the §40.3 proof (pigeonhole on the five edges at a vertex), every one of those 32768 colorings contains a monochromatic triangle, so an exhaustive checker would print True for all of them and False for none. Construction ($n=5$ avoids) plus the proof ($n=6$ cannot) gives $R(3,3) = 6$.

from itertools import combinations, product

def all_colorings_of_K6_have_mono_triangle():
    """Reasoned, not executed: would exhaustively confirm R(3,3) <= 6."""
    edges = list(combinations(range(6), 2))          # 15 edges
    for assignment in product('RB', repeat=len(edges)):   # 2^15 = 32768 colorings
        cmap = dict(zip(edges, assignment))
        def color(i, j, cmap=cmap):
            return cmap[(i, j)] if (i, j) in cmap else cmap[(j, i)]
        if not has_mono_triangle(6, color):
            return False                              # a counterexample would appear here
    return True                                       # none does

# Expected output (by the 40.3 proof, were this run):
# True

⚠️ Common Pitfall: It is tempting to "confirm $R(3,3) = 6$" by testing a few colorings of $K_6$ and seeing a triangle each time. That confirms nothing — it is the very "tested it on some cases" trap theme four warns against. The construction at $n=5$ is a genuine proof of the lower bound; the exhaustive check (or the §40.3 argument) is what settles the upper bound. Evidence on a few colorings is neither.

Phase 4: Build the probabilistic-method lab and feel its bite

Now the deep part. Section 40.3's Erdős argument proves that for large $k$, some 2-coloring of $K_n$ has no monochromatic $K_k$ — whenever $\binom{n}{k}\,2^{\,1-\binom{k}{2}} < 1$ — yet it names no such coloring. We build a lab to (a) compute that bound and (b) confront the existence-without- construction idea head-on.

First, the bound. We find, for $k = 4$, the largest $n$ for which the expected number of monochromatic $K_4$'s in a random coloring is below 1:

from math import comb

def expected_mono_ksets(n, k):
    """E[X] for a uniformly random 2-coloring of K_n: C(n,k) * 2^(1 - C(k,2))."""
    return comb(n, k) * 2 ** (1 - comb(k, 2))

def largest_n_below_one(k):
    """Largest n with E[X] < 1, giving the Erdos lower bound R(k,k) > n."""
    n = k
    while expected_mono_ksets(n + 1, k) < 1:
        n += 1
    return n

k = 4
print(round(expected_mono_ksets(5, k), 4))     # E[X] for n=5, k=4
print(largest_n_below_one(k))                  # Erdos lower bound: R(4,4) > this
# Expected output:
# 0.1562
# 6

Hand-derived check. For $n = 5, k = 4$: $\binom{5}{4} = 5$ and $\binom{4}{2} = 6$, so

$$E[X] = 5 \cdot 2^{\,1-6} = 5 \cdot 2^{-5} = \frac{5}{32} = 0.15625 \approx 0.1562.$$

(The exponent $2^{\,1-\binom{k}{2}}$ already folds in the factor of 2 for "all-red or all-blue," so there is no extra doubling.) For largest_n_below_one(4) we need the largest $n$ with $\binom{n}{4}\,2^{-5} < 1$, i.e. $\binom{n}{4} < 32$: $\binom{6}{4} = 15 < 32$ ✓ but $\binom{7}{4} = 35 \ge 32$ ✗, so the loop stops at $n = 6$. The bound is $R(4,4) > 6$.

🐛 Find the Error: A teammate hand-traces this and writes the expected output as 0.3125 / 6, reasoning that "there are two colors, so multiply by an extra 2." Pinpoint their mistake using the chapter's exact formula.

Answer

The factor of 2 for the two colors is already inside the chapter's exponent: the probability a fixed $k$-set is monochromatic is $2 \cdot 2^{-\binom{k}{2}} = 2^{\,1-\binom{k}{2}}$, and $E[X] = \binom{n}{k}\,2^{\,1-\binom{k}{2}}$. Multiplying again double-counts it. The correct value is $\binom{5}{4}\,2^{1-6} = 5/32 = 0.1562$, not $0.3125$. The lesson is theme four's: a printed number is only as good as the derivation behind it — hand-check the formula, do not eyeball the doubling.

The bite. Compare the Erdős lower bound $R(4,4) > 6$ (from this $k=4$ computation) to the known exact value $R(4,4) = 18$ (§40.3). The probabilistic bound is correct but loose — and that looseness is the point: the method proves a good coloring of $K_6$ (indeed of much larger graphs as $k$ grows) exists, without ever drawing one. For $k=4$ it under-shoots the truth badly; its real power shows for large $k$, where it yields $R(k,k) > 2^{k/2}$, an exponential lower bound no construction has matched.

# The existence claim has NO accompanying construction. We can verify a SPECIFIC
# small coloring avoids a pattern (Phase 3's c5 for K5), but the Erdos theorem
# for large n hands us a guarantee, not a coloring. There is no function to call
# that returns "the good coloring" -- that absence IS the threshold concept.
def good_coloring_exists(n, k):
    """True if Erdos's bound guarantees a K_k-free-of-one-color 2-coloring of K_n."""
    return expected_mono_ksets(n, k) < 1

print(good_coloring_exists(5, 4))   # guaranteed to exist...
print("...but no construction is returned -- existence without construction.")
# Expected output:
# True
# ...but no construction is returned -- existence without construction.

🚪 Threshold Concept. You built a function that proves a coloring exists and cannot return one. good_coloring_exists answers "is there a good coloring?" with a confident True, yet there is no sibling function find_good_coloring the proof could supply — the averaging argument guarantees a success without exhibiting it. Sitting with that gap — a True you cannot turn into an object — is the clearest way to feel why existence is strictly weaker than construction. It is the same family as Chapter 10's uncountability and Chapter 36's undecidability: knowledge that outruns construction.

Discussion Questions

The LP solver enumerates $\binom{m}{2}$ corners for $m$ constraints. That is fine for a handful of constraints but blows up for thousands. Which algorithm named in §40.1 avoids enumerating all corners, and what does it do instead? Why is your tiny solver still the right pedagogical starting point?
The certificate in Phase 2 verified a dual point rather than solving the dual. Relate this to the verification-versus-solution distinction of Chapter 37 (P vs. NP). Why is "easy to check, hard to find" a recurring and powerful pattern?
In Phase 3 we proved $R(3,3) > 5$ by construction (the pentagram coloring) and $R(3,3) \le 6$ by an argument (or exhaustive check). Why could we not prove the lower bound $R(3,3) > 5$ the way Erdős proves large lower bounds — by averaging — and get the exact value $6$? What does this say about when the probabilistic method is the right tool?
good_coloring_exists returns True with no construction. Suppose your manager says "if it exists, just return it." Explain, using this chapter, why that request is not a missing feature but a mathematical impossibility for this proof technique — and what kind of different argument (constructive) you would need to actually produce the object.

Your Turn: Extensions

Option A (a third constraint). Add the constraint $x \le 4$ to the workshop LP (encode as $(1, 0, 4)$) and re-run solve_lp in your head: recompute the feasible corners and the new optimum, giving the hand-derived expected output. Does the optimum move? Then find a dual certificate for the new optimum (the dual gains a variable).
Option B (R(3,4)). Modify has_mono_triangle into a checker for "a red triangle ($K_3$) or a blue $K_4$," and reason (do not brute-force by hand) about how you would search for the largest $K_n$ that avoids both — the lower-bound side of $R(3,4)$. State what the answer $R(3,4) = 9$ would require you to confirm.
Option C (sharper Erdős). Tabulate expected_mono_ksets(n, k) for $k = 5$ and increasing $n$, find the largest $n$ with $E[X] < 1$ by hand, and report the lower bound $R(5,5) > n$ it yields. Compare to the chapter's known range $43 \le R(5,5) \le 48$: is your bound inside, below, or above it?

Key Takeaways

The corner theorem makes LP buildable in a dozen lines. Optima sit at vertices, so intersect pairs of constraints, keep feasible ones, take the best — the kernel of simplex (§40.1).
A certificate beats a search. Weak duality lets a single dual point prove optimality; verifying it is cheaper than solving, the same easy-to-check/hard-to-find pattern as Chapter 37.
Construction and proof do different jobs in Ramsey theory. A coloring proves a lower bound; an argument (or exhaustive check) proves the upper bound; together they pin $R(3,3) = 6$.
Some Trues come with no object. Building good_coloring_exists — a proof-of-existence with no constructor — is the most concrete way to feel existence-without-construction, the chapter's threshold idea and theme four made tactile.