Four WEIRD Theorems I Learned from Wikipedia

You Won’t Believe How SIMPLE Their Proofs Are!

1. Balinski’s Theorem. If is a convex -dimensional polytope, then its skeleton is a -connected graph. (The skeleton of a polytope is the graph you get from just taking the vertices and edges. A -connected graph is a graph which is still connected if you delete any vertices.)

Proof.  Let be any set of at most vertices of , and pick a vertex outside . Since contains at most points, it is contained in a hyperplane in , and there is a linear functional which is zero on but nonzero outside it. Call a point positive if takes a positive value on it, and negative otherwise.

Now, apply the simplex method from linear programming; it tells us that there is a path from every vertex to the -maximizing vertex , and each move along this path only increases the value of . Thus and every positive point is connected to by a path of only positive points. Similarly, and every negative point is connected to the -minimizing vertex by only negative points. Thus every vertex outside is connected to .

2. The De Bruijn–Erdős Theorem. If all finite subgraphs of an infinite graph are -colorable, then so is . (A graph is -colorable if it has a proper -coloring, i.e. an assignment of integers up through to vertices so that adjacent vertices have different colors.)

Proof. Proper colorings of are functions , which we can think of as points in . Under the product topology, is compact by Tychonoff’s theorem. For any finite subgraph of , denote by the (closed) subset of functions in which properly color . By the assumption, is nonempty. Furthermore, any finite intersection of ‘s is itself and and is nonempty. Thus, by compactness the mutual intersection of all the ‘s is nonempty. Any common intersection is a proper coloring of .

3. Frucht’s Theorem. Every finite group is the automorphism group of a finite simple graph.

Proof. For a finite group , pick a set of generators and construct the (directed) Cayley graph , the graph whose vertex set is and edges are drawn between elements differing by an element of . Color each edge according to which generator it represents multiplication by. Then, it is easy to check that the only automorphisms of the (colored, directed) are given by multiplication by elements of , and so .

It remains to convert into an honest uncolored, undirected graph. This can be done by choosing different “weird gadget” graphs to replace the edges in each color class with. For example, I might replace the edges of the first color with paths of length seventeen with a Petersen graph attached to the fourth internal vertex. As long as these gadgets are weird enough, no additional automorphisms are introduced.

4. The Gallai–Hasse–Roy–Vitaver Theorem. The chromatic number of an undirected graph is equal to the minimum number of vertices, over all orientations of , in the longest oriented path in . (An orientation of an undirected graph is a directed graph obtained by giving each edge in a direction.)

Proof. If has a proper -coloring, orient each edge to go from the smaller color to the larger color. Then, every oriented path in this orientation contains at most vertices.

In the opposite direction, suppose we have an orientation of for which every oriented path contains at most vertices. Pick a maximal acyclic subgraph , i.e. keep adding edges that don’t form an oriented cycle until you can’t. Color each vertex of by the length of the longest path of ending in that vertex. This will be a proper -coloring of .

HPMoE 2

HPMOE2

As usual, post solutions in ROT13.

Harry Potter and the Method of Entropy

I did some Aversion Factoring and found that my main aversion to writing math is the terrible LaTeX support on WordPress. For now, I’ll try writing things up offline and posting PDFs.

HPMoE is a sequence on the entropy method in combinatorics. It should be fun to think about for anyone interested in information theory and probability as well.

HPMoE1

Please post solutions to the exercises in ROT13.

Solzhenitsyn’s Yin Yang

If only it were all so simple! If only there were evil people somewhere insidiously committing evil deeds, and it were necessary only to separate them from the rest of us and destroy them. But the line dividing good and evil cuts through the heart of every human being. And who is willing to destroy a piece of his own heart?
― Aleksandr Solzhenitsyn, The Gulag Archipelago 1918-1956

Solzhenitsyn states that the line dividing good and evil cuts through every human heart. This can’t literally be true – human hearts are somewhat evenly distributed around the globe.

The first question we might ask is: instead of a line, what’s the simplest surface we can draw that cuts through the heart of every human being? But simply cutting through is a boring interpolation question. If you’re an idealist like me, you’d think every human heart is exactly half good and half evil. So the real question is: what’s the simplest surface that bisects every human heart?

Ramanujan Graphs

Here is an exposition of the construction of bipartite Ramanujan graphs for my own benefit, starting from basics about expanders: RamanujanGraphs.

The Heilbronn Triangle Problem

I recently gave a talk (here is an outline) about the work of K. F. Roth on the famous triangle problem of Heilbronn, and was shocked and saddened to discover that Roth passed away that same day. Terry Tao wrote a great post about some of Roth’s most important results in analytic number theory.

Today I will discuss the general approach of Roth, later refined by Komlos, Pintz, and Szemeredi, in proving upper bounds for the Heilbronn Triangle Problem. At the end of the day, the most interesting step comes from a quasi-orthogonality property between indicator functions of bounded strips in the plane. Let be a pair of points in the plane and let be the indicator function of the strip of points at most away from the line through . We cut off these functions outside some convex region, say the unit circle – call this the cutoff region. Then, it is natural to consider the “expansion function”

,

which measures the weighted difference between two strips of different widths , around the same line. The point is that if we integrate this expansion function against the indicator function of a given set of points in the plane, then  counts the change in the density of points when we expand from a strip of width to a strip of width .

Primitive Sets with Small Gaps

A primitive set is a set of positive integers such that no pair of distinct elements satisfies .

A square-primitive set is a set of positive integers such that no pair of distinct elements has ratio equal to an square integer.

In the following writeup, I show how to construct square-primitive sets with very short gaps . This relies on dividing the poset ordered by divisibility into antichains consisting of all numbers in with exactly (not necessarily distinct) prime factors, and then picking one randomly.

Square Primitive Sets With Small Gaps