Recent Comments

Recent Posts
 Questions and Concerns About Google’s Quantum Supremacy Claim
 Physics Related News: Israel Joining CERN, Pugwash and Global Zero, The Replication Crisis, and MAX the Damon.
 Test your intuition 52: Can you predict the ratios of ones?
 Amnon Shashua’s lecture at Reichman University: A Deep Dive into LLMs and their Future Impact.
 Mathematics (mainly combinatorics) related matters: A lot of activity.
 Alef Corner: Deep Learning 2020, 2030, 2040
 Some Problems
 Critical Times in Israel: Last Night’s Demonstrations
 An Aperiodic Monotile
Top Posts & Pages
 Questions and Concerns About Google’s Quantum Supremacy Claim
 An Aperiodic Monotile
 Test your intuition 52: Can you predict the ratios of ones?
 A Mysterious Duality Relation for 4dimensional Polytopes.
 TYI 30: Expected number of Dice throws
 The Simplex, the Cyclic polytope, the Positroidron, the Amplituhedron, and Beyond
 A Nice Example Related to the Frankl Conjecture
 Quantum Computers: A Brief Assessment of Progress in the Past Decade
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
RSS
Tag Archives: Extremal combinatorics
Extremal Combinatorics V: POSETS
This is the remaining post V on partially ordered sets of my series on extremal combinatorics (I,II,III,IV,VI). We will talk here about POSETS – partially ordered sets. The study of order is very important in many areas of mathematics starting … Continue reading
Analysis of Boolean Functions – week 1
Home page of the course. In the first lecture I defined the discrete ndimensional cube and Boolean functions. Then I moved to discuss five problems in extremal combinatorics dealing with intersecting families of sets. 1) The largest possible intersecting family … Continue reading
Cap Sets, Sunflowers, and Matrix Multiplication
This post follows a recent paper On sunflowers and matrix multiplication by Noga Alon, Amir Spilka, and Christopher Umens (ASU11) which rely on an earlier paper Grouptheoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans (CKSU05), … Continue reading
Extremal Combinatorics on Permutations
We talked about extremal problems for set systems: collections of subsets of an element sets, – Sperner’s theorem, the ErdosKoRado theorem, and quite a few more. (See here, here and here.) What happens when we consider collections of permutations rather than … Continue reading
Posted in Combinatorics
Tagged David Ellis, Ehud Friedgut, ErdosKoRado theorem, Extremal combinatorics, Haran Pilpel, Permutations
9 Comments
FranklRodl’s Theorem and Variations on the Cap Set Problem: A Recent Research Project with Roy Meshulam (A)
Voita Rodl I would like to tell you about a research project in progress with Roy Meshulam. (We started it in the summer, but then moved to other things; so far there are interesting insights, and perhaps problems, but not substantial … Continue reading
Posted in Combinatorics, Open problems
Tagged Cap sets, Extremal combinatorics, Intersection theorems, polymath1
11 Comments
Lovasz’s Two Families Theorem
Laci and Kati This is the first of a few posts which are spinoffs of the extremal combinatorics series, especially of part III. Here we talk about Lovasz’s geometric two families theorem. 1. Lovasz’s two families theorem Here … Continue reading
Posted in Combinatorics, Convexity, Open problems
Tagged exterior algebras, Extremal combinatorics, Laci Lovasz, shellability
7 Comments
Extremal Combinatorics IV: Shifting
Compression We describe now a nice proof technique called “shifting” or “compression” and mention a few more problems. The SauerShelah Lemma: Let . Recall that a family shatters a set if for every there is such that … Continue reading
Extremal Combinatorics III: Some Basic Theorems
. Shattering Let us return to extremal problems for families of sets and describe several basic theorems and basic open problems. In the next part we will discuss a nice proof technique called “shifting” or “compression.” The SauerShelah (Perles VapnikChervonenkis) Lemma: (Here we write .) … Continue reading
Extremal Combinatorics II: Some Geometry and Number Theory
Extremal problems in additive number theory Our first lecture dealt with extremal problems for families of sets. In this lecture we will consider extremal problems for sets of real numbers, and for geometric configurations in planar Euclidean geometry. Problem I: Given a set A of … Continue reading
Local Events, Turan’s Problem and Limits of Graphs and Hypergraphs
I will write a little about how hectic things are now here at HU, and make two (somewhat related) followups on previous posts: Tell you about Turan’s problem, and about Balázs Szegedi’s lecture from Marburg dealing with limits of graphs and hypergraphs. Local Events … Continue reading
Posted in Combinatorics, Open problems
Tagged Extremal combinatorics, Graph limits, Quasirandomness, Turan's problem
4 Comments