Just returning from a cozy two days discrete-math workshop in Marburg. A very nice mixture of participants and topics. The title of my talk was “Helly theorem, hypertrees and strange enumeration” and I plan to blog about it sometime soon. A few hours before taking off, Aner Shalev told me that a 1951 conjecture by Ore asserting that every element in a non abelian finite simple group is a commutator have just been proved by a group of four researchers – Aner himself and Liebeck, O’Brien and Tiep. (Ore himself proved that for every element is a commutator.) The basis for a very complicated inductive proof required computer works and the final OK came four hours before Aner gave a lecture about it!
The talks in Marburg were very interesting.
Day 1:Enumerative combinatorics techniques and results related to the asymptotic conjectured formula for the number of self avoiding random walks (a holy grail in statistical mechanics); Automated symbolic proofs for expressions involving harmonic series and complicated formulas from particle physics; Exponential lower bounds for the chromatic number of via the “linear programming method” (competing well with the bounds obtained by the “polynomial method”); Combinatorial commutative algebra related to powers of linear forms and refinements of the notion of Grobner bases for subalgebras; a proof that sufficiently many points in the plane contain an empty convex hexagons (this was an old open problem); An extension of Fleischner’s theorem asserting that the square of a 2-connected graph is Hamiltonian to infinite graphs (with a “correct” notion of Hamiltonian cycle).
Day 2: Understanding the structure and complexity of Lehman matrices – important combinatorial objects arising in the study of finite geometries, combinatorial optimization, and extremal combinatorics; Combinatorial and algorithmic problems arising in the study of wireless sensor networks; A mixture of probabilistic and enumerative techniques in the study of phase transition of random graphs and, in particular, random graphs with prescribed vertex degrees; A characterization of t-transitive designs and results regarding block transitive designs both answering long standing questions; What is the correct notion of limit of graphs and hypergraphs and some highlights and surprises from the emerging theory; Learning a small number of dominant variables in Boolean functions in the presence of noise and from multiple product distributions;
Interested in more details? following the links in the program to hompages can link you quickly to more relevant material. Also for a few of the lectures I can tell more.