Mathematics Problem Archive

Erdős: Show that every (1/2+ľ)|E(ő_(n))| edges of the n-cube ő_(n) contains a C_(4) when n is sufficiently large. (The best known value of ľ is around...

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

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

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

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

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

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

Given a permutation σ, what is the maximum number of copies of σ that a permutation on n symbols may contain?...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 $M(n)$ be the number of monotone Boolean functions of $n$ variables, equivalently the number of antichains of subsets of an $n$-element set. Deter...

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

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

Is the number of degenerate Herman rings of a rational function finite, and can it be bounded in terms of the degree of the rational function?...

Let $A$ be a set of vectors $a=(a_1,\ldots,a_n)\in\mathbb C^n$ such that every $n$ of them are linearly independent, and assign to every $a\in A$ a $\...

Let $A$ be a set of vectors $a=(a_1,\ldots,a_n)\in\mathbb C^n$ such that every $n$ are linearly independent, and let $K_a$ be plane convex compact set...

Classify entire functions $f,g$ for which $f\circ g$ is periodic. Prove that, up to the natural equivalences, the possibilities are exhausted by: $g$ ...

Does there exist an entire function whose zeros lie on the positive ray and whose $1$-points lie on two rays making angles $\pm\alpha$ with it, for so...

For $\omega=e^{2\pi i/5}$, is an entire solution of $$f(\omega z)f(\omega^{-1}z)=f(z)-1$$ unique up to rotation of the variable $z$?...

Let $f$ be entire and suppose every zero of every derivative $f^{(n)}$, $n\ge0$, lies in the closed lower half-plane. Must $f$ lie in the compact-open...

Let $\mu$ be a positive plane measure with $\mu(\{|z|\le r\})\le cr^\alpha$ for some $0<\alpha<1/2$. Can its logarithmic potential $$u(z)=\int\log\lef...

For rational functions of each fixed degree, determine the analogues of Goldberg's constant and the unit-disk zero/one-point extremal quantities, and ...

For a regular connected compact plane set $E$, let $\beta_E=\limsup_{\varepsilon\to0}\log l(\varepsilon)/(-\log\varepsilon)$, where $l(\varepsilon)$ i...

If the definition of $\sup_E\beta_E$ is extended from connected regular compact plane sets to all regular compact sets, is the supremum attained on co...