Archive
Concise functions and spanning trees
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:
- 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).
- 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).
- 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 = ∪ An. 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 Z2 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 ∈ An 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 ∈ R2 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 Cn < g(T) <Dn. 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)!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) < 6n. 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.
The power of negative thinking: Combinatorial and geometric inequalities
It’s been awhile since I blogged about mathematics. You know why, of course — there are so many issues in the real world, the imaginary world is just not as relevant as it used to be. Well, at least that’s how I felt until now. But the latest paper we wrote with Swee Hong Chan was so much fun (and took so much effort), the wait is over. There is also some interesting backstory before we can state the result.
What is the inverse problem in Enumerative Combinatorics?
Before focusing on combinatorics, note that inverse problems are everywhere in mathematics. Sometimes they are obvious and stated as such, and sometimes we are so used to these problems we don’t think of them as inverse problems at all. You are probably thinking of major problems (both solved and unsolved), like the inverse Galois problem, Cauchy problem, Minkowski problem or the Alexandrov existence theorem. But really, even prime factorization, integration, taking logs and subtraction can be viewed this way. As I said — they are everywhere.
In Enumerative Combinatorics, a typical problem goes like this: given some set A, find the number N:=|A|. Finding a combinatorial interpretation is an inverse problem: given N, find A such that N=|A|. This might seem silly to an untrained eye: obviously, every nonnegative integer counts something. But it is completely normal to have constraints on the type of solution that you want — this case is no different.
Indeed, if you think about it, the direct problem is not all that well-defined either. For example, do you want an asymptotics or just some kind of bounds on N? Or maybe you want a closed formula? But what is a closed formula? Does it have to be a product formula, or some kind of summation will work? Can it be a multisum with both positive and negative terms? Or maybe you are ok with a closed formula for the generating function in case A=UAn? But what exactly is a closed formula for a GF? The list of questions goes on.
Five years ago, I discussed various different answers to these question in my ICM paper, with ideas goes back to Wilf’s beautiful paper (see also Stanley’s answer). If anything, the answers are not short and sometimes technical. Although my formulations are well-defined, positive results can be hard to prove, while negative results can be really hard to prove. Such is life, I suppose.
So what exactly is a combinatorial interpretation?
It is easy to go philosophical (as Rota does or I do on somewhat broader questions), but let’s focus on math here. I started thinking about the problem when I came to UCLA over twelve years ago, and struggled to find a good answer. I discussed the problem in my Notices paper when I finally made peace with the computational complexity approach. Of the multiple definitions, there is only one that is both convincing, workable and broad enough:
Combinatorial interpretation = #P
I explain the answer in my lengthy OPAC survey on the subject, and in my somewhat entertaining OPAC talk (slides). I have miles to say about this, maybe some other time.
To understand why I case, it’s worth thinking of the origin of the problem. Say, you have an inequality a ≥ b between number of certain combinatorial objects, where a=|A|, b=|B|. If you have a nice explicit injection φ : B → A, this gives a combinatorial interpretation for the defect (a–b) as the number of elements in A without a preimage. If φ and its inverse are computable in polynomial time, this shows that (a–b) counts the number of objects which can be certified to be correct in polynomial time. Thus, the definition of #P.
Now, as always happens in these cases, the reason for the definition is not to give a positive answer (“you know it when you see it” was a guiding principle for a long time), but to give a negative answer. What if many of these combinatorial interpretation problems Stanley discusses in his famous survey simply don’t have a solution? (see my OPAC survey linked above, and this MO discussion for the state of art).
To list my favorite open problem, do Kronecker coefficients g(λ,μ,ν) have a combinatorial interpretation? I don’t believe so, but to give a negative answer we need a definition. There is just no way around it. Note that we already have g(λ,μ,ν)= a(λ,μ,ν) – b(λ,μ,ν) for some numbers of combinatorial objects a and b (formally, these are #P functions). It is the injection that doesn’t seem to work. But why not?
Unfortunately, the universe of “not in #P” results is very small and includes only this FOCS paper with Christian Ikenmeyer and this SODA paper with Christian Ikenmeyer and Greta Panova. Simply put, such results are rare and hard to prove. Let me not explain them, but rather turn in the direction of my current work.
Poset inequalities
Since the inequalities like g(λ,μ,ν) ≥ 0 are so unapproachable in full generality, some four years ago I turned to inequalities on the number of linear extensions of finite posets. Many such inequalities are known in the literature, e.g. the XYZ inequality, the Sidorenko inequality, the Björner–Wachs inequality, etc. It is unclear whether the defect of the XYZ inequality has a combinatorial interpretation, but the other two certainly do (see our “Effective poset inequalities” paper with Swee Hong Chan and Greta Panova).
What we found most interesting and challenging, is the following remarkable Stanley’s inequality on the log-concavity of the number of certain linear extensions:
(this is a slide from my 2021 talk). In a remarkable breakthrough, Stanley resolved the Chung-Fishburn-Graham conjecture using the Alexandrov–Fenchel inequality (more on this later). What I was interesting in the following problem: Is the defect of Stanley’s inequality N(k)^2-N(k-1) N(k+1) in #P? This is still an open problem, and we don’t have tools to resolve it.
It gets worse: in an effort to show that this inequality is in #P, two years ago we introduced a whole new technology of combinatorial atlas. We used this technology to prove a lot new inequalities in this paper with Swee Hong Chan, including multivariate extensions of Stanley inequalities and correlation inequalities. We now know why this technology was never going to apply to the #P problem, but that’s all yet another story.
What we did in our new paper is attacked a similar problem for the generalized Stanley inequality, which has the same statement but with additional constraints that L(xi)=ci for all 1 ≤ i ≤ m, where xi are fixed poset elements and ci are fixed integers. Stanley derived the log-concavity of these more general numbers from the AF inequality in one big swoosh. In our paper, we prove:
Corollary 1.5. The defect of the generalized Stanley inequality is not in #P, for all m ≥ 2 (unless PH collapses to a finite level).
Curiously, in addition to a lot of poset theoretic technology we are using the Yao-Knuth theorem in number theory. Our main result is stronger:
Theorem 1.3. The equality cases of the generalized Stanley inequality are not in PH, for all m ≥ 2 (unless PH collapses to a finite level).
Clearly, if the defect was in #P, then the “defect =? 0″ is in coNP, and the “not in #P” result follows. The complexity theoretic idea of the proof is distilled in our companion paper where we explain why the coincidence problem for domino tilings in R3 is not in PH, and the same holds for many other hard combinatorial problems.
This underscores both the strength and the weakness of our approach. On the one hand, we prove a stronger result than we wanted. On the other hand, for m=0 it is known that the equality cases of the generalized Stanley inequality are in P. This is a remarkable result of Shenfeld and van Handel (actually, a consequence of the their remarkable theory). In fact, we reprove and generalize the result in our combinatorial atlas paper. In the new paper, we prove the m=1 version of this result, using a (also remarkable) followup paper by Ma and Shenfeld. We conjecture that m=2, the defect is already not in #P (Conjecture 10.2), but there seem to be difficult number theoretic obstacles to the proof.
In summary, we now know for sure that the defect of the generalized Stanley inequality does not have a combinatorial interpretation. In particular, there is no direct injective proof similar to that for the Sidorenko inequality, for example (cf. this old blog post). If you are deeply engaged with the subject (and why would you be, obviously?), you are happy. But if not — you probably shrug. Let me now explain why you should still care.
Geometric inequalities
It is rare when when you can honestly say this, but the geometric inequalities really do go back to antiquity (see e.g. here and there), when the isoperimetric inequality in the plane was first discovered. Of the numerous inequalities that followed, note the Brunn–Minkowski inequality and the Minkowski quadratic inequality (MQI) for three convex bodies in R3. These are all consequences of the Alexandrov–Fenchel inequality mentioned above. However, when it comes to equality conditions there is a bit of wrinkle.
For the isoperimetric inequality in the plane, the equality cases are obvious (discs), and there is an interesting history of proofs by symmetrization. For the BM inequality, the equality cases are homothetic convex bodies, but the proof is very far from obvious and requires the mixed volume machinery. For the MQI, the equality conditions were know only in some special cases, and resolved in full generality only recently by Shenfeld and van Handel.
For the AF inequality, the effort to understand the equality conditions goes back to A. D. Alexandrov, who found equality conditions in some cases:
Serious difficulties occur in determining the conditions for equality to hold in the general inequalities just derived. [Alexandrov, 1937]
In 1985, Rolf Schneider formulated a workable conjecture on the equality conditions, which remains out of reach in full generality. He made a strong case for the importance of the problem:
As [AF inequality] represents a classical inequality of fundamental importance and with many applications, the identification of the equality cases is a problem of intrinsic geometric interest. Without its solution, the Brunn–Minkowski theory of mixed volumes remains in an uncompleted state. [Schneider, 1994]
In the remarkable paper mentioned above, Shenfeld and van Handel resolved several special cases of the conjecture. Notably, they gave a complete characterization of the equality conditions for convex polytopes, in a sense of extracting all geometry from the problem, and stating the condition in terms of equality of certain mixed volumes. This is where we come in.
Equality cases of the AF inequality are not in PH
To understand the way Stanley derived his inequality from the AF inequality, it’s worth first explaining the connection to log-concavity:
Stanley considered sections P, Q of the order polytope associated with a given poset and concluded log-concavity for the numbers N(k) via a simple calculation.
Now, our “not in PH” theorem on the equality cases of Stanley’s inequality and this Stanley’s calculation imply that equality cases of the AF inequality are also not in PH (under the same complexity assumptions plus computational setup on how the polytopes are presented). In some sense, this says that the equality cases of the AF inequality can never be fully described, or at least the description by Shenfeld and van Handel is probably the best one can do.
In the spirit of the #P application, our result also implies, that there is unlikely to be a stability result for the AF inequality in full generality (in this sense), see Corollary 1.2 in the paper. Omitting precise statements and technicalities, let us only mention that Bonnesen’s inequality is a basic stability result which can be viewed as a sharp extension of the isoperimetric inequality, including the equality conditions. What we are saying is — don’t expect to ever see anything like that for the AF inequality (see the paper for details).
UPDATE (Feb. 7, 2024). The “m ≥ 6” was later improved to “m ≥ 2“, see our paper on the arXiv. See this video of my Oberwolfach talk on the subject. See also this blog post by Gil Kalai. Note: This paper was accepted to appear at STOC 2024.
UPDATE (Dec 26, 2024). The paper was published in Forum Math. Pi., see here.
Igor Pak's blog 
You must be logged in to post a comment.