Some mathematical news

Combinatorics and more 2024-11-29

Prologue (Anton Kapustin): Arnold at the gym

A story about the mathematical experience as told by Anton Kapustin (over Facebook):

While working out at the gym I was thinking about Kolmogorov-Arnold-Moser theory and whether it has a quantum analog. Suddenly I heard a guy say, “This was Arnold’s favorite exercise!” It took me several seconds to realize he meant a different Arnold.

2arnold

Arnold (left) and a different Arnold (right). The different Arnold from Anton’s story may well be different from both.

In this post we will mention eight recent papers: 1) Reconstructing a Shellable Sphere from its Facet-Ridge Graph, by Yirong Yang; 2) Face Numbers of Shellable CW Balls and Spheres, by Joshua Hinman; 3) A short proof of the existence of designs, by Peter Keevash; 4) Reasonable Bounds for Combinatorial Lines of Length Three, by Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer; 5) Improved bounds for the Furstenberg-Sárközy theorem, by Ben Green, and Mehtaab Sawhney; 6) q-deformed rationals and q-continued fractions, by Sophie Morier-Genoud and Valentin Ovsienk; 7) A new approach to strong convergence, by Chi-Fang Chen, Jorge Garza-Vargas, Joel A. Tropp, Ramon van Handel; 8) The Aldous–Lyons Conjecture I: Subgroup Tests, by Lewis Bowen, Michael Chapman, Alexander Lubotzky, Thomas Vidick.

I. Reconstruction of polytopes and spheres

Reconstructing a Shellable Sphere from its Facet-Ridge Graph, by Yirong Yang

Abstract: We show that the facet-ridge graph of a shellable simplicial sphere Δ uniquely determines the entire combinatorial structure of Δ. This generalizes the celebrated result due to Blind and Mani (1987), and Kalai (1988) on reconstructing simple polytopes from their graphs. Our proof utilizes the notions of good acyclic orientations from Kalai’s proof as well as k-systems introduced by Joswig, Kaibel, and Körner.

My commentary: A central open problem about triangulated spheres is the conjecture that the dual graph (also known as the facet-ridge graph and the puzzle) of a simplicial sphere determines its full combinatorial structure. For simplicial polytopes this was proved by Blind and Mani in 1987 and I gave a simple proof in 1988. My proof applied to a restricted class of shellable simplicial spheres and now Yang proved it to all shellable spheres. I wrote about the problem in this 2009 post.

II. Bárány’s conjecture for strong CW complexes

Face Numbers of Shellable CW Balls and Spheres, by Joshua Hinman

Imre Bárány posed in the late 1990s the following question:

For a $d$ -dimensional polytope $P$ and every $k$ , $0 \le k \le d-1$ , is it true that $f_k(P) \ge \min (f_0(P),f_{d-1}(P))$ ?

Two years ago Hinman proved the conjecture (and some stronger inequalities) for polytopes and his proof strongly used metric properties and especially a result of Perles and Shephard about angles sums of convex polytopes. (See also this post.) Now Hinman goes on to extend his 2022 result to shellable strongly regular spheres. Also here, removing the condition of shellability would be interesting. Hindman also discusses some connections with the strong upper bound conjecture for polytopes and more general cellular objects.

III. A simpler proof for the existence of designs

A short proof of the existence of designs, by Peter Keevash

Abstract: We give a new proof of the existence of designs, which is much shorter and gives better bounds.

We wrote about earlier breakthroughs about designs here (2014), here(2016), here (2018) and here (2015). The new proof may come close to the ultimate test for a mathematical proof: To make it to the classroom.

IV. Reasonable bounds for DHJ[3]

Reasonable Bounds for Combinatorial Lines of Length Three, by Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer

Abstract (slightly shortened): We prove that any subset $A \subseteq [3]^n$ with $3^{-n}|A| \ge (\log \log \log \log n)^{-c}$ contains a combinatorial line of length 3. This improves on the previous best bound of $3^{-n}|A|\ge \Omega ((\log ^*n)^{-1/2})$ of [D.H.J. Polymath, Ann. of Math. 2012]

My commentary: Amey Bhangale, Subhash Khot, and Dor Minzer are involved in a long term project (now joined by Yang P. Liu) primarily addressing approximability of satisfiable constraint satisfaction problems that have interesting applications to additive combinatorics. We mentioned some of their earlier results in this post. DHJ[3] was the goal of the first polymath project and I hope that there will be a detailed DHJ post devoted to the new paper. In Polymath1 an ultra-optimistic conjecture for the best DHJ[3] bound was made.

V. Guaranteeing a square difference

Improved bounds for the Furstenberg-Sárközy theorem, Ben Green, and Mehtaab Sawhney

Abstract: Suppose that $A \subset \{1,2,\dots,n\}$ has no two elements differing by a square. Then $|A| \ll N e^{-(\log N)^c}$ for any $c < \frac {1}{4}$ .

From the paper: “The proof of Theorem 1.2 makes very substantial use of the results and ideas in a paper of Keller, Lifshitz and Marcus concerning global hypercontractivity in product spaces. This is the culmination of body of work, of which we mention in particular the earlier work of Keevash-Lifshitz-Long-Minzer. We remark in our context, a “local” function is one which strongly correlates with an arithmetic progression with common difference which is a product of “few” elements of Q. A global function by contrast does not correlate strongly with such functions. “

We discussed global hypercontractive inequalities in this post and this one (both posts were authored by Noam Lifshitz). The very recent sharp global hypercontractive inequalities of Keller, Lifshitz and Marcus turned out to be useful for various applications in extremal combinatorics.

VI. q-analogs for the rational and real numbers

q-deformed rationals and q-continued fractions, by Sophie Morier-Genoud and Valentin Ovsienko

Abstract: We introduce a notion of q-deformed rational numbers and q-deformed continued fractions. A q-deformed rational is encoded by a triangulation of a polygon and can be computed recursively. The recursive formula is analogous to the q-deformed Pascal identitiy for the Gaussian binomial coefficients, but the Pascal triangle is replaced by the Farey graph. The coefficients of the polynomials defining the q-rational count quiver subrepresentations of the maximal indecomposable representation of the graph dual to the triangulation. Several other properties, such as total positivity properties, q-deformation of the Farey graph, matrix presentations and q-continuants are given, as well as a relation to the Jones polynomial of rational knots.

My commentary: q-analogs is a central theme in enumerative combinatorics and in other areas of mathematics. Now, the q-analog of an integer $n$ is $[n]=1+q+q^2+\cdots+q^{n-1}$ . Sophie Morier-Genoud and Valentin Ovsienko used continued fractions to find q-analogs $[m/n]$ for rational numbers (that can be extended also to the reals). Two examples from the paper are:

$\displaystyle [\frac 52] = \frac {1+2q+q^2+q^3}{1+q}~$ and $\displaystyle ~[\frac 53] = \frac {1+q+2q^2+q^3}{1+q+q^2}$

VII. A new approach to strong convergence

A new approach to strong convergence, Chi-Fang Chen, Jorge Garza-Vargas, Joel A. Tropp, Ramon van Handel

From the abstract: “… strong convergence is notoriously difficult to prove and has generally required delicate problem-specific methods. In this paper, we develop a new approach to strong convergence that uses only soft arguments.”

From the paper:

” We obtain a new proof of Friedman’s theorem on the second eigenvalue of random regular graphs that enables a sharp characterization of the tail behavior of the second eigenvalue. As a byproduct, our results settle several open problems on the behavior of random regular graphs.
We obtain a nonasymptotic form of the strong convergence of random permutation matrices due to Bordenave and Collins [7, 8], which significantly improves the best known convergence rate for arbitrary polynomials.
We establish strong convergence of random matrices defined by any stable representation of the symmetric group (in the sense of [25]). This provides a large new family of examples of the strong convergence phenomenon, and illustrates that strong convergence arises in settings far beyond the standard representation.”

We discussed Charles Bordenaves new simple proof of Friedman’s second eigenvalue Theorem (Alon’s conjecture) and its extension to random lifts, in this 2015 post.

VIII. The Aldous-Lyons conjecture

The Aldous–Lyons Conjecture I: Subgroup Tests, by Lewis Bowen, Michael Chapman, Alexander Lubotzky, Thomas Vidick.

From the abstract: “This paper, and its companion [BCV24], are devoted to a negative resolution of the Aldous–Lyons Conjecture [AL07, Ald07]. This conjecture, originated in probability theory, is well known (cf. [Gel18]) to be equivalent to the statement that every invariant random subgroup of the free group is co-sofic. We disprove this last statement.

… By composing this correspondence with a stronger variant of the reduction in MIP*=RE [JNV+21], proved in the companion paper [BCV24], we deduce that approximating the sofic value of a subgroup test is as hard as the Halting Problem, and in particular, undecidable. The combination of our two main results proves the existence of non co-sofic invariant random subgroups of the free group.”

We discussed the MIP*=RE result and the connection to group theory in this post.

Figures and formulas