Paul Erdős in Jerusalem,
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
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.
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
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)
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?
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.
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