Combinatorial Problems I Like

Last Edit: Oct 2020. Did I leave something out? Has something here been resolved? Please let me know! Email lastname at math dot sc dot edu.

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. Recently, De Grey showed it's at least 5. See this. A related problem, due to Chris Dillard: Consider B_r, the Ball of radius r about 0 in R². 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₀, the chromatic number must become 4. It is easy to see that r₀ 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.

  [画像:Moser Graph]

• 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. (Boris Bukh points out that there is good evidence against this now: here and here, for example.)

• 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.

Geometry

• Pach : Suppose a geometric graph has no pairwise k-crossing 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.

• Kalai : 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 R³ faithfully, i.e., the vertices are placed in such a way that, for any two edges e₁ and e₂ of H, the planar triangles spanned by their respective vertices intersect if and only if e₁ and e₂ 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²).

• Solymosi : Suppose a family V of n points are chosen in R³ 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 n-simplexes needed to triangulate the n-cube? 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 illuminable from some point? See this.

Graphs, Hypergraphs, Set Systems, Designs

• Erdős-Gyárfás: Is it true that every graph whose vertices have odd degree greater than one contains a cycle of length 2ⁿ 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.

• Beck: Show that the discrepancy of any hypergraph H is at most c|E(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^ľ ? This is open even for a 5-cycle.
  

• 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(ő_n)| edges of the n-cube ő_n contains a C₄ 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: "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.

• 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.

• ☺: What is the list-chromatic 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. Even for k=4, the question is open.
  

• ☺: A graph G is said to be uniquely H-saturated 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)?
  

• Nikiforov: What is the meaning of the multiplicity of zero as a root of a hypergraph's (or graph's) characteristic polynomial?

• van Dam, Haemers : Is it true that almost all graphs are determined by their (adjacency) spectrum?

• ☺/Dutle : What are the (homogeneous adjacency) spectra of the ultracube and the complete hypergraph? (Ultracube = cartesian power of a hyperedge.)

• ☺/Clark : What is the (homogeneous adjacency) spectrum of the Fano plane?

• Brouwer : Is it true that the sum of the k largest Laplacian eigenvalues of a graph with m edges is at most k(k+1)/2+m?
  

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!²(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(1+o(1)), 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 d-dimensional permutation of order n is an n-by-n-by-...-by-n (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₁j₂j₃...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₁j₂j₃...j_d+1)=1.) Let P(n,d) be the number of d-dimensional 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 well-known bounds on the number of Latin squares (which are 2-dimensional permutations in disguise). See this.

Matroids, Lattices, and Posets

• ☺: 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 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 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: ("Diamond-Free Posets Problem") What is the size of the largest subset of the Boolean lattice B_n which includes no B₂ 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 (not-necessarily induced) subposet. Show that lim_n→∞ ex(n,P) n^1/2 2 ^-n exists.

• 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.

• ☺: Is enumeration of pressing sequences of bicolored graphs (aka simple pseudographs) #P-hard? Is there an FPRAS for sampling them?

• ☺: Is the 1/3-2/3 Conjecture for Pressing Sequences true? That is, if a graph G is not uniquely pressable, is it true that there much be two vertices x and y so that the probability that x comes before y in a uniform random pressing sequence of G is between 1/3 and 2/3? 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/2mod 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 Sylvester-Gallai: Suppose S is a tranversal of Z_p², 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 s₁+s₂ for s₁, s₂ 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 a nonempty set of 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 = 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ⁿ which haveall nonzero coordinates so that Ax = y. See this.

• Graham: Is x²+y²=z² 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? (Update 2017: Heule+Kullman+Marek showed that this cannot be done with two colors, and that the smallest n for which it becomes impossible to 2-color [n] is exactly 7825!)

• 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.

• 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²and (n+1)² for every n > 0?

• Is the least quadratic residue modulo p at most p^ľfor any ľ > 0?

• Erdős: What is Σ_n≥1 φ(n)/2ⁿ, 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?

• ☺/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?

• ☺: Let f be the formal power series over Z/2Z whose nth coefficient is independently chosen to be 1 with probability Ü(n^-2) (and probability 1 for n=0). Is it true that the density of 1's in the power series 1/f is 1/2?

Words and Codes

• 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 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 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 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 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 c2ⁿ/n^R and c2ⁿ log n/n^R.

• Is there a word which is unavoidable over a k letter alphabet, but not a (k-1) letter alphabet, for each integer k > 1? See this.

• Chung/Diaconis/Graham: For each k and every sufficiently large n with k dividing ((n-1) choose (k-1)), there is a universal cycle for the k-subsets of an n set.

• Kolakoski: There is (essentially) a unique sequence over {1,2} which is its own run-length encoding. Is the density of 1's in this sequence 1/2? See this.

• ☺/Rorabaugh: Is it true that, for some k, if all (K-1)-words are encountered by a t-ary word at the same rate as a uniform random t-ary word, then this is also true for K-words, when K>k? That is, do substitution instance counts exhibit quasirandom threshold-like 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), (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) = k²/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.)

• Galvin: Let f(p;n,k) = C(n,k) p^k (1-p)^n-k. If p is not 0, 1/2, or 1, is it possible for f(p;n,k) = f(p;n,l) and f(p;n,k') = f(p;n,l') for distinct k, k', l, l'? This is connected with the question of which permutations can arise as the pattern of independence polynomials of trees.
  

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ⁿ, interpreted as a family of truth assignments to x₁,...,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 > ąⁿ for some ą > 1 and all sufficiently large n. Is S_n-SAT NP-Hard? See this.

• Bixby-Flint-Miklos : 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 one-letter edits. Is it true that H is always connected? See this and this.