Mathematics Problem Archive

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

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

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^(n) for some n? This one has k...

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

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

Seymour/Szekeres: The "cycle double cover conjecture" states that every bridgeless graph contains a set of cycles which cover each edge of the graph e...

Seymour: "Seymour's Second Neighborhood Conjecture" Any oriented graph has a vertex whose outdegree is at most its second outdegree (vertices at direc...

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

: Given two permutations σ and τ, what is the expected number of copies of σ in a permutation chosen uniformly at random from those permutations on n ...

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

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

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

Is the poset of integer partitions ordered by refinement Sperner?...

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

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

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

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

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

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

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

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

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

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

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

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 positive integers $N,q,a$, let $Q(N;q,a)$ be the number of perfect squares among $a,a+q,\ldots,a+(N-1)q$, and let $Q(N)=\max_{q,a\geq1}Q(N;q,a)$. ...

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

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

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

How many completely invariant components can the Fatou set of a transcendental entire function have? In particular, can there be more than one?...

Does there exist a rational function having an analytic invariant Jordan curve on which it is topologically conjugate to an irrational rotation, where...