Mathematics Problem Archive

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

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

Define $f:\mathbb{N}\to\mathbb{N}$ by $f(n)=n+\operatorname{rev}(n)$, where $\operatorname{rev}$ reverses the decimal digits. Are there infinitely man...

What is the complexity of the union of ``fat'' objects in $\mathbb{R}^3$?...

What is the maximum number of $k$-sets? (Equivalently, what is the maximum complexity of a $k$-level in an arrangement of hyperplanes?)...

What is the complexity of the vertical decomposition of $n$ surfaces in $\mathbb{R}^d$, $d \ge 5$?...

How many intersections among an arrangement of pseudosegments in the plane must be added as vertices to allow the pseudosegment arrangment to be exten...

How many polyominoes on $n$ squares are there? A polyomino is a connected interior-disjoint union of axis-aligned unit squares joined edge-to-edge, in...

Given a set of $n$ unit-radius balls in $\mathbb{R}^3$, what is the number of lines that are tangent to four of the balls in the set, and miss all the...

Label the faces of a unit cube with numbers $1$--$6$ as in a die. Place the cube to sit on an integer lattice grid, with one corner at the origin and ...

Let us say that two rectangles in the place are independent if both their $x$- and $y$-axis projections are disjoint. A set of rectangles is then inde...