Category Archives: Combinatorics

The Cap-Set Problem and Frankl-Rodl Theorem (C)

Posted on May 18, 2009 by

Update: This is a third of three posts (part I, part II) proposing some extensions of the cap set problem and some connections with the Frankl Rodl theorem. Here is a post presenting the problem on Terry Tao’s blog (March 2007). Here … Continue reading →

Posted in Combinatorics, Open problems | Tagged , , | Leave a comment

Around the Cap-Set problem (B)

Posted on May 11, 2009 by

Part B: Finding special cap sets This is a second part in a 3-part series about variations on the cap set problem that I studied with Roy Meshulam. (The first post is here.)  I will use here a different notation than in part … Continue reading →

Posted in Combinatorics, Open problems | Tagged , , | 2 Comments

(Eran Nevo) The g-Conjecture II: The Commutative Algebra Connection

Posted on April 9, 2009 by

Richard Stanley This post is authored by Eran Nevo. (It is the second in a series of five posts.) The g-conjecture: the commutative algebra connection Let be a triangulation of a -dimensional sphere. Stanley’s idea was to associate with a ring … Continue reading →

Posted in Combinatorics, Convex polytopes, Open problems | Tagged , , , | 3 Comments

How the g-Conjecture Came About

Posted on April 4, 2009 by

This post complements Eran Nevo’s first  post on the -conjecture 1) Euler’s theorem Euler Euler’s famous formula for the numbers of vertices, edges and faces of a  polytope in space is the starting point of many mathematical stories. (Descartes came close … Continue reading →

Posted in Combinatorics, Convex polytopes, Open problems | Tagged , , , , | 4 Comments

(Eran Nevo) The g-Conjecture I

Posted on April 2, 2009 by

This post is authored by Eran Nevo. (It is the first in a series of five posts.) Peter McMullen The g-conjecture What are the possible face numbers of triangulations of spheres? There is only one zero-dimensional sphere and it consists … Continue reading →

Posted in Combinatorics, Convex polytopes, Guest blogger, Open problems | Tagged , , | 4 Comments

An Open Discussion and Polls: Around Roth’s Theorem

Posted on March 25, 2009 by

Suppose that  is a subset of of maximum cardinality not containing an arithmetic progression of length 3. Let . How does behave? We do not really know. Will it help talking about it? Can we somehow look beyond the horizon and try to guess what … Continue reading →

Posted in Combinatorics, Open discussion, Open problems | Tagged , , , | 24 Comments

A Beautiful Garden of Hypertrees

Posted on March 14, 2009 by

We had a series of posts (1,2,3,4) “from Helly to Cayley” on weighted enumeration of Q-acyclic simplicial complexes. The simplest case beyond  Cayley’s theorem were Q-acyclic complexes  with vertices, edges, and triangles. One example is the six-vertex triangulation of the … Continue reading →

Posted in Combinatorics | Tagged , | Leave a comment

Extremal Combinatorics on Permutations

Posted on March 13, 2009 by

  We talked about extremal problems for set systems: collections of subsets of an element sets, - Sperner’s theorem, the Erdos-Ko-Rado theorem, and quite a few more. (See here, here and here.) What happens when we consider collections of permutations rather … Continue reading →

Posted in Combinatorics | Tagged , , | 9 Comments

Polymath1: Success!

Posted on March 11, 2009 by

 “polymath” based on internet image search And here is a link to the current draft of the paper. Update:  March 26, the name of the post originally entitled “Polymath1: Probable Success!” was now updated to “Polymath1: Success!” It is now becoming … Continue reading →

Posted in Blogging, Combinatorics, What is Mathematics | Tagged , | 10 Comments

Noise Sensitivity Lecture and Tales

Posted on March 6, 2009 by

  A lecture about Noise sensitivity Several of my recent research projects are related to noise, and noise was also a topic of a recent somewhat philosophical post.   My oldest and perhaps most respectable noise-related project was the work with Itai Benjamini and Oded … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Probability | Tagged , , , , , , | 11 Comments