Mathematics Problem Archive

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

For finitely many positive charges $a_k$ at points $x_k\in\mathbb R^3$, is the critical set of $u(x)=\sum_{k=1}^n a_k/|x-x_k|$ always finite?...

Let $u_1,u_2,u_3$ be subharmonic in the plane with $u_j(0)=0$, and let $v_1\le v_2\le v_3$ be their pointwise increasing rearrangement. Put $I(r,v)=\i...

Let $f:\mathbb C\to\mathbb P^2$ be linearly nondegenerate and let $\delta(a,f)$ be the Nevanlinna deficiency of a point $a\in\mathbb P^2$. Prove that ...

Let $f:\mathbb C\to\mathbb P^n$ be holomorphic with spherical derivative $\|f'\|(z)=O(|z|^\sigma)$ for some $\sigma>-1$, and let $a_1,\ldots,a_q$ be h...

For $p\ge3$, let $V(D)$ consist of zero-free holomorphic vectors $(f_1,\ldots,f_p)$ on $D$ with $\sum f_j=0$, and use the source's definition of a $C$...

For real matrices $A\in\operatorname{Mat}_{n\times n}$, $B\in\operatorname{Mat}_{n\times p}$, and $C\in\operatorname{Mat}_{m\times n}$ with $n=mp$, de...

A facet of a $d$-polytope is degenerate if it has more than $d$ vertices. Determine the maximum number of degenerate facets of an $n$-vertex $d$-polyt...

Determine the maximum total number of faces of a $d$-dimensional convex polytope with $n$ vertices and $n$ facets. In dimension four, do such fat-latt...

For fixed $d>3$, determine whether every point of an $n$-point set in $\mathbb R^d$ is a convex-hull vertex faster than the best known near-$n^{2\lflo...

Given a sorted list of $n$ real numbers, find for every $1\le k\le n$ the shortest interval containing exactly $k$ entries. Find a subquadratic algori...

Given lines in the plane and two vertices $s,t$ of their arrangement, find a subquadratic algorithm for the shortest $s$-$t$ path along arrangement ed...

Can every convex polytope be triangulated so that every vertex degree, or every edge degree, is bounded by a constant or by a polylogarithmic function...

Determine the least number of colors needed to color the Euclidean plane so that points at unit distance receive different colors....

Given a finite planar point set and a prescribed rectangle, approximate efficiently the minimum number of congruent copies of the rectangle needed to ...

Do there exist seven planar points in general position—no three collinear and no four concyclic—such that every pairwise distance is an integer?...

Can the $3\times6$ rectangle with a $2\times2$ corner removed tile a rectangle using an odd number of congruent copies?...

Can sums of square roots of integers be compared in polynomial time on a Turing machine? Equivalently, obtain effective polynomial bit bounds for a no...

Find the largest function $t(n)$ such that every convex $n$-gon has a triangulation containing at least $t(n)$ distinct triangle areas; also determine...

What is the coarse Ricci curvature of discrete or continuous nilpotent groups? In particular, for the natural random walk generated by $a,b$ on the di...

Suppose the global infimum of coarse Ricci curvature is zero, while its infimum on every finite-radius ball about an origin is positive. Is there a sy...

Define curvature up to $\delta$ by $$T_1(m_x,m_y)\leq(1-\kappa(x,y))d(x,y)+\delta.$$ Which theorems for positive coarse Ricci curvature extend to this...

Define a scalar-curvature candidate by $S(x)=\int\kappa(x,y)\,dm_x(y)$, possibly with a distance-dependent weight. Does this quantity have useful geom...

Under the strengthened transport estimate $$T_1(m_x^{*t},m_{x'}^{*t'})\leq e^{-\kappa\min(t,t')}d(x,x')+C\frac{(\sqrt t-\sqrt{t'})^2}{2d(x,x')},$$ the...

For permutation groups with the transposition random walk, coarse Ricci curvature is positive but gives concentration of the wrong order. Can this dis...

Let $(X,\rho)$ be a finite metric space. Its fundamental polytope $R_{X,\rho}$ is the convex hull of the vectors $e_{x,y}=(\delta_x-\delta_y)/\rho(x,y...