Jean

Jean Bourgain and Joram Lindenstrauss.

I was very sad to hear that Jean Bourgain, among the greatest mathematicians of our time, and a dear friend, passed away.  I first met Jean about forty years ago and later we have become friends and collaborators.  In the 80s and 90s Jean used to visit Israel quite often and had close collaboration with the Banach space Israeli community, and with the Ergodic theory community,  and with the Harmonic analysis community, and the PDE community, and later also with the combinatorics, probability,  algebra, number theory,  and theoretical computer science communities.  I always admired his immense mathematical powers and his deep devotion to mathematics.

You can read about Jean Bourgain in Terry Tao’s beautiful obituary post.  I was also moved by Svetlana Jitomirskaya’s beautiful facebook post. Some of Jean’s contributions to combinatorics (which formed a small portion of his interests) are mentioned in several posts over my blog (and my lecture below). I will try to come back to these mathematical topics at a later post and here I post a few pictures of Jean over the years. Here is the moving IAS obituary notice. See also Ryan O’Donnell’s moving comment. And here is a MathOverflow question Jean Bourgains relatively lesser known significant contributions. (Added later:) Here is a beautiful tribute on GLL for Jean Bourgain and Michael Atiya. Let me also add a link to the moving obituary post of Terry Tao on Elias Stein.

 

My 2016 lecture “Questions for Jean Bourgain” about questions that I (and some colleagues) asked Jean Bourgain over the years, mainly in the areas of combinatorics and combinatorial aspects of convexity.

Continue reading

Advertisements
Posted in Algebra and Number Theory, Analysis, Combinatorics, Computer Science and Optimization, Convexity, Obituary | Tagged | 4 Comments

Amazing: Karim Adiprasito proved the g-conjecture for spheres!

Karim in his youth with a fan

Congratulations, Karim!

Update: Here is the link to the paper

From the arXive, Dec 26, 2018. (Link will be added tomorrow.)

COMBINATORIAL LEFSCHETZ THEOREMS BEYOND POSITIVITY

by Karim Adiprasito

Abstract: Consider a simplicial complex that allows for an embedding into \mathbb R^d. How many faces of dimension d/2 or higher can it have? How dense can they be?

This basic question goes back to Descartes. Using it and other fundamental combinatorial
problems, we will introduce a version of the Kähler package beyond positivity,
allowing us to prove the Lefschetz theorem for toric varieties even when the ample
cone is empty. A particular focus lies on replacing the Hodge-Riemann relations by a
non-degeneracy relation at torus-invariant subspaces, allowing us to state and prove a
generalization of the theorems of Hall and Laman in the setting of toric varieties. Of
the many applications, we highlight two main applications, one because it is the most
well-known, the other because it provided the most guiding light.

(1) We fully characterize the possible face numbers of simplicial spheres, resolving the
so called g-conjecture of McMullen in full generality and generalizing Stanley’s
earlier proof for simplicial polytopes.

(2) We prove that for a simplicial complex K that embeds into \mathbb R^{2d}, the number of d-dimensional simplices exceeds the number of (d − 1)-dimensional simplices by a factor of at most d + 2. This generalizes a result of Descartes, and resolves the Grünbaum-Kalai-Sarkaria conjecture.

_______

(GK:) A few further comments. Probably the g-conjecture for spheres is the single problem I knock my head against the most. It is great to see it settled and it is even greater to see it settled by my friend and colleague Karim Adiprasito.

To the three ingredients of the standard conjectures (See also the previous post), Poincare duality (PD), Hard Lefschetz (HL) and Hodge-Riemann (HR), Karim adds the Hall-Laman relations. Very roughly, the Hall-Laman relations  substitute (HR) and apply genericity (rather than definiteness) toward (HL).

(We still need a good acronym for Hall-Laman, maybe (AHL).)

One very nice feature of Karim’s proof is that vertex decomposable spheres play a special role in the path toward the proof. Those were introduced by Provan and Billera in the context of the Hirsch conjecture.

We have devoted plenty of posts to the g-conjecture for spheres, and mentioned it in even more posts.  For an introduction to the conjecture see Eran Nevo introductory post, and the post How the g-Conjecture Came About. There is also plenty left to be done beyond the g-conjecture.

Merry X-mas and Happy new year 2019 to all our readers.

Posted in Combinatorics, Updates | Tagged , | 8 Comments

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.

Posted in Combinatorics, ICM2018 | Tagged , , , , , | 2 Comments

Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant Solved the Mihail-Vazirani Conjecture for Matroids!

 

Milena+Umesh
Milena Mihail and Umesh Vazirani

I thank Nati Linial, Dan Spielman and Karim Adiprasito for sharing the news with me.

The Mihail-Vazirani conjecture for matroids and Feder-Mihail’s theorem

Consider a collection X of n vectors. A basis is a subset of X of linearly independent vectors that span the subspace spanned by X.  We can define a graph whose vertices are all bases and two bases are adjacent if their symmetric difference has two elements. Mihail and Vazirani conjectured that for every set Y of vertices in this graph the number of edges between Y to its complement \bar Y is at least \min (|Y| |,\bar Y|).

If X consists of the elements of the standard basis in \mathbb R^d and their negatives then the graph we obtain is the graph of the discrete n dimensional discrete cube and the assertion of the Mihail-Vazirani conjecture is well known.

The Mihail-Vazirani conjecture was formulated (and has now been proved) for arbitrary matroids. Think about a matroid as a collection K of subsets (the independent sets of the matroid) of some ground set X that closed under taking subsets (hence a simplicial complex) with the following property: For every Y \subset X, the induced simplicial complex on Y denoted by K(Y)  is pure. In other words, for every Y \subset X, all maximal independent subsets of Y have the same cardinality.

In a pioneering 1992 paper Tomás Feder and Milena Mihail proved the conjecture for balanced matroids.

Mihail and Vazirani conjecture for 0-1 polytopes.

An even more general conjecture by Mihail and Vazirani is still open. It asserts that for every 0-1 polytope, for every set Y of vertices, the number of edges between Y to its complement \bar Y is at least \min (|Y|, |\bar Y|).

The new breakthrough

Here is the link to the paper.

Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid by Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant

Let me mention another paper by a subset of the authors on related questions, another paper by Brändén and Huh, who independently proved the strong log-concavity of several of the polynomials appeared in the ALOV  paper, and are be several forthcoming papers by these two groups.

Here is the abstract: We design an FPRAS to count the number of bases of any matroid given by an independent set oracle, and to estimate the partition function of the random cluster model of any matroid in the regime where 0<q<1. Consequently, we can sample random spanning forests in a graph and (approximately) compute the reliability polynomial of any matroid. We also prove the thirty year old conjecture of Mihail and Vazirani that the bases exchange graph of any matroid has expansion at least 1. One of our key observations is a close connection between pure simplicial complexes and multiaffine homogeneous polynomials. Specifically, if X is a pure simplicial complex with positive weights on its maximal faces, we can associate with X a multiaffine homogeneous polynomial p_X such that the eigenvalues of the localized random walks on X correspond to the eigenvalues of the Hessian of derivatives of p_X.

Spectral negative dependence and Hodge-Riemann

A key paragraph regarding the method is the following:

“Our approach has a close connection to the original plan of Feder and Mihail (1992) who used the negative correlation property of balanced matroids to show that the bases exchange walk mixes rapidly. Unfortunately, most interesting matroids do not satisfy negative correlation. But it was observed [AKH18; HW16; AOV18] that all matroids satisfy a spectral negative dependence property.” AKH18 (a typo, it should be AHK18) is the solution for the Rota-Heron conjecture by Adiprasito, Huh and Katz that relies on the Hodge-Riemann property for matroids that we mentioned in this post. (I still feel in debt for a more detailed blog post about Adiprasito, Huh and Katz’ breakthrough!).”

I think that high dimensional expanders and random walks on them also plays a role in the new development.

Update: Related very recent papers

Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids

Authors: Nima Anari, Shayan Oveis Gharan, Cynthia Vinzant

Log-Concave Polynomials III: Mason’s Ultra-Log-Concavity Conjecture for Independent Sets of Matroids

Authors: Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant

Hodge-Riemann relations for Potts model partition functions

Authors: Petter Brändén, June Huh

Correlation bounds for fields and matroids

Authors: June Huh, Benjamin Schröter, Botong Wang

Posted in Combinatorics, Computer Science and Optimization, Updates | Tagged , , , , , , | 7 Comments

Igor Pak will give the 2018 Erdős Lectures

 

Next week Igor Pak will give the 2018 Erdős Lectures (delayed from June)

Here is the poster

 

Combinatorics — Erdos lecture: Igor Pak (UCLA) “Counting linear extensions”

Monday December 10  11:00-13:00

Location:  IIAS Hall 130, Feldman building,  Givat Ram

 

 

I will survey various known and recent results on counting the number of linear extensions of finite posets. I will emphasize the asymptotic and complexity aspects for special families, where the problem is especially elegant yet remains #P-complete.

CS Theory — Erdős Lecture: Igor Pak (UCLA) “Counting Young tableaux”

Wednesday, Dec. 12,  2018, 10:30am to 12:00pm

Location: Rothberg (CS building) B-220

The number of standard Young tableaux of skew shape is a mesmerizing special case of the number of linear extensions of posets, that is important for applications in representation theory and algebraic geometry.  In this case there is a determinant formula, but finding their asymptotics is a difficult challenge.  I will survey some of the many beautiful result on the subject, explain some surprising product formulas, connections to Selberg integral, lozenge tilings and certain particle systems.

Colloquium: Erdos lecture – Igor Pak (UCLA) “Counting integer points in polytopes”

Thursday,  Dec 13, 2018 2:30pm to 3:30pm

Location: Manchester Building (Hall 2), Hebrew University Jerusalem

Given a convex polytope P, what is the number of integer points in P? This problem is of great interest in combinatorics and discrete geometry, with many important applications ranging from integer programming to statistics. From a computational point of view it is hopeless in any dimensions, as the knapsack problem is a special case. Perhaps surprisingly, in bounded dimension the problem becomes tractable. How far can one go? Can one count points in projections of P, finite intersections of such projections, etc.?

Posted in Combinatorics, Computer Science and Optimization, Updates | Tagged , , | Leave a comment

PCP fest, Tel Aviv University, 18-20 December 2018

Conference web site

The study of Probabilistically Checkable Proofs, starting with the discovery of the PCP Theorem, is a cornerstone of modern computer science, with impact on complexity theory, algorithms, and cryptography. Born as a purely theoretical notion, mostly used to prove hardness of approximation results, PCPs are now becoming a widely deployed tool in blockchain platforms. The workshop will touch the past, the state of the art, and future of PCPs. Topics will include: hardness of approximation, PCPs in cryptography and blockchains, no-signaling PCPs, PCPs in P, and Boolean function analysis.

Confirmed speakers:

Boaz Barak, Shafi Goldwasser, Eli Ben Sasson, Gil Kalai, Yael Kalai, Guy Kindler, Elchanan Mossel, Christos Papadimitriou, Aviad Rubinstein, Ran Raz, Ronitt Rubinfeld, Oded Schwartz, Irit Dinur, Andrew Yao, and Avi Wigderson.

Organizers:

Nir Bitansky, Esty Kelman, Subhash Khot, Dor Minzer, and Muli Safra

Posted in Combinatorics, Computer Science and Optimization, Conferences, Updates | Tagged | Leave a comment

Exciting Beginning-of-the-Year Activities and Seminars.

Let me mention two talks with very promising news by friends of the blog, Karim Adiprasito and Noam Lifshitz. As always, with the beginning of the academic year there are a lot of exciting activities,  things are rather hectic around,  and I hear a lot of exciting things (both news and things I was supposed to know long ago). I am quite sure that we will return to the topics of the two lectures in later posts and I also welcome discussing them in the comment section. (A few related older posts for Karim’s talk and seminar: F ≤ 4E;  Beyond the g-conjecture.   and for Noam’s seminar: Influence, Threshold and NoiseBoolean functions: Influence, threshold and noise;  .)

Karim Adiprasito’s colloquium talks and course

HUJI Thu, 25/10/2018 – 14:30 to 15:30; TAU 29/10/2018 12:15-13:15

Combinatorics, topology and the standard conjectures beyond positivity

Abstract: Consider a simplicial complex that allows for an embedding into \mathbb R^d. How many faces of dimension d/2 or higher can it have? How dense can they be? This basic question goes back to Descartes. Using it and other rather fundamental combinatorial problems, I will motivate and introduce a version of Grothendieck’s “standard conjectures” beyond positivity (which will be explored in detail in the Sunday Seminar). All notions used will be explained in the talk (I will make an effort to be very elementary)

Sunday’s seminar refer to a HUJI Kazhdan seminar given by Karim on this topic. (3-5 Ross building’s seminar room.)  This is a good opportunity to congratulate Karim Adiprasito and June Huh on receiving the New Horizon Prize, and congratulations also to Vincent Lafforgue who received the breakthrough prize and to all the other winners!

Noam Lifshitz’ combinatorics seminar

When: Monday Oct.29, 11:00–12:45
Where: Rothberg CS building, room B500, Safra campus, Givat Ram

Sharp thresholds for sparse functions with applications to extremal combinatorics. (based on a joint work by Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer.)

Abstract:
The sharp threshold phenomenon is a central topic of research in the analysis of Boolean functions. Here, one aims to give sufficient conditions for a monotone Boolean function f to satisfy\mu_p(f)=o(\mu_q(f)), where q = p + o(p), and \mu_p(f) is the probability that f=1 on an input with independent coordinates, each taking the value 1 with probability p.

The dense regime, where \mu_p(f)=\Theta(1), is somewhat understood due to seminal works by Bourgain, Friedgut, Hatami, and Kalai. On the other hand, the sparse regime where \mu_p(f)=o(1) was out of reach of the available methods. However, the potential power of the sparse regime was suggested by Kahn and Kalai already in 2006.

In this talk we show that if a monotone Boolean function f with \mu_p(f)=o(1) satisfies some mild pseudo-randomness conditions then it exhibits a sharp threshold in the interval [p,q], with q = p+o(p). More specifically, our mild pseudo-randomness hypothesis is that the p-biased measure of f does not bump up to Θ(1) whenever we restrict f to a sub-cube of constant co-dimension, and our conclusion is that we can find q=p+o(p), such that \mu_p(f)=o(\mu_q(f)).

At its core, this theorem stems from a novel hypercontactive theorem for Boolean functions satisfying pseudorandom conditions, which we call `small generalized influences’. This result takes on the role of the usual hypercontractivity theorem, but is significantly more effective in the regime where p = o(1).

We demonstrate the power of our sharp threshold result by reproving the recent breakthrough result of Frankl on the celebrated Erdos matching conjecture, and by proving conjectures of Huang–Loh–Sudakov and Furedi–Jiang for a new wide range of the parameters.

Alef: Koebe’s Karnaf

Posted in Combinatorics, Geometry, Probability | Tagged , , , , | Leave a comment

Aleph’s Corner: T-Shirts

The artist behind Aleph’s corner has now a website offering over 100 T-shirt designs. In addition to a few pictures related to  mathematics there are many in a few other categories: “Jazz,” “Urban,” “Nature,” “Signature design,” and “Sea”. Here are a few of my favorites

 

picaboo

 

 

C*

Continue reading

Posted in Art, Combinatorics | Tagged | Leave a comment

ICM 2018 Rio (3) – Coifman, Goldstein, Kronheimer and Mrowka, and the Four Color Theorem

This post is my third report from ICM 2018. You may remember that I had planned to live-blog on the last four days of the congress but on Monday evening I realized that this was an unrealistic task and decided instead to blog only on a single day – Monday. A little later I realized this was also unrealistic and decided to limit my blogging to a single  lecture  by Peter Kronheimer and Tomasz Mrowka on Knots, three-manifolds and instantons.  But in the end I did not live-blog at all and in this post I will briefly described Tuesday’s morning lectures and give a belated report on Peter and Tomasz’s lecture. I actually arrived in Rio very early  on Saturday morning and attended many talks on Saturday, but  this was not part of my planned blogging  and I was relaxed and did not take lecture notes. Sunday was a day off and I had a great time with friends.

I greatly enjoyed all of Monday’s morning lectures. The first very inspiring lecture by my friend and colleague Rafi (Ronald) Coifman was entitled Harmonic analytic geometry in high dimensions – Empirical models (click for the video). Rafi’s research spans across a wide range of areas many of which he himself created and goes from the very applied (e.g., applications of harmonic analysis to pluming, biology, and finance) to the very pure (e.g., applications of wavelets to classical problems in harmonic analysis). The lecture covered a lot of ground, starting with Fourier’s original ideas and his perception that he had discovered the “language of nature” and continuing  with wide applications to structural and multi-scale analysis of high dimensional data, and to the possibility, pushing Fourier’s vision one step further,  of automatically learning the laws of physics from data.

Toward the third lecture on the history of mathematics by Catherine Goldstein I thought that I could relax and listen to a historical lecture that does not require much mathematical efforts. To my surprise, it was very demanding for me (but fully worth the effort) to follow the mathematics itself.  The historical discussion and insights were great. The title of the lecture was Long-term history and ephemeral configurations  (click for the video) and it started with a famous quote of Poincaré: Mathematics is the art of giving the same name to different things (Poincaré gave the examples of “groups” and “uniform convergence”.)  At the center of the talk was Charles Hermite and the lecture dealt, among other things,  with the very interesting question: Is mathematics a natural science? For Hermite the answer was: Yes! Altogether there were a lot of great insights and great lines. (Pictures from these two lectures at the end of the post.)

Kronheimer and Mrowka: Knots, three-manifolds and instantons

Knots, three manifolds and instantons

The talk was fantastic, it had great results, the slides were great, the presentation was great, thoughtful, with a lot of food for thought, both for the large audience and (I think) also for experts. A main famous theorem by the speakers is:

Theorem: Knots with vanishing Instanton Floer homology and (therefore) also knots with trivial Khovanov’s homology are unknots.

Khovanov’s homology are invariants of groups that refine the famous Jones polynomials and, of course, two problems naturally arise. First, is it the case that the Jones polynomial itself determines unknots? (This is a famous open problem.) And also does Khovanov’s homology or Floer’s homology distinguish different knots? (Maybe the answer for the second bold question is known to be negative…)  The lecture had four parts

Part I (Tomasz): knots, Papakyriakopoulos, and the main theorem.

I was surprised that I had the feeling that I understood everything in the first part. It started with a quick pictorial introduction to what knots are, then looking at the complement of a knot, followed by Dehn’s lemma that was proved by Papakyriakopoulos. (I think but am not sure that Papakyriakopoulos’s proof is still needed for all the stronger results that follow.)

  

So Papakyriakopoulos’ theorem tells you that the fundamental group of the complement of a non-trivial knot is not Abelian, but could we say something stronger? Peter mentioned that for most, but not all non-trivial small knots  the fundamental group maps onto a dihedral group. And the main result is that for all non trivial knots the fundamental group maps onto SO (3). There were two delicate yet important points that were mentioned.  The first is that often SO(3) can or should be replaced by its double cover SU(2), and the second is that there is also a crucial condition (that makes the theorem stronger) about the images of “meridians” (small circles around a point on the knot in its complement).

Part II (Peter): Floer’s instanton homology and many mathematical ideas and tools

The second part was about ideas, notions and tools needed for the proof of the main theorem. Naturally it was more difficult and for various things I only just pleasantly got a general impression together with some pointers on notions that I should (finally) learn. Connections, flat connections, Chern-Simons functionals, Young-Mills equations and their solutions called “instantons”, and the Floer’s (instanton) homology, …  .  As you can see from the fourth slide the list of tools that are actually needed for the proof extends even further and Peter and Tomasz also mentioned connections with Ozsváth and Szabo theory of Heegard Floer homology.

 

 

Part III (Tomasz): Khovanov homology, and skein relations

Surprisingly, the third part dealt with notions that were somewhat easier for me than those of the second part. The Khovanov homology is a refinement of another famous knot-invariant the  Jones polynomial.

  

I remember hearing a few talks about Khovanov homology in the early 2000. Dror Bar Nathan showed how they appear very naturally and how it is a straight forward matter to compute them (alas, not efficiently). In a different talk some years later David Kazhdan showed how, taking a different point of view, those invariants depend on a sequence of amazing miracles.   In any case, the Khovanov homology groups are finite dimensional and the Jones polynomial are just the alternating sums of their dimensions (or Euler characteristics). Like the Jones polynomial themselves there is also some connection (“skein relations“) between the Khovanov homologies of knots when you apply two simple operations on the knots.

 

The skein relations for Khovanov homology are given in terms of a long exact sequence, and similar relations hold for the Floer homology. Moreover there is some relation (a spectral sequence) between these two exact sequences which shows that when Khovanov homology  is not trivial then  Floer (instanton) homology is also non trivial and hence from what we already know about Floer homology the knot is not trivial.

and when part IV came I expected that the discussion will be aimed at real experts in the audience and that I could relax and think about other things. However this was not the case. Below the fold I will tell you about the surprising fourth part, and then proceed to talk about various other really interesting things. Statistics tell me that only about a third of the readers read below the fold but this time I truly recommend it.

Continue reading

Posted in Combinatorics, Geometry, ICM2018 | Tagged , , , | 2 Comments

Ricky and Branko

Two dear friends, and great geometers, Ricky Pollack and Branko Grünbaum  passed away a few weeks ago. Ricky was a close friend that both Mazi my wife and I loved, and we were both fascinated by his wisdom, charm and love of life. Branko was my academic grand father and I met him through his writings many years before I had the privilege and pleasure to meet in person.  Here are some pictures of Ricky and Branko. (If you have more, send me and I will add them.)

In future posts I will tell you a little about their mathematics. See also these posts about stories and math related to Ricky ( A Discrepancy Problem for Planar Configurations;  Many triangulated three-spheres!; Academic Degrees and Sex; GLL: Polls and prediction and P=NP . ) and to Branko ( My Copy of Branko Grünbaum’s Convex Polytopes; The World of Michael Burt: When Architecture, Mathematics, and Art meet; Coloring Simple Polytopes and Triangulations; Budapest, Seattle, New Haven ; How the g-Conjecture Came About; GLL: What are proofs for , anyway.) (Links for blog posts on other blogs are welcome.)

 

    

 

Branko with Janos Pach

The legendary mathematical partnership and friendship of Ricky and Eli Goodman is rare in mathematics.

Five generations in Seattle: Branko was the advisor of Micha A Perles (and also of Joram Lindenstrauss, Moshe Rosenfeld, Joseph Zaks and many others). Micha was my advisor (and also of  Meir Katchalski, Michael Kallay, Nati Linial Noga Alon and many others). Isabella Novik was my student and here we are with four student of Isabella: Michael Goff,  Kurt Luoto,  Andy Frohmaderand, and Steven Klee. (From left to right.)

 

Saugata Basu, Ricky Pollack and  Marie-Francois Roy’s  book Algorithms in real algebraic geometry.

   

Posted in Combinatorics, Convexity, Geometry, Obituary | Tagged , | 3 Comments