Discrepancy


Erdős: Color the
positive integers red and blue. If I choose a subset S of
numbers, let's call the "discrepancy" of that set the absolute value of
the difference of the number of blues and red. (So, three
blues and one red means discrepancy two, as does 85 reds and 83
blues.) List out all the finite arithmetic progressions
starting with zero (such as {0,1,2}, {0,13,26,39}, and {0,4,8,12,16}),
and calculate all their discrepancies. Can the numbers you
get all be bounded by some B? (You could
also, instead of summing functions of integers into {1, 1} over all
finite arithmetic progressions, consider functions into the nth
roots of unity, or even into the complex unit circle.) What
if the coloring function must be completely multiplicative, i.e., f(nm)
= f(n) f(m)
for all naturals n, m?
This problem is sometimes known as "determining the
discrepancy of homogeneous arithmetic progressions."

Beck:
Suppose we have three permutations σ_{1},
σ_{2}, and σ_{3}
of the integers 1 to n. If we color each
number in this range red or blue, call the discrepancy
of the coloring the maximum difference between the number of blues and
reds in any interval of σ_{1},
σ_{2}, and σ_{3}. Is
it always possible to find a coloring for any
three permutations so that the discrepancy is O(1)?
(The best known result is O(log n).)
For example, if σ = [1,5,2,7,4,3,6], and we take the coloring
(1,2,3,4,5,6,7), then the
discrepancy of the interval [5,2,7,4] is 2 :


1


3

6


5

2

7

4


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

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.

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}!)
 ErdősSzekeres : Does every o(2k
choose k) points in the
plane contain a convex kgon?
 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.
 Danzer:
A point set in the plane is said to be "Danzer" if it intersects every
convex set of area 1. Does there exist a Danzer set with bounded
density, i.e., so that the Rball about the origin contains O(R^{2}) points of the set?

Graphs, Hypergraphs, Set Systems, Designs


ErdősGyárfás:
Is it true
that every graph whose vertices have odd degree greater than one
contains a cycle of length 2^{n}
for some n? This one has kept me (and
apparently,
lots of others) up many a night trying fruitlessly to
construct a counterexample. See this.

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 true that G(n,1/2) is uniquely colorable (aas)?

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.

Zaremba: 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 by B. Is B=5
already sufficient?

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.

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.

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.
