Some old and new problems in combinatorics and geometry

Paul Erdős in Jerusalem, 1933  1993

Update: Here is a link to a draft of a paper* based on the first part of this lecture. Some old and new problems in combinatorial geometry I: Around Borsuk’s problem.

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 be the smallest integer so that every set of diameter one in can be covered by sets of smaller diameter. Borsuk conjectured that .

It is known (Kahn and Kalai, 1993) that : , and also that (Schramm, 1989) .

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 .

Question (Oded Schramm): Is there some so that for every  there exist a set of constant width 1 in dimension n whose volume satisfies .

Around Tverberg’s theorem

Tverberg’s Theorem states the following: Let be points in  with . Then there is a partition of such that  .

Problem 4:  Let be the smallest integer such that given points  in , there exists a partition of such that every among the convex hulls ,   have a point in common.

Reay’s “relaxed Tverberg conjecture” asserts that that whenever (and ), .

Problem 5: For a set , denote by those points in which belong to the convex hull of pairwise disjoint subsets of . We call these points Tverberg points of order .

Conjecture: For every , .

Note that .

Problem 6:   How many points in guarantee that they can be divided into two parts so that every union of convex sets containing the first part has a non empty intersection with every union of 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 and (so far we disregard the orientation of edges,) so that when you reverse the directions of all edges in you get a strongly connected digraph.

Erdős-Ko-Rado theorem meets Catalan

Problem 8 

Conjecture: Let be a collection of triangulations of an n-gon so that every two triangulations in  share a diagonal.  Then 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 . Denote by E the number of edges of K and by F the number of 2-faces of K.

Conjecture: F ≤ 4E

A weaker version which is also widely open and very interesting is: For some absolute constant C, F ≤ 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 . (Say, a ball, say a cube…) For which classes of functions, every  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, , 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,  where you can prove that

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 d 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 .
How large X is needed to be so that the restriction (trace) of X to some set ,  has at least elements?

Graph-codes

Problem 18: Let  P  be a property of graphs. Let be a collection of graphs with n vertices so that the symmetric difference of two graphs in has property P. How large can 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 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 . Problem 15 is known only for . 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.

*This is a draft of a chapter for “Surveys in Combinatorics 2015,” edited by Artur Czumaj, Angelos Georgakopoulos, Daniel Kral, Vadim Lozin, and Oleg Pikhurko. The final published version shall be available for purchase from Cambridge University Press