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 c|E(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 two-dimensional 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 Br, the Ball of radius r about 0 in R2. What is the chromatic number of the unit distance graph on Br? 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 r0, the chromatic number must become 4. It is easy to see that r0 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 k-coloring of Euclidean N-space contains a monochromatic copy of S. Show that, if S can be embedded in some d-dimensional 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 non-equilateral triangle T, show that it is possible to color the plane with three colors so that there is no monochromatic (congruent) copy of T.
Geometric
Graphs
(graphs associated
with a straight-line embedding in the plane)
-
Pach : Suppose a geometric graph has no pairwise k-crossing lines. That is, no k edges all cross each other. Must the graph have Ok(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 3-uniform 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 R3 faithfully, i.e., the vertices are placed in such a way that, for any two edges e1 and e2 of H, the planar triangles spanned by their respective vertices intersect if and only if e1 and e2 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(n2).
-
Solymosi : Suppose a family V of n points are chosen in R3 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: n1/2!)
- Erdős-Szekeres : Does every o(2k choose k) points in the plane contain a convex k-gon?
- 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).
Graphs and Hypergraphs
-
Erdős-Gyárfás: Is it true that every graph whose vertices have odd degree greater than one contains a cycle of length 2n for some n? This one has kept me (and apparently, lots of others) up many a night trying fruitlessly to construct a counterexample.
-
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 straight-line embedding in the plane. Define the "pairwaise crossing number" of a graph the be the minimum number of crossing pairs of edges in any straight-line 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) = | |S||T|/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(Qn)| edges of the n-cube Qn contains a C4 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 vertex-transitive graph have a Hamilton path? See this.
- Seymour: 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.
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.
-
Graham: Call a sequence of permutations σi on ni symbols m-symmetric if the number of copies of τ is approximately n!/m!2 for each τ on m symbols. Is it possible for each m > 0 for a sequences of permutations to be m symmetric but not (m+1)-symmetric? If not, what is the least m for which m-symmetry implies (m+1)-symmetry?
-
☺ 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 m-symmetric” 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.
Matroids, Lattices, and Posets
-
Rota: Are the Whitney numbers of every geometric lattice unimodal? (Or even better: log-concave.) 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 GFp^q contains at least one of as a minor?
-
☺ What are the Whitney numbers of the (lattice of contractions of the) n-cube? 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 Sn (the "inversion" poset) 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 n-set? Conjecture: n-1.
-
☺ 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 Bn which includes no B2 as a subposet?
Set Systems
-
Frankl: If F is a finite non-trivial union-closed family of finite sets, then some element appears in at least half the members of F. 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 Zp, 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 Sylvester-Gallai: Suppose S is a tranversal of Zp2, 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ős-Turán: Suppose that S is a set of positive integers with the property that S+S -- that is, all sums of the form s1+s2 for s1, s2 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 2n-1 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ős-Ginzburg-Ziv 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 two other elements. Such a set is called "sum-free." 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 sum-free S. It is known that R is less than 4, and R > 2.064 (Abbott and Levine-O'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.
-
Erdős, Strauss: Show that, for each positive integer n, it is possible to write 4/n as a sum of three reciprocals of positive integers. 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 Fn which haveall nonzero coordinates so that Ax = y. See this.
-
Graham: Is x2+y2=z2 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ős-Strauss : 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.
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 n2and (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, p-1) = 1? In this case, we are forcing the map j→jk 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.
Coding Theory
-
A covering code of radius R is a set of binary n-words so that every binary n-word 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 2R / nR, 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 n-words so that every binary n-word 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 2R / nR, but it’s not known what c(R) is. Some believe that c(R) = 2R R!.
-
☺/Ellis/Kahng: An asymmetric packing code of radius R is a set of binary n-words so that no binary n-word 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 wrap-around) 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 c2n/nR and c2n log n/nR.
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), (x-1, y), (x, y+1), or (x, y-1) 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 d-dimensional 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) = k2/2.
Miscellaneous
-
What is the minimum number of n-simplexes needed to triangulate the n-cube? See this.
-
Is the exponent of matrix multiplication 2? In other words, can two n b n matrices be multiplied in O(n2+ε) 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 Sn be a subset of 2n, interpreted as a family of truth assignments to x1,...,xn. Let Sn-SAT be the problem of determining satisfiability over the possible assignments in Sn. Call Sn "exponential" if Sn > αn for some α > 1 and all sufficiently large n. Is Sn-SAT NP-Hard? See this.
