Some old and new problems in combinatorics and geometry

Paul99

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)

Traces

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?

Graph-codes

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.

Remarks:

The title of the lecture is borrowed from several papers and talks by Erdős. (And I tried to imitate a little his lectures.)  The presentation give some more details on the twenty problems, and here are a few further comments. I devoted a few posts to questions around Borsuk’s problem (I, II, III), and an MO question for problem 3 on sets of constant width in high dimensions. I also devoted a post to questions around Tverberg’s theorem where problems 4 and 5 are mentioned. I asked problems 5 and 6 in the early 70′s. Problem 7 is motivated by a very special case of problem 5. Problem 8 is recent and was asked also on MO. Gjergji Zaimi (private communication) proposed a far-reaching extension:

Question: Let P be a convex polytope without triangular two dimsneional faces. Is it true that a collection of vertices so that every two of them belongs to a facet, has at most as many vertices as the largest facet?

Problem 9 which represents one of my current main research effort was asked by Sarkaria, me, and perhaps others in the late 80s. (See also this post.) Problem 10 was the subject of polymath 3 that started here. Problem 11 intrigued me since my undergraduate years, see this post, and I recalled it again after hearing a lecture by Haim Brezis. (See Haim’s publication list for some relevant papers with Bourgain,  Mironescu, Nguyen, and others.) Problems 12 and 13 are motivated by recent progress on Möbius randomness and on finding primes in various sets of integers, and also by this MO problem. Problem 14 was motivated by a lecture of Bollobas and by my general interest in fault-tolerance see this TCSoverfow problem and this MO problem. For open problems on polytopes including Problems 10, and 15 see this post.  Problems 16, 17 also represent one of my main current research efforts, see this paper with Jeff Kahn for problem 16 and this paper with Kahn on problem 17. (The best known very recent upper bound by Bourgain fot problem 17 is not yet published.)  Variants of problem 18 were raised by several other people (Körner, Katona, Gowers). Problems 19 and 20 are motivated by Helly-type questions and in particular by the fractional Helly property.

More comments: (The post was launched a day too early before it was completed, so let me add a few more comments.)

The solution of Borsuk’s problem was a very nice success to Erdős’ mathematics. It relies on the interplay between combinatorial and geometric structures. In fact, Erdős himself, Rogers, Danzer, and perhaps others suggested that combinatorial configurations will lead to counterexamples. Larman made a crucial step in translating the question from geometry to combinatorics. Larman also asked about 2-distance sets and this was crucial to the recent counterexample in dimension 65. (See this post.) Problem 7 is related to a special case of Conjecture 5. It is based on replacing a directed edge from vertex i to vertex j by the point e_i-e_j. Problem 15 is known only for k=2. It is true for zonotopes (where a simplex face is not an option) with d=2k.  This case is a high-dimensional analog of Gallai-Sylvester theorem. It is quite interesting for simple polytopes.

About these ads
This entry was posted in Combinatorics, Geometry, Open problems and tagged . Bookmark the permalink.

4 Responses to Some old and new problems in combinatorics and geometry

  1. Dear Gil,

    Thanks for the nice collection of problems. It is hard to believe that the photo at the top is from 1933!
    Best,

    Joe

  2. Dear Gil,
    Relating Problem 14 and my earlier comment on universality and (ir)reversibility in Scott’s blog — I do not know, if other CA are interesting for you, but not long time ago I realized that reversible CA I used earlier for some experiments is likely computationally universal http://quantumbot.wordpress.com/2013/07/27/reversible-anto-logic/
    Sincerely, Alex

  3. Pingback: Random Graphs Week – Monday | Eventually Almost Everywhere

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s