Euclidean
Ramsey Theory


Erdős:
How many colors is it necessary to use so that, if you paint every
single point of the twodimensional plane some color, no two points
which are a distance one from each other are the same color?
(That is, what is the chromatic number of the unit distance graph in
the plane?) It's not hard to show that the number is between
4 and 7  but nobody has a clue where it falls in between.
See this.
A related problem, due
to Chris Dillard: Consider B_{r},
the Ball of radius r about 0 in R^{2}.
What is the chromatic number of the unit distance graph on B_{r}?
We know that, for r < 1/2, it is 1; for r
= 1/2,
it is 2; for 1/2 < r <=
sqrt(3)/3, it's 3. How about for r >
sqrt(3)/3? At some r_{0},
the chromatic number must become 4. It is easy to see that r_{0
}is no more than 3/sqrt(11) : see the figure
below. In fact, it is possible to improve this to sqrt(3)/2,
but that still leaves a sizable gap. Of course, it would be
great to find an r for which the chromatic number
goes up to 5, but that's not going to come so easily.

Graham:
A set of points S is Euclidean Ramsey if, for every
k,
there exists an N
so that every kcoloring of Euclidean Nspace
contains a monochromatic copy of S. Show
that, if S can be embedded in some ddimensional
sphere, then it is Euclidean Ramsey. This problem is open
even for four points on a circle, although it is known to be true for
triangles. (Boris Bukh points out that there is good evidence
against this now: here
and here,
for example.)

Graham:
For every nonequilateral triangle T, show that it
is possible to color the plane with three colors so that there is no
monochromatic (congruent) copy of T.

Geometry


Pach : Suppose
a geometric graph has no pairwise kcrossing
lines. That is, no k edges all cross each
other. Must the graph have O_{k}(n)
edges?

☺ Suppose
we begin with a set of points S in the plane. Let T(S) be the set of
points one gets by taking all lines through pairs of points in S, and
taking all intersections of those lines. If one iterates T(.), how
quickly does the cardinality of the set grow? See this.

Solymosi
: Suppose H is a
linear 3uniform hypergraph, i.e., a subset of the set of all triples
of n points with the property that no two edges intersect in more than
one point. Further suppose that H is embedded in R^{3}
faithfully, i.e., the vertices are placed in such a way that, for any
two edges e_{1} and e_{2}
of H, the planar triangles spanned by their respective vertices
intersect if and only if e_{1}
and e_{2} intersect in H, and,
if they do intersect, they do so in precisely their common vertex. Show
that the number of edges in H is o(n^{2}).

Solymosi
: Suppose a family V
of n points are chosen in R^{3}
and L is a collection of lines so that every triangle spanned by three
points of V is pierced by some element of L. Show that L must grow at
least linearly in n. (Best known: n^{1/2}!)
 Conway : Does every thrackle
have average degree at most 2? A thrackle is a drawing of a
graph
in the plane so that every two edges share exactly one point (whether
it is an endpoint of two incident edges or a transverse crossing  no
tangencies allowed).

What
is the minimum number of nsimplexes needed to
triangulate the ncube? See this.

How
many congruent regular tetrahedra can touch at a point? Easy
to
show it's at least 20, and at most 22. Apparently, this has
been
open a long
time.
 Straus: Is
every polygonal room in the plane illuminatable from some
point? See this.

Graphs,
Hypergraphs, Set Systems, Designs

 Beck:
Show that the discrepancy of any
hypergraph H
is at most cE(H)^{1/2}

Erdős: Does lim R(k,k)^{1/k}
exist? What is it? (If it exists, it's between
sqrt(2) and 4.) See "Small Ramsey Numbers"
by Stanislaw
Radziszowski.

Erdős,
Hajnal: Suppose G has n
vertices and no induced copy of H. Is
there an ε > 0, depending only on H,
so that the homogeneous number of G (i.e., the size
of the largest clique or independent set) is at least n^{ε
}?

Pach,
Tóth: Define the "crossing number" of
a graph to be the minimum number of (topological) crossings of edges in
any straightline embedding in the plane. Define the
"pairwaise crossing number" of a graph the be the minimum number of
crossing pairs of edges in any straightline embedding in the
plane. These two quantities may differ, since two edges may
cross multiple times. But do they really differ?
Or, on the other hand, is it true that for every graph G,
its crossing number and pairwise crossing number are the same?

Chung,
Graham:Define the discrepancy of a
graph to be the
largest value of D(S,T)
=  ST/2 � e(S,T)
, over all disjoint vertex sets S and T.
Suppose that G has no induced copy of some graph H.
How large must the discrepancy be?
 Erdős: Show
that every (1/2+ε)E(Q_{n}) edges of the ncube Q_{n}
contains a C_{4} when n
is sufficiently
large. (The best known value of ε is around .19 due to
Chung.)
 Seymour/Szekeres:
The "cycle
double
cover conjecture" states that every bridgeless graph contains a set of
cycles which cover each edge of the graph exactly twice. See this
and this.
 Lovász : Does every finite connected
vertextransitive graph have a Hamilton path? See
this.
 Seymour: "Seymour's Second Neighborhood
Conjecture" Any oriented graph has a vertex
whose outdegree is at most its second outdegree (vertices at directed
distance 2). See this.
 Graham: Suppose
that G is
a tree. Denote by L(G)
the line
graph of G. Is the sequence G,
L(G),
L(L(G)),
L(L(L(G)))
... unique to G?
That is, can a tree be reconstructed from the sequence of
sizes of its iterated line graphs? See this.
 ☺ What is the listchromatic number of Sudoku?
That is, suppose one places k symbols (aka
colors) in each cell of a Sudoku board  not necessarily all the same
lists of symbols. What is the least k
so that it is always possible to choose a symbol/color from each list
for its cell that the resulting choices have no conflicts in rows,
columns, or blocks (the 3X3 submatrices that cannot have conflicts in
ordinary Sudoku)? This is the Sudoku analogue of the famous Dinitz
Conjecture / Galvin Theorem.
 ☺ A graph G is said to be
uniquely Hsaturated
if it contains no H,
but adding any edge to G
creates exactly one copy of H
(up to isomorphism). Clearly, if G is uniquely K_{r}saturated,
then joining a single vertex to G
creates a uniquely K_{r}_{+1}saturated graph.
Call a uniquely K_{r}saturated graph
sporadic if it has no dominating vertex. Is it true that, for
each r,
there are finitely many sporadic uniquely K_{r}saturated graphs?
 ☺ A graph G is said to
be uniquely
colorable
it has only one optimal coloring up to permutation of the colors.
(That is, there is only one partition into a minimum number
of
independent sets.) Is it false that G(n,1/2) is uniquely
colorable (aas)?
 ☺/Dutle : What are the
(homogeneous adjacency) spectra of the ultracube and the complete
hypergraph? (Ultracube = cartesian power of a hyperedge.)
 ☺/Dutle
: Give a combinatorial characterization of those kuniform
hypergraphs whose (homogeneous adjacency) spectra are invariant under
multiplication by kth
roots of unity.

Permutations


Given
a permutation τ, what is the maximum number of copies of
τ that a permutation on n symbols may
contain?

☺ Given two permutations τ
and σ, what is the expected number of copies of σ
in a permutation chosen uniformly at random from those permutations on n
symbols which avoid τ? Newsflash!
Miklós Bóna has a nice
paper
addressing this.

☺ Is it
possible for a permutation on n symbols to contain
exactly n!/(m!^{2}(n
 m)!)
copies of each
permutation on m symbols? (Yes for m=1,2,3.
Unknown for m>3.) Do infinitely
many such perfectly msymmetric
permutations exist?

Propp:
Show that the inversion
permutation, i.e., the one which takes s to 1/s
mod p,
has longest increasing
subsequence of length 2√p,
i.e., the length it would have if the permutation were truly random.
 What
is the length of the shortest sequence in [n]* containing, as a
(consecutive) subword, each permutation of [n]? See this,
this,
this,
this,
and this.
 Linal/Luria: A
ddimensional
permutation of order n
is an nbynby...byn (d+1)dimensional
array of zeroes and ones, with the property that every row, column,
etc., has exactly one 1 in it. (More precisely, if the array
entries are A(j_{1}j_{2}j_{3}...j_{d+1}),
for each k
in [d+1]
and t in [n], there is
exactly one choice of all coordinates j_{i} except i=k so that
setting j_{i}=k makes A(j_{1}j_{2}j_{3}...j_{d+1})=1.)
Let P(n,d) be the number of
ddimensional
permutations of order n.
Linial and Luria showed that P(n,d) <
((1+o(1))n/e^{d})^n^{d}.
Is this tight, i.e., is P(n,d) >
((1+o(1))n/e^{d})^n^{d }also
true? If so, this would be a very satisfying generalization
of
Stirling's formula and wellknown bounds on the number of Latin squares
(which are 2dimensional permutations in disguise). See this.
 ☺/Kirkpatrick: What
is the computational complexity of enumerating linear extensions of
dimension 2 posets?

Matroids,
Lattices, and Posets


Rota: Are
the Whitney numbers of every geometric lattice unimodal? (Or
even better: logconcave.) Again, not much is
known. Perhaps it would be easier to prove it for (the
lattices of contractions of) planar graphs...? See this.

Rota: Are
there are finite number of excluded minors for matroids representable
over any given finite field? That is, is there a finite set
of matroids which every matroid not representable
over GF_{p^q} contains at least
one of as a minor?

☺ What
are the Whitney numbers of the (lattice of contractions of the) ncube?
What if contractions equivalent under symmetries of the cube are
identified? How many contractions are there up to
isomorphism? See this.

Is
the weak order on S_{n}
(the "inversion" poset) Sperner?
 Is the poset of integer partitions ordered
by refinement Sperner?
 Fishburn,
Pekec, Reeds: How
many comparisons are needed to determine a linear order of the Boolean
poset? That is, what is the fewest number of questions of the
form "Is S
< T?"
must one ask in order to find out a linear ordering of all subsets of
an nset?
Conjecture: n1.

☺
Show that the jump number of a random linear extension of a grid poset
(i.e., a product of chains) is close to the maximum w.h.p.
(For
the "symmetric grid" poset [m]^n, this is known for n = exp(o(log m)).)
 Griggs, Lu:
What is the size of
the largest subset of the Boolean lattice B_{n} which
includes no B_{2}
as
a subposet? (What is the maximum number of subsets of [n] so that there
are no A, B, C, D with A < B, A < C, B < D, and C < D?)
 Griggs, Lu: For
any poset P, define ex(n,P) to be the size of the largest
subset of the
Boolean lattice B_{n} which
includes no
(injective) copy of P as a (notnecessarily induced)
subposet.
Show that lim_{n}_{→}_{∞} ex(n,P) n^{1/2}
2^{
n}
exists.
 ☺
Is
enumeration of linear
extensions #Phard for twodimensional posets? This is
equivalent
to the question: is it #Phard to compute the size of intervals of the
weak Bruhat order?
 Kislitsyn:
"1/3  2/3 Conjecture" For every poset that is not a chain,
there
is some pair of elements x and y so that x appears above y in a random
linear extension of the poset at least 1/3 of the time and at most 2/3
of the time. See this.

Combinatorial
Number Theory


Erdős: Suppose I have a
sequence of positive integers whose reciprocals sum to
infinity. Must that sequence contain arbitrarily long
arithmetic progressions? Apparently very
hard, though obnoxiously simple.

3n+1
("Collatz" or "Ulam") problem: Take any positive integer, and
apply the
following process: (1) divide it by two if it's even, multiply by three
and add one if it's odd, (2) repeat until you reach one. Must
this process terminate? This one is famously difficult, and
is a spectacular way to waste days, weeks, or years of your
life. See this.

Erdős: In the binary
expansion
of sqrt(2), are there arbitrarily long sequences of 0's?
Can you find a single algebraic number with this property?

Are
the positive integer powers of 3/2 mod 1
uniformly distributed in the unit interval? One would think
so, but apparently this is a hard question. See this.

Alon,
Peres: Given any subset S of the
integers modulo a prime p, what is the least K=K(p)
for which there always exists an m so that mS
has no gap of length greater than K?
This question is particularly interesting if S contains about half of
the elements of Z_{p},
since then it bears on questions concerning quadratic residues.

Niederreiter:
Show that
there exists a B so that, for every n >
0, there exists a k relatively prime to n
whose continued fraction has partial quotients all bounded in average
by B. (The sequence a,
b, c, d
is bounded in average by B if a
<= B, a+b
<= 2B, a+b+c <= 3B,
etc.) Is B=3 already
sufficient? If such a B exists, it means
that there are "good multipliers" for quasirandom
permutations.

☺/Solymosi:
Finite field SylvesterGallai: Suppose S is a
tranversal of Z_{p}^{2},
i.e., a set of points in the affine plane so that every row and column
(any two distinguished maximal families of parallel lines, really)
contains exactly one point of S. Must
there be some line which contains exactly two points of S?

ErdősTurán:
Suppose
that S is a set of positive integers with the
property that S+S  that is,
all sums of the form s_{1}+s_{2}
for s_{1}, s_{2}
in S  contains all sufficiently large
integers. (Then S is called an "additive
basis".) Is it possible for the number of representations of n
as one of these sums to be bounded, for all n?
(Conjectural answer: of course not!)

Olson: Every
sequence of 2n1
elements from a group of order n (written
multiplicatively) has an n element subsequence with
product 1 (in the given order). This is the ErdősGinzburgZiv
Theorem for nonabelian groups. See this.

Wills, Cusick: Suppose k
runners having distinct constant speeds start at a common point and run
laps on a unit length circular track. Then for any given runner x,
there is a time at which runner x is distance at
least 1/k away from every other runner.
See this.

Erdős: Suppose that S
is a set of positive integers with the property that no element is the
sum of a nonempty set of other elements. Such a set is called
"sumfree."
Let R(S) be the sum of the reciprocals of S.
How large can R(S) be? Denote by
R the
supremum of R(S)
over all sumfree S. It is known that R
is less than 4, and R > 2.064 (Abbott and
LevineO'Sullivan, respectively).

Dudeney:
Is it possible to choose 2n points in an n by n grid in the
plane so that no three are collinear? Conjecture: no.
In fact, it is conjectured that the answer is still "no"
unless 2 is changed to something less than π√3/3 =
1.813799.... However, this problem dates back to 1917 and
little is known about it. See this.
 Jaeger: If F is a
finite field with at least 4 elements and A is an
invertible n by n matrix
over F, then
there are vectors x, y in F^{n} which
haveall nonzero coordinates so that Ax = y.
See this.

Graham: Is x^{2}+y^{2}=z^{2}
partition regular? That is, is it true that every coloring of
the
positive integers by a finite number of colors contains a monochromatic
Pythagorean triple?
 Rado:
Is it true that, for every n,
there is an
integer M(n), so that
whenever a linear homogeneous equation in n variables is
Ramsey (in the positive integers) for M(n)colors, it is
Ramsey for any number of colors?
 ErdősStrauss
: Is
it possible, for each positive integer n,
to find positive integers a,
b,
and c so
that 4/n =
1/a + 1/b + 1/c ? See this.
 Singmaster
: Show
that
there is some B so that no integer
appears more than B times among the binomial coefficients.
See this.
 Carmichael
: There is no n
so that the only integer m
with phi(n)
= phi(m) is
m=n. ("phi"
is the Euler phi/totient function). See this.
 Ulam
: Is there a dense of points in the real plane
so that every two points are at a rational distance? See this.

Classical
Number Theory


How
quickly do the gaps between successive primes grow? Is it
slower than n^{ε}
for every ε > 0? See this.

Erdős: Is there a prime
between n^{2}and (n+1)^{2
}for every n
> 0?

Is
the least quadratic residue modulo p at most p^{ε}^{
}for any ε >
0?

☺ Consider
the incomplete Gauss sum
∑_{ j=0,...,M}
exp(2πijk/p),
for some prime p. It is known that, for
large p, there exist integers k
and M for which this quantity grows linearly in p,
i.e., is >> p. Is this still true if we require
that (k, p1) = 1? In
this case, we are forcing the map j→j^{k}
to be a permutation.

Erdős: What is ∑_{ n=1,...,∞
}φ(n)/2^n,
where φ(n) is the Euler phi (totient)
function, counting the number of integers less than n
which are relatively prime to n. (Note: a
closed form answer is desired.) Is it irrational?

Show
that (μ(1) + ... +
μ(n))/sqrt(n) →
∞, where μ(n) is the M�bius function. This is connected with
the Mertens Conjecture.

☺/Riasanovsky:
Let
f
be the formal power series over Z/2Z
whose nth
coefficient is the
parity of the divisor function σ(n). Is it true that
the density of 1's in the power series 1/f is 1/32?

Words
and Codes


A
covering code of radius R is a set of binary nwords
so that every binary nword can be reached from one
of the codewords by changing at most R
bits. How big is the smallest covering code of radius R
with n bits? It is known to be a constant
c(R)
times 2^{R }/ n^{R},
but it's not known what c(R)
is. Some believe that c(R)
= R!.

☺/Ellis/Kahng:
An asymmetric covering code of radius R is a set
of binary nwords so that every binary nword
can be reached from one of the codewords by changing at most R
zeroes to ones. How big is the smallest asymmetric covering
code of radius R with n
bits? It is known to be a constant c(R)
times 2^{R }/ n^{R},
but it's not known what c(R)
is. Some believe that c(R)
= 2^{R} R!.

☺/Ellis/Kahng:
An asymmetric packing code of radius R is a set of
binary nwords so that no binary nword
can be reached from more than one of the codewords by changing at most R
zeroes to ones. How big is the largest asymmetric covering
code of radius R with n bits?

Chung/☺: A de
Bruijn
covering code of radius R is a binary string so
that the set of words appearing as n consecutive
symbols (with wraparound) is a covering code of radius R.
What is the smallest de Bruijn covering code with parameters R
and n? It is known to
be between c2^{n}/n^{R}
and c2^{n} log
n/n^{R}.
 Is there a word which is unavoidable over a k letter alphabet,
but not a (k1)
letter alphabet, for each integer k
> 1? See this.
 Chung/Diaconis/Graham:
For each k
and every sufficiently large n
with k
dividing ((n1)
choose (k1)),
there is a universal cycle for the ksubsets
of an n
set.
 Kolakoski:
There is (essentially) a unique sequence over {1,2} which is its own
runlength encoding. Is the density of 1's in this sequence
1/2?
See this.
 ☺/Rorabaugh:
Is it true that,
for some k,
if all (K1)words
are encountered by a tary
word at the same rate as a uniform random tary
word, then this is also true for Kwords,
when K>k? That
is, do substitution instance counts exhibit quasirandom thresholdlike
behavior?

Probability


Consider
the following walk: start at (0,0), at each point in time, we take a
step from (x, y) to (x+1,
y), (x1, y),
(x, y+1), or (x,
y1) with probability
proportional to one
plus the number of steps we have already taken from (x,
y)
to the destination point in the
past. What is the probability of returning to the origin at
some point? Even if the �weight� of an
edge
(i.e., one plus the number of steps taken between two points) is never
incremented beyond 2, this problem is open.

☺/Spencer:
Consider p(v,
t), the probability that a walk beginning from the origin
ends at the point v on the ddimensional
integer lattice in time t. Conjecture :
Ignoring the obvious "parity issue", this function is unimodal in t
>= 0.
 Alon: What is the threshold function n = f(k)
for the event
that a random permutation on n
symbols contains all patterns on k
symbols? Conjecture: f(k) = k^{2}/2
(1+o(1)).
 Tao:
What is the probability that a random nXn matrix over Z_{p} has
zero permanent as n
goes to infinity? (Surely 1/p... as long as p is not 2.)

Miscellaneous


Is
the exponent of matrix multiplication 2?
In other words, can two n b n
matrices be multiplied in O(n^{2+}^{ε})
steps? See this.

Kahn:
If A is an invertible n x n
matrix, is there always an n x n
submatrix B of [A A] so that perm(B) is nonzero. The notation
perm(B) means the permanent of B, which is the "determinant
without the signs". This implies Jaeger's conjecture
above. See this.

☺ Let S_{n}
be a subset of 2^{n},
interpreted as a family of truth assignments to x_{1},...,x_{n}.
Let S_{n}SAT be the problem of
determining satisfiability over the possible assignments in S_{n}.
Call S_{n} "exponential" if S_{n}
> α^{n}
for some α
> 1 and all sufficiently large n. Is S_{n}SAT
NPHard? See this.
 BixbyFlintMiklos :
Let G be a
bicolored graph, and let H
be the graph whose vertices are the valid
pressing sequences of G
and whose edges connect two pressing sequences if they differ by at
most 4 oneletter edits. Is it true that H is always
connected? See this
and this.
