Mathematics Problem Archive

: What are the Whitney numbers of the (lattice of contractions of the) n-cube? What if contractions equivalent under symmetries of the cube are identi...

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

: 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 "symmetri...

Griggs, Lu: ("Diamond-Free Posets Problem") What is the size of the largest subset of the Boolean lattice B_(n) which includes no B_(2) as a subposet?...

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

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

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

Erdős: Suppose I have a sequence of positive integers whose reciprocals sum to infinity. Must that sequence contain arbitrarily long arithmetic progre...

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

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

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

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

/Solymosi: Finite field Sylvester-Gallai: Suppose S is a tranversal of Z_(p)^(2), i.e., a set of points in the affine plane so that every row and colu...

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_(1)+s_(2) for s_(1), s_(2) in ...

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

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

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

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

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

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

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

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

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

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

/Riasanovsky: Let f be the formal power series over Z/2Z whose nth coefficient is the parity of the divisor function Ă_(0)(n). Is it true that the den...

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

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

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

/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 code...

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

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

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

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

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

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

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

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

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