Mathematical news to cheer you up


1.  Anna Kiesenhofer, a PhD mathematician researching PDEs at Ecole Polytechnique Federale Lausanne (EPFL), won the gold medal in the women’s bicycle road race at the Olympics.

Here are two trivia question: a) Which hero of a recent post over here is related to Kiesenhofer’s mathematical side? b) Name another famous connection between EPFL-mathematics and sport.

2. János Nagy and Péter Pál Pach proved the Alon-Jaeger-Tarsi conjecture via group ring identities

The abstract says it all: In this paper we resolve the Alon-Jaeger-Tarsi conjecture for sufficiently large primes. Namely, we show that for any finite field F of size 61<|F|79 and any nonsingular matrix M over F there exists a vector x such that neither x nor Ax has a 0 component.

3. Michael Simkin asymptotically solved the n-queens problem! (We mentioned this classic problem and earlier progress by Zur Luria in this post.)

Abstract: The n-queens problem is to determine {\mathcal Q}(n), the number of ways to place n mutually non-threatening queens on an n \times n board. We show that there exists a constant α=1.942±3×10-3 such that {\mathcal Q}(n)=((1 \pm o(1))n e ^{-\alpha})^n. The constant α is characterized as the solution to a convex optimization problem in {\mathcal P}([−1/2,1/2]2), the space of Borel probability measures on the square. The chief innovation is the introduction of limit objects for n-queens configurations, which we call “queenons”. These are a convex set in \mathcal P([−1/2,1/2]2). We define an entropy function that counts the number of n-queens configurations that approximate a given queenon. The upper bound uses the entropy method. For the lower bound we describe a randomized algorithm that constructs a configuration near a prespecified queen on and whose entropy matches that found in the upper bound. The enumeration of n-queens configurations is then obtained by maximizing the (concave) entropy function in the space of queenons. Along the way we prove a large deviations principle for n-queens configurations that can be used to study their typical structure.


Intermission: the sun over Tel Aviv sea

4. Boris Bukh demonstrated Extremal graphs without exponentially-small bicliques

Abstract: The Turán problem asks for the largest number of edges in an $latex n$-vertex graph not containing a fixed forbidden subgraph F. We construct a new family of graphs not containing K_{s,t}, for t=C^s, with  \Omega (n^{2-1/s}) edges matching the upper bound of Kövári, Sós and Turán. 

5. Michael Capalbo, Explicit 𝑁-vertex graphs with maximum degree 𝐾 and diameter [1+𝑜(1)]log𝐾-1 𝑁 for each 𝐾-1 a prime power,

Abstract:   Here we first present the solution of a long-standing open question–the explicit construction of an infinite family of N-vertex cubic graphs that have diameter [1+o(1)]log2 N. We then extend the techniques to construct, for each K of the form 2s+1 or K=ps+1; s an integer and p a prime, an infinite family of K-regular graphs on N vertices with diameter [1+o(1)]logK−1 N.

I missed this breakthrough in STOC 2019 but now it appeared in Combinatorica, and Nati told me about it.

6.  A beautiful survey article: Intersection Problems in Extremal Combinatorics: Theorems, Techniques and Questions Old and New, by David Ellis,

Abstract: The study of intersection problems in Extremal Combinatorics dates back perhaps to 1938, when Paul Erdős, Chao Ko and Richard Rado proved the (first) `Erdős-Ko-Rado theorem’ on the maximum possible size of an intersecting family of k-element subsets of a finite set. Since then, a plethora of results of a similar flavour have been proved, for a range of different mathematical structures, using a wide variety of different methods. Structures studied in this context have included families of vector subspaces, families of graphs, subsets of finite groups with given group actions, and of course uniform hypergraphs with stronger or weaker intersection conditions imposed. The methods used have included purely combinatorial ones such as shifting/compressions, algebraic methods (including linear-algebraic, Fourier analytic and representation-theoretic), and more recently, analytic, probabilistic and regularity-type methods. As well as being natural problems in their own right, intersection problems have connections with many other parts of Combinatorics and with Theoretical Computer Science (and indeed with many other parts of Mathematics), both through the results themselves, and the methods used. In this survey paper, we discuss both old and new results (and both old and new methods), in the field of intersection problems. Many interesting open problems remain; we will discuss several. For expositional and pedagogical purposes, we also take this opportunity to give slightly streamlined versions of proofs (due to others) of several classical results in the area. This survey is intended to be useful to PhD students, as well as to more established researchers. It is a personal perspective on the field, and is not intended to be exhaustive; we apologise for any omissions. It is an expanded version of a paper that will appear in the Proceedings of the 29th British Combinatorial Conference.

7.  An interview with me; interviewer Toufik Mansour.



This entry was posted in Combinatorics, Sport, Uncategorized, Updates. Bookmark the permalink.

5 Responses to Mathematical news to cheer you up

  1. Robert Rand says:

    Darn! I was sure 1b was Bettina Heim (of Q# fame, also former Swiss figure skating champion) but she got her PhD from Matthias Troyer at ETH.

    Well, a point for ETH in the rivalry.

  2. kodlu says:

    Thanks for this nice post. You switched from matrix M to matrix A in item 2, it seems.

  3. Pingback: Daily Bookmarks to GAVNet 08/04/2021 | Greener Acres Value Network News

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s