Discrete — page 4

Every edge on exactly two cycles

Draw a graph on paper without crossings and its faces are cycles, each edge on exactly two of them. George Szekeres and Paul Seymour asked in the 1970s whether every graph without a bridge has such a set of cycles, drawn on paper or not. The Petersen graph needs five, the flower snark on twenty points five as well, every random graph tried has one, and nobody has proved it — though a minimal counterexample would have to be a snark.

Coins hidden in the roots

The polynomial that counts permutations by their descents has no product formula, and nothing in the definition of a descent is a coin toss. But every root of the polynomial is real and negative, and a polynomial like that is a product of coins in disguise: each root r is a coin landing heads with chance 1/(1 − r). The descent count of a random permutation is exactly a sum of independent coins nobody can point to — which is why it is bell-shaped, and why its coefficients obey inequalities the inversion count breaks.

The longest wait for a prime

Near a number x the primes are on average log x apart, and the longest stretch without one below x is much longer: about the square of log x, if the primes behave like random numbers with the right density. Sieving to thirty million finds twenty-four record gaps, all climbing in the shape of that square and all below it. A random model of the primes gets the scale right and the details wrong, and the correction for what it gets wrong predicts gaps larger still — larger than any anyone has found.

The symmetric graphs no tour can close

Take the words of five places with two ones and join two when they share no one. The ten words look exactly alike to the graph, and no closed tour runs through them — because every way of leaving out one edge at each word leaves two pentagons. Only four connected graphs this symmetric are known to fail like that, and nobody knows whether a fifth exists.

Matching when the arrivals are shuffled

An adversary who chooses the order in which applicants arrive can hold any fixed matching rule to half the best. Take the order away and let it be random, and the plainest rule of all — give each arrival its first free place in a fixed list — rises to 1 − 1/e, because shuffling the arrivals turns out to be exactly the trick RANKING plays with the places, seen from the other side. Shuffle both and the guarantee rises again, to somewhere between 0.696 and 0.727, and where in that interval it lies is not known.

A sum that forbids half the pairings

Put two 1s, two 2s, …, two ns in a row so that between the two ks there are exactly k other numbers. For n = 3 there is one way, 312132; for n = 4 one way; for n = 5 and 6 none at all, and the reason is a single sum — adding up the positions of every entry in two ways forces n(3n − 1)/2 to be even. A search confirms the count forbids nothing that exists and finds 26 arrangements at n = 7 and 108,144 at n = 12, but the sum is all anyone knows about why.

Every function is a tree with two marks

There are n to the n functions from n points to themselves, and n to the n − 2 trees on those points. André Joyal noticed in 1981 that the missing factor of n² is a choice of two points — a head and a tail — and that a function, read the right way, simply is a tree with a head and a tail. The reading turns Cayley's formula into one line and hands over a fact about random trees from the birthday problem.

Almost every tree can be turned over

Cayley's n^(n−2) counts trees with labels on their points. Take the labels off and the count has no formula, because a symmetric shape absorbs labellings: the star on seven points can be labelled only seven ways, the one asymmetric shape 5,040. The bookkeeping that reconciles the two counts says something unexpected — almost every tree, labelled or not, can be turned over onto itself, where almost every graph cannot.

Half the neighbours forces a tour

Deciding whether a graph has a closed tour through every point is one of the hardest problems computers are asked to solve. Gabriel Dirac found a condition that settles it in one glance: if every point is joined to at least half the others, a tour exists. The proof is a counting argument on a single path, it runs as an algorithm, and two small graphs show that the half cannot be lowered — while random graphs show how much stronger than necessary it is.

The boards a knight can tour

A knight can visit every square of a chessboard once and land a move from where it began. On a 5 × 5 board it cannot, on a 4 × 100 board it cannot, and on a 3 × 8 board it cannot, though on 3 × 10 it can in sixteen ways. Allen Schwenk found in 1991 the complete list of rectangles without a closed tour, and the reasons on it are of two kinds — a colouring that counts squares, and a second colouring that a tour would have to make agree with the first.

Signs that make a determinant count

Hall's theorem says whether a board can be covered by dominoes. How many ways it can be covered is a different question, and for a general graph a hopeless one — the count is a permanent, and nobody expects an efficient way to compute permanents. On a flat board it is a determinant. Put a minus sign on the vertical pairs in every second column and the thirty-six coverings of a four-by-four board stop cancelling and add up; the chessboard has 12,988,816. A hole in the board breaks the rule in a way a cut repairs, and on K₃,₃, which cannot be drawn flat, no choice among its 512 signings works at all.

The diamond that freezes its corners

A square board's domino tilings grow like 1.3385 choices per square. Arrange the same squares in a staircase-edged diamond and the count is exactly 2 to the n(n+1)/2 — only 1.1892 choices per square, at every size. The boundary has reached into the middle. Pick one of the diamond's tilings at random and the reason is visible: outside the circle inscribed in the diamond the dominoes are frozen into solid brickwork, and only inside it is the tiling free.

The roots every matching polynomial keeps real

Count a graph's matchings by size and make the counts the coefficients of a polynomial. On every one of 35,664 graphs tested, that polynomial has only real roots — a theorem of Heilmann and Lieb from 1972. Count independent sets instead and the roots wander off the axis on a growing share of graphs, but never on a graph without a claw, and matchings are the independent sets of a graph that never has one.

Log-concave with nothing to make it so

The chromatic polynomial of a graph counts its colourings, and its coefficients rise to one peak and fall, each squared at least the product of its neighbours. For a real-rooted polynomial that would be automatic. But by nine vertices fewer than one graph in twenty has only real chromatic roots, and the coefficients stay log-concave anyway — on every graph tested, and, by June Huh's theorem of 2012, on every graph there is.

How far apart two triangulations can be

Any triangulation of a polygon can be turned into any other by flipping one diagonal at a time. On an octagon seven flips always suffice; on a polygon with m vertices the worst case is 2m − 10 flips once m reaches thirteen, a value Sleator, Tarjan and Thurston proved with hyperbolic geometry in 1988. Breadth-first search over all 58,786 triangulations of the 13-gon finds the sixteen.

Pairs of trees that count planar maps

Give every flip of a triangulation a direction and the triangulations become an order, the Tamari lattice. Counting the pairs that are in order — 1, 3, 13, 68, 399, 2,530, 16,965, 118,668, 857,956 — gives 2(4n + 1)!/((n + 1)!(3n + 2)!), which is exactly Tutte's 1962 count of planar triangulations. Chapoton noticed the match in 2006; a pair of trees and a map on a sphere turn out to be the same thing.

No triangle, and four colours

A graph that contains four mutually joined points needs four colours. The converse looks obvious — a graph needing four colours should contain something like that — and it is false. Grötzsch's graph has eleven points, no three of them mutually joined, and needs four colours. Mycielski found a step that adds one colour to any graph without creating a triangle, so graphs with no triangle can need any number of colours, and their need is spread through the whole graph, with no part to point at.

How often a number can appear in Pascal's triangle

Every number bigger than one appears in Pascal's triangle at least twice, next to the 1 at each end of its own row. A few appear more often: 120 appears six times, and 3003 eight — as C(3003, 1), C(78, 2), C(15, 5) and C(14, 6), each twice. Counting every entry up to a million million finds seven numbers that appear more than four times and none that appear five, seven or more than eight. Whether any number appears ten times, or whether there is any limit at all, is unknown.

The dots a ball catches

Count the lattice points inside a ball and compare with its volume. In five dimensions the error is about the size of one spherical shell, and that is a theorem; in four a logarithm sneaks in; in three and two the true size of the error is unknown. The difficulty runs backwards because the arithmetic of sums of squares is most erratic when there are fewest squares to add.

Triangle-free, and two-sided eventually

Every graph with no triangle and the most edges possible is bipartite. Erdős, Kleitman and Rothschild proved that almost every triangle-free graph is bipartite too — and yet among the 246,348,115 triangle-free graphs on nine labelled vertices, fewer than half are. The share falls before it rises, and the reason is that small graphs are sparse.

How many shapes a tree can take

There are 262,144 labelled trees on eight points and only twenty-three shapes. Labels make counting easy — Cayley's nⁿ⁻² — and shapes make it hard, because a symmetric shape absorbs labellings. The count of shapes comes instead from a recurrence for trees with a root and a theorem of Richard Otter's for taking the root away: in every tree there is exactly one more class of points than of edges. Run to two hundred points, the counts grow like 0.535 × 2.9558ⁿ ÷ n^(5/2), and the same arithmetic counts the alkanes.

The forests a graph can hold

Count the sets of edges in a graph that contain no cycle, sorted by size, and the counts rise and fall in a single peak — more sharply peaked, John Mason conjectured in 1972, than the binomial coefficients with the same number of edges. On every graph with up to six points the strongest of his three inequalities holds, with equality exactly where cycles are too long to matter; on random graphs with nine points it holds with a margin of about one per cent. It was proved for every graph, and every matroid, in 2018.

Two arrows in and two out

An Eulerian circuit enters every point as often as it leaves, so it hands every edge an arrow with the arrows balanced at each point. Count those balanced orientations instead of the circuits and the question turns into the ice in a freezer: on the square grid, where every point has two arrows in and two out, there are about 1.5396 of them per point — Lieb's (4/3)^(3/2), against Pauling's guess of 1.5. Fix the walls of a square of ice and the count becomes 1, 2, 7, 42, 429, 7436: the alternating-sign matrices.

No graph is poorer in squares than chance

Take any graph with a fixed share of its possible edges and count how often four points chosen in order close up into a ring. However the edges are arranged — in cliques, in two-sided blocks, at random — the count never falls below what a random graph of the same density gives. Sidorenko conjectured that the same holds for every pattern without an odd cycle. For a triangle it is false; for a path or a ring of four it takes two lines; for K₅,₅ with a ten-cycle removed nobody knows.