A lecture by Noga


Noga with Uri Feige among various other heroes

A few weeks ago I devoted a post to the 240-summit conference for Péter Frankl, Zoltán Füredi, Ervin Győri and János Pach, and today I will bring you the slides of Noga Alon’s lecture in the meeting. Noga is my genious twin academic brother – we both were graduate students under the supervision of Micha A. Perles in the same years and we both went to MIT as postocs in fall 1983.  The lecture starts with briefly mentioning four results by the birthday boys related to combinatorics and geometry and continues with recent startling results by Alon, Ankur Moitra, and Benny Sudakov. One out of many contributions of Noga over the years is building a large infrastructure of constructions and examples, often very surprising,  in combinatorics, graph theory, information theory,TOC, and related areas. And the new results add to this infrastructure. The slides are very clear. Enjoy!






Extremal Combinatorics VI: The Frankl-Wilson Theorem


Rick Wilson

The Frankl-Wilson theorem is a remarkable theorem with many amazing applications. It has several proofs, all based on linear algebra methods (also referred to as dimension arguments). The original proof is based on a careful study of incidence matrices for families of sets. Another proof by Alon, Babai and Suzuki applies the “polynomial method”. I will describe here one variant of the theorem that we will use in connection with the Borsuk Conjecture (It follows a paper by A. Nilli).  I will post separately about more general versions, the origin of the result, and various applications. One application about the maximum volume of spherical sets not containing a pair of orthogonal vectors is presented in the next post.

Let n=4p and suppose that p is a prime.

Theorem: Let \cal F be a subset of \{-1,1\}^n with the property that no two vectors in \cal F are orthogonal. Then |{\cal F}| \le 4({{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}}).

We will prove a slightly modified version which easily implies the Theorem as we stated it before:

Let \cal G be the set of vectors (x_1,x_2,\dots,x_n) in \{-1,1\}^n such that x_1=1 and the number of ‘1’ coordinates is even.  Let \cal F be a subset of \cal G with the property that no two vectors in \cal F are orthogonal. Then |{\cal F}| \le {{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}}.


The ad-hoc trick:

Claim 1: Let x,y\in {\cal G}. If <x,y>=0(mod~p) then <x,y>=0. Continue reading

Combinatorics, Mathematics, Academics, Polemics, …

1. About:

My name is Gil Kalai and I am a mathematician working mainly in the field of Combinatorics.  Within combinatorics, I work mainly on geometric combinatorics and the study of convex polytopes and related objects, and on the analysis of Boolean functions and related matters. I am a professor at the Institute of Mathematics at the Hebrew University of Jerusalem and also have a  long-term visiting position at the departments of Computer Science and Mathematics at Yale University, New Haven.  








 Gosset polytope- a hand drawing by Peter McMullen of the plane projection of the 8-dimensional 4-simplicial 4-simple Gosset polytope. Continue reading