Igor Pak's blog

Is there anything new in Enumerative Combinatorics?  Most experts would tell you about some interesting new theorems, beautiful bijections, advanced techniques, connections to other areas, etc. Most outsiders would simply scoff, as in “what can possibly be new about a simple act of counting?” In fact, if you ask traditional combinatorialists they would be happy to tell you they they like their area to be trend-resistant. They wouldn’t use these words, obviously, but rather say something about timeless, or beautiful art, or “balls in boxes”. The following quote is a classic of this genre:

Combinatorialists use recurrence, generating functions, and such transformations as the Vandermonde convolution; others, to my horror, use contour integrals, differential equations, and other resources of mathematical analysis. (J. Riordan, Combinatorial identities, 1968)

If you’ve been reading this blog for a while, then you already know how I feel about such backward-looking views. When these win, the area becomes stale, isolated, and eventually ignored by both junior researchers and the “establishment” (leading math journals, granting agencies, etc.) Personally, I don’t I don’t see this happening in part due to the influence of Theoretical Computer Science (TCS) that I discussed back in 2012 in this blog post.

In fact, the influence of TCS is so great on all aspects of Combinatorics (and Mathematics in general), let me just list three ideas with the most impact on Enumerative Combinatorics:

1. Thinking of a “closed formula” for a combinatorial counting function as algorithm for computing the function, leading to Analysis of Algorithms type analysis (see Wilf’s pioneer article and my ICM paper).
2. The theory of #P-completeness (and related notions such as #P-hard, #EXP-complete, class GapP, etc.) explaining why various functions do not have closed formulas. This is now a core part of Computational Complexity (see e.g. Chapter 13 in this fun textbook).
3. The idea that a “combinatorial interpretation” is simply a function in #P. This is my main direction these days, see this blog post, this length survey and this OPAC talk and this StanleyFest talk.

All three brought remarkable changes in the way the community understands counting problems. In my own case, this led to many interesting question resulting in dozens on papers. Last year, in the middle of a technical complexity theoretic argument, I learned of a yet another very general direction which seem to have been overlooked. I will discuss it briefly in this blog post.

Complete functions

Let A be a set of combinatorial objects with a natural parametrization: A = ∪ A_n. For example, these can be graphs on n vertices, posets on n elements, regions in the square grid with n squares, etc. Let f: A → N be a function counting objects associated with A. Such functions can be, for example, the number of 3-colorings or the number of perfect matchings of a graph, the number of order ideals or the number of linear extensions of a poset, the number of domino tilings of a region, etc.

We say that f is complete if f(A)=N. Similarly, f is almost complete if f(A) contains all sufficiently large integers. For example, the number of perfect matchings of a simple graph is complete as can be seen from the following nice construction:

Moreover, the number of domino tilings of a region in Z² is complete since for every integer k, there is a staircase-type region like you see below with exactly k domino tilings (this was observed in 2014 by Philippe Nadeau).

In fact, most natural counting functions are either complete or almost complete. For example, the number of spanning trees of a simple graph is almost complete since the number of spanning trees in an n-cycle is exactly n, for all n>2. Similarly, the number of standard Young tableaux |SYT(λ)| of a partition λ is almost complete since |SYT(m,1)|=m. Many other natural examples are in our paper with Swee Hong Chan (SHC) which started this investigation.

Concise functions

Let f be an almost complete function. We say that f is concise if for all large enough k, there exist an element a ∈ A_n such that f(a) = k and n < C (log k)^c, for some C, c>0. Just like explicit constructions in the context of Graph Theory (made famous by expanders), this notion makes perfect sense irrespectively from our applications in computational complexity (see our paper with SHC linked above).

Note that none of the simple constructions mentioned above imply that the corresponding functions are concise. This is because the size of combinatorial objects is linear in each case, not poly-logarithmic as we need it to be. For the number of perfect matchings, an elegant construction by Brualdi and Newman (1965) shows that one can take n = O(log k). This is the oldest result that we know, that some natural combinatorial counting function is concise.

For the number of domino tilings, SHC and I proved an optimal bound: there is a region with O(log k) squares with exactly k domino tilings. The proof is entirely elementary, accessible to a High School student. The idea is to give explicit transformations k → 2k and k → 2k-1 using gadgets of the following kind:

As always, there are minor technical details in this construction, but the important takeaway is that we obtain an optimal bound, but the regions we construct are not simply-connected. For simply-connected regions the best bound we have is O(log k log log k) for the snake (ribbon) regions, via connection to continued fractions that was recently popularized by Schiffler. Whether one can obtain O(log k) bound in this case is an interesting open problem, see §6.4 in our paper with SHC.

Many concise functions

For the number of spanning trees, whether this function is concise remained an open problem for over 50 years. Even a sublinear bound was open. The problem was recently resolved by Stong in this beautiful paper, where he gave O((log k)^3/2/(log log k)) upper bound. Sedláček (1967) conjectured that o(log k) bound for general graphs, a conjecture which remains wide open.

For some functions, it is easy to see that they are not concise. For example, for a partition λ of n, the number of standard Young tableaux |SYT(λ)| is a divisor of n! Thus, for k prime, one cannot take n<k in this case.

Curiously, there exist functions, for which being almost complete and concise are equivalent notions. For example, let T ∈ R² be a set of n points in general positions in the plane. Denote by g(T) the number of triangulations of T. Is g almost complete? We don’t know but my guess is yes, see Conjecture 6.4 in our paper with SHC. However, we do know exponential lower and upper bounds Cⁿ < g(T) <Dⁿ. Thus, if g is almost complete it is automatically concise with an optimal O(log k) upper bound.

Our final example is much too amusing to be skipped. Let e(P) denote the number of linear extensions of a poset on n elements. This function generalized the number of standard Young tableaux, and appears in a number of applications (see our recent survey with SHC). Tenner proved a O(√k) bound, the first sublinear bound. The conciseness was shown recently by Kravitz and Sah, where they established O(log k log log k) upper bound. The authors conjectured O(log k) bound, but potentially even O((log k)/(log log k)) might hold.

Consider now a restriction of the function e to posets of height two. In our paper with SHC, we have Conjecture 5.17 which claims that such e is still almost complete. In other words, for all large enough k, one can find a poset of height two with exactly k linear extensions. Since the number of linear extensions of such posets is at least (n/2)!² this would give an optimal bound for general posets as well, so a very sharp extension of the Kravitz–Sah bound. We should mention an observation of Soukup (p. 80), that 13,168,189,439,999 is not the number of linear extensions of a height two poset. This suggests that our conjecture is either false, or likely to be very hard.

Latest news: back to spanning trees

In our most recent paper with Swee Hong Chan and Alex Kontorovich, we resolve one Sedláček’s question and advance another. We study the number τ(G) of spanning trees in a simple planar graph G on n vertices. This function τ is concise by Stong’s theorem (his construction is planar), and it is easy to show by planarity that τ(G) < 6ⁿ. Thus, a logarithmic upper bound O(log k) is the best one can hope for. Clearly, proving such result would be a major advancement over Stong’s poly-logarithmic bound.

While we don’t prove O(log k) bound, we do get very close — we prove that this bound holds for the set of integers k of density 1. The proof is both unusual (to me as a combinatorialist), and involves a mixture of graph theory, number theory, ergodic theory, and some pure luck. Notably, the paper used the remarkable Bourgain–Kontorovich technology developed towards the celebrated Zaremba’s Conjecture. You can read it all in the paper or this longish post by Alex.

P.S. Being stubborn and all, I remain opposed to the “unity of mathematics” philosophy (see this blog post which I wrote about the ICM before later events made it obsolete). But I do understand what people mean when they say these words — something like what happened in our paper with Alex and Swee Hong with its interdisciplinary tools and ideas. And yet, to me the paper is squarely in Combinatorics — we just use some funky non-combinatorial tools to get the result.