Mathematics Problem Archive

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

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

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

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

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

Let $A=(a_{ij})$ be an $n\times n$ matrix with nonnegative entries and total entry sum $n$. Define $$\phi(A)=\prod_{i=1}^n\sum_{j=1}^n a_{ij}+\prod_{j...

A superpermutation on $n$ symbols is a string containing every permutation of the $n$ symbols as a contiguous substring. Determine the minimum possibl...

For partitions $\lambda,\mu,\nu$ of $n$, the Kronecker coefficient $g_{\mu\nu}^{\lambda}$ is defined by $$V_\mu\otimes V_\nu\cong\bigoplus_\lambda g_{...

Let $W(r,k)$ be the least $N$ such that every coloring of $\{1,\ldots,N\}$ with $r$ colors contains a monochromatic arithmetic progression of length $...

Let $\boldsymbol{d}=(d_1,\ldots,d_n)$ be an unordered partition of $4g-4$ with $d_i\in\{-1,0,1,2,\ldots\}$, and let $\widehat\Pi_{4g-4}$ be the set of...

Let $\boldsymbol{d}=(d_1,\ldots,d_n)$ be an unordered partition of $4g-4$ with $d_i\in\{-1,0,1,2,\ldots\}$, and let $\widehat\Pi_{4g-4}$ be the set of...

Let $\boldsymbol{d}=(d_1,\ldots,d_n)$ be an unordered partition of $4g-4$ with $d_i\in\{-1,0,1,2,\ldots\}$, and let $\widehat\Pi_{4g-4}$ be the set of...

Fix singularities $a_1,\ldots,a_n$ and real exponent differences $\alpha_1,\ldots,\alpha_n$ for second-order Fuchsian equations on the Riemann sphere....

For the Heun equation $$y''+\left(\sum_{j=0}^2\frac{1-\alpha_j}{z-a_j}\right)y'+\frac{Az-\lambda}{(z-a_0)(z-a_1)(z-a_2)}y=0,$$ where $\alpha_j>0$, $A=...

Classify the entire solutions of $F(y^{(k)},y)=0$ when $F$ is irreducible and its highest-degree homogeneous part has a single distinct linear factor,...

Let $f$ be a nonlinear entire function and let $D$ be a Fatou component on which all limit functions of the iterates $f^n$ are constant. Can the set o...

Let $f:\widehat{\mathbb C}\to\widehat{\mathbb C}$ be rational with Julia set $J$, and suppose that a component $D$ of $\widehat{\mathbb C}\setminus J$...