Some old and new problems in combinatorics and geometry


Paul Erdős in Jerusalem, 1933  1993

I just came back from a great Erdős Centennial conference in wonderful Budapest. I gave a lecture on old and new problems (mainly) in combinatorics and geometry (here are the slides), where I presented twenty problems, here they are:

Around Borsuk’s Problem

Let f(d) be the smallest integer so that every set of diameter one in R^d can be covered by f(d) sets of smaller diameter. Borsuk conjectured that f(d) \le d+1.

It is known (Kahn and Kalai, 1993) that : f(d) \ge 1.2^{\sqrt d}and also that (Schramm, 1989) f(d) \le (\sqrt{3/2}+o(1))^d.

Problem 1: Is f(d) exponential in d?

Problem 2: What is the smallest dimension for which Borsuk’s conjecture is false?

Volume of sets of constant width in high dimensions

Problem 3: Let us denote the volume of the n-ball of radius 1/2 by V_n.

Question (Oded Schramm): Is there some \epsilon >0 so that for every n>1 there exist a set K_n of constant width 1 in dimension n whose volume satisfies VOL(K_n) \le (1-\epsilon)^n V_n.

Around Tverberg’s theorem

Tverberg’s Theorem states the following: Let x_1,x_2,\dots, x_m be points in R^d with m \ge (r-1)(d+1)+1Then there is a partition S_1,S_2,\dots, S_r of \{1,2,\dots,m\} such that  \cap _{j=1}^rconv (x_i: i \in S_j) \ne \emptyset.

Problem 4:  Let t(d,r,k) be the smallest integer such that given m points  x_1,x_2,\dots, x_m in R^d, m \ge t(d,r,k) there exists a partition S_1,S_2,\dots, S_r of \{1,2,\dots,m\} such that every k among the convex hulls conv (x_i: i \in S_j), j=1,2,\dots,r  have a point in common.

Reay’s “relaxed Tverberg conjecture” asserts that that whenever k >1 (and k \le r), t(d,r,k)= (d+1)(r-1)+1.

Problem 5: For a set A, denote by T_r(A) those points in R^d which belong to the convex hull of r pairwise disjoint subsets of X. We call these points Tverberg points of order r.

Conjecture: For every A \subset R^d , \sum_{r=1}^{|A|} {\rm dim} T_r(A) \ge 0.

Note that \dim \emptyset = -1.

Problem 6:   How many points T(d;s,t) in R^d guarantee that they can be divided into two parts so that every union of s convex sets containing the first part has a non empty intersection with every union of t convex sets containing the second part.

A question about directed graphs

Problem 7: Let G be a directed graph with n vertices and 2n-2 edges. When can you divide your set of edges into two trees T_1 and T_2 (so far we disregard the orientation of edges,) so that when you reverse the directions of all edges in T_2 you get a strongly connected digraph.

Erdős-Ko-Rado theorem meets Catalan

Problem 8 

Conjecture: Let \cal C be a collection of triangulations of an n-gon so that every two triangulations in \cal C share a diagonal.  Then |{\cal C}| is at most the number of triangulations of an (n-1)-gon.

F ≤ 4E

Problem 9: Let K be a two-dimensional simplicial complex and suppose that K can be embedded in R^4. Denote by E the number of edges of K and by F the number of 2-faces of K.

Conjecture:  4E

A weaker version which is also widely open and very interesting is: For some absolute constant C C E.

Polynomial Hirsch

Problem 10:  The diameter of graphs of d-polytopes with n facets is bounded above by a polynomial in d and n.

Analysis – Fixed points

Problem 11: Let K be a convex body in R^d. (Say, a ball, say a cube…) For which classes \cal C of functions, every f \in {\cal C} which takes K into itself admits a fixed point in K.

Number theory – infinitely many primes in sparse sets

Problem 12: Find a (not extremely artificial) set A of integers so that for every n, |A\cap [n]| \le n^{0.499}where you can prove that A contains infinitely many primes.

Möbius randomness for sparse sets

Problem 13: Find a (not extremely artificial) set A of integers so that for every n, |A\cap [n]| \le n^{0.499} where you can prove that

\sum \{\mu(k): k \le n, k \in A\} = o(|A \cap [n]).

Computation – noisy game of life

Problem 14: Does a noisy version of Conway’s game of life support universal computation?

Ramsey for polytopes

Problem 15: 

Conjecture: For a fixed k, every d-polytope of sufficiently high dimension contains a k-face which is either a simplex or a (combinatorial) cube.

Expectation thresholds and thresholds

Problem 16: Consider a random graph G in G(n,p) and the graph property: G contains a copy of a specific graph H. (Note: H depends on n; a motivating example: H is a Hamiltonian cycle.) Let q be the minimal value for which the expected number of copies of H’ in G in G(n,q) is at least 1/2 for every subgraph H’ of H. Let p be the value for which the probability that G in G(n,p) contains a copy of H is 1/2.

Conjecture: [Kahn – Kalai 2006]  p/q = O( log n)


Problem 17: Let X be a family of subsets of [n]=\{1,2,\dots,n\}.
How large X is needed to be so that the restriction (trace) of X to some set B \subset [n]|B|=(1/2+\delta)n has at least 3/4 \cdot 2^{|B|} elements?


Problem 18: Let  P  be a property of graphs. Let \cal G be a collection of graphs with n vertices so that the symmetric difference of two graphs in \cal G has property PHow large can \cal G be.

Conditions for colorability

Problem 19: A conjecture by Roy Meshulam and me:

There is a constant C such that every graph G
with no induced cycles of order divisible by 3 is colorable by C colors.

Problem 20:

Another conjecture by Roy Meshulam and me: For every b>0 there
is a constant C=C(b) with the following property:

Let G be a graph such that for all its induced subgraphs H

The number of independent sets of odd size minus the number of independent sets of even size is between -b  and b.

Then G is colorable by C(b) colors.


The title of the lecture is borrowed from several papers and talks by Erdős. Continue reading

Erdős’ Birthday

erdos-warsawPaul Erdős was born on March 26, 1913 2013 a hundred years ago. This picture (from Ehud Friedgut’s homepage) was taken in September ’96 in a Chinese restaurant in Warsaw, a few days before Paul Erdős passed away. The other diners are Svante Janson, Tomasz Łuczack and Ehud Friedgut. Erdős’ influence is felt everywhere in combinatorics, mathematics as a whole, and this blog as well. (A few more links: my most decorated MO answer is about Erdős, a recent heated discussion on the “two cultures in mathematics,” a new post on Erdős discrepancy problem on GLL,  and, most important, a link to Erdős centennial conference, in Budapest July 1-5, 2013. Join the celebration!)

Do not hesitate to contribute a comment!

Extremal Combinatorics I: Extremal Problems on Set Systems

The “basic notion seminar” is an initiative of David Kazhdan who joined HU math department  around 2000. People give series of lectures about basic mathematics (or not so basic at times). Usually, speakers do not talk about their own research and not even always about their field. I gave two lecture series, one about “computational complexity theory” a couple of years ago, and one about extremal combinatorics or Erdös-type combinatorics a few months ago, which later I expanded to a series of five+one talks at Yale. One talk was on  the Borsuk Conjecture,  which I will discuss separately, and five were titled: “Extremal Combinatorics: A working tool in mathematics and computer science.”  Let me try blogging about it. The first talk was devoted to extremal problems concerning systems of sets.



 Paul Erdös

1. Three warm up problems

Here is how we move very quickly from very easy problems to very hard problems with a similar flavour.

Problem I: Let  N = {1,2, … , n } . What is the largest size of a family \cal F  of subsets of N such that every two sets in \cal F have non empty intersection? (Such a family is called intersecting.)

Continue reading