ICM 2018 Rio (4): Huh; Balog & Morris; Wormald

 

This is my fourth report from ICM2018. (I plan one more.)  As I already mentioned, Combinatorics  was very nicely represented at ICM2018.  The combinatorics session itself was great, and there were quite a few other sessions and other lectures related to combinatorics. I also met quite a few combinatorialists. As I mentioned in my ICM 2010 post, one thing that I enjoyed was to unexpectedly meet some old friends and this also happened in Rio (maybe a little less compared to Hyderabad as I learned to expect the unexpected). I also had an irrational expectation to unexpectedly meet the same people that I met unexpectedly in India. It was a pleasure meeting  Tadeusz Januszkiewicz again   but I was irrationally disappointed not to bump again into Oriol Serra and Anna Llado whom I had met  by surprise in Hyderabad.

This post will be about the Monday afternoon Session in combinatorics. Let me mention that the ICM 2018 You Tube channel now contains high quality videos for plenary and invited talks (as well as discussion panels, public lectures, and various other activities). This is a valuable resource! Here is the combinatorics session playlist, and the CS session, and the probability and statistics session, and the plenary lectures, and the public lectures. Also, here is the most recent version of my ICM paper THREE PUZZLES ON MATHEMATICS, COMPUTATION, AND GAMES. Last minute corrections and comments are most welcome.

Monday’s afternoon combinatorics

The Monday afternoon combinatorics session featured three lectures that knocked my socks off. The talks were great and I was in a perfect position to enjoy them as I knew something about the problems and some related results  and yet each lecture surprised me.  The three talks were Combinatorial applications of the Hodge–Riemann relations by June Huh, The method of hypergraph containers by József Balogh & Robert Morris,  Asymptotic enumeration of graphs with given degree sequence by Nicholas Wormald. Bella Bollobas chaired the session and gave a very nice and thoughtful introduction to each of the four speakers.

 

June Huh, and the Lefschetz package in combinatorics

June Huh: The standard conjectures are both ubiquitous and fundamental

Combinatorial applications of the Hodge–Riemann relations

June Huh talked about a mysterious package of conjectures (PD), (HL) and (HR), referred to as the standard conjectures,  for certain algebras associated with geometric and combinatorial objects. PD stands for the Poincare Duality, and it asserts that certain vector spaces A_i and A_{d-i} are dual. HD stands for Hard Lefschetz and it asserts that certain linear maps \phi_k from A_k to A_k+1  have the property that their composition from A_i all the way to A_{d-i} is an injection. (HR) stands for Hodge Riemann relations. (PD) and (HD) imply that a certain bilinear form  is nondegenerate and (HR) is a stronger statement that this form is definite!

June started with some startling applications of the Hard-Lefschetz theorem in combinatorics pioneered by Stanley. He then mentioned a startling new application with Wang: Consider n points spanning a d-dimensional space.  Let w_i be the number of flats of dimension k spanned by the point.  Motzkin  conjectured in 1936 and proved over the reals that  w_1 \le w_d. The planar case follows from the classic Erdos deBruijn theorem. Hu and Wang used {HL} to prove w_i \le w_d-i, i \le [d/2] which was conjectured by Dowling and Wilson.

Next came applications of (HR), starting with Huh’s proof of the log concavity of coefficients of chromatic polynomials for graphs (Read conjecture ) and the far-reaching extension by Adiprasito-Huh-Kats to general matroids (Rota’s conjecture). We mentioned the Adiprasito-Huh-Katz solution of the Rota-Heron conjecture in the previous post and in this one.

Here is the link to the ICM paper by June Huh: Combinatorial applications of the Hodge-Riemann relations.

 

József Balogh and Rob Morris and the container method

The method of hypergraph containers

The container theorem for hypergraphs is one of the most important tools in extremal combinatorics with many applications also to random graphs and hypergraphs, additive combinatorics, discrete geometry, and more.

Rob Morris explained the container theorem for triangle-free graphs. It asserts that there is a collection \cal C of graphs on n vertices with the following three properties:

(1) Every graph in the collection contains o(n^3) triangles,

(2) The number of graphs in the collection is n^{C \cdot 3/2},

(3) Each triangle free graph is contained in a graph in the collection.

Rob explained the origins of this theorem, how it follows from a container theorem for 3-uniform hypergraphs,   and how the later extends to the very general and important container theorem for k-uniform hypergraphs that was achieved in 2012 independently by Saxton and Thomason (Here is the link to their paper), and by Balogh, Morris, and Samotij (Here is a link to their paper).

Jozsef Balogh described two consequences of the container theorem to additive combinatorics and to discrete geometry. Let me describe the result in discrete geometry by Balogh and Solymosi. The (4,3) problem ask for the size $\alpha (n)$ of the largest subset of points in general position (no three on a line) that can always be found in a planar configuration of n points with the property that no four points lie on a line. The container method is used to show (surprisingly!) that \alpha(n)=n^{5/6+o(1)} .

For a recent beautiful application to (p,q)-Helly type theorems see A new lower bound on Hadwiger-Debrunner numbers in the plane by Chaya Keller and Shakhar Smorodinsky.

Here is a link to the ICM survey paper: The method of hypergraph containers, by József Balogh, Robert Morris, and Wojciech Samotij

(In a previous post  Midrasha Mathematicae #18: In And Around Combinatorics, we gave links to a series of lectures Wojiech Samotij: Toward the hypergraph “container” theorem (4 lectures) Video 1, video 2 video 3 video 4.)

Nick Wormald and counting regular graphs.

Asymptotic enumeration of graphs with given degree sequence

How many k-regular graphs are there? This is a very central problem in combinatorics and Nick Wormald was quite interested in its solution ever since his Ph. D.  The talk describes the early history of the problem, the early works by Wormald and McKay from the 90s,  the recent breakthrough by Antia Liebenau and Nick Wormald,  the techniques involved in the old and new proofs and some related results.

A good place to start is with Read’s 1958 formula for the number g_3(n) of 3-regular graphs with n labelled vertices

g_3(n) \sim (3n)! e^{-2}/(3n/2)!288^{n/2}.

Following an important model of Bollobas for creating regular graphs, general formulas were developed for low degrees, By McKay, McKay and Wormald, and others that depend on the probability of a random graph in Bollobas’ model to be simple. (See pictures below). Some results were proven also for the high degree regime and McKay and Wormald gave in 1990 and 1997 unified conjectural formulas for the number of d-regular graphs for a wide range of parameters. Moreover these conjectures extend to a large range of vectors of degree sequences.

In 2017 Anita Liebenau and Nick Wormald proved all these conjectures!!! (Here is a link to the paper.)

The formula for the behavior of the number of d-regular graphs with n vertices is remarkably elegant

e^{1/4}\sqrt{2}d^d(n-1-d)^{n-1-d}(n-1)^{-(n-1)}{{n-1} \choose {d}}^n.

The full result is very general, and the method extends further in various directions.

Here is the link to paper: Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph, by Anita Liebenau and Nick Wormald.

A bit psychedelic pictures

    

With Nick Wormald and Yoshi Kohayakawa just before my lecture.

Some important pictures from the Session

Bela Bollobas

Bela Bollobas served as the session chair

Nick Wormald on enumeration of regular graphs

Read’s formula and Bollobas model.

Formulas by McKay and McKay-Wormald (above and below)

General conjectures (above and below)

The Theorem by Liebenau and Wormald (above and below)

 

Balogh and Morris on containers

The Container theorem for triangle-free graphs

The hypergraph container theorem for 3-uniform hypergraphs

The hypergraph container theorem in full generality.

 

An application for the number of subsets of integers without k-term arithmetic progressions.

What was known and expected on the (4,3) problem (above) and the new breakthrough (below)

 

 

Applications of the container method

June Huh on the standard conjectures

Five seemingly unrelated mathematical objects

 

Poincare duality (PD), Hard Lefschetz (HL), and Hodge Riemann (HR).

A 1964 letter from Serre to Grothendieck on young Bombieri

The algebraic setting for the standard conjectures. 

Five cases were the standard conjectures are known and the original open case.

Advertisements
This entry was posted in Combinatorics, ICM2018 and tagged , , , , , . Bookmark the permalink.

2 Responses to ICM 2018 Rio (4): Huh; Balog & Morris; Wormald

  1. Pingback: Amazing: Karim Adiprasito proved the g-conjecture for spheres! | Combinatorics and more

Leave a Reply

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

WordPress.com Logo

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

Google+ photo

You are commenting using your Google+ 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