Mathematics Problem Archive

Given k disjoint matchings in a bipartite graph, a rainbow matching is a matching that contains one edge from each of them. Is it true that any family...

Given a crossing negamodular function $R:2^V\to \mathbb{Z}$ such that $R(X)\ne 1$ for every $X\subseteq V$ and a hypergraph $G_0=(V,\mathcal{E}_0)$, f...

A graph G is said to be a Seymour graph if for any edge set F that satisfies $|C\cap F|\le |C\setminus F|$ for every circuit C of G, there exist $|F|$...

Let M be a matroid, and let A and B be two bases of M. A subset X of A and a subset Y of B, both of size k, form a serial symmetric exchange with resp...

Let $p_1$ and $p_2$ be integer skew-supermodular set functions on ground set S such that $\max\{p_1(X),p_2(X)\}\leq \min\{|X|,k\}$ for every $X \subse...

Let G=(V,E) be a graph with maximum degree $\Delta \geq 2$, and let M=(V,r) be a matroid that has $2 \Delta$ disjoint bases. Is it true that M has $2 ...

For a loopless matroid $M=(S,r)$, let $\Delta(M)=\max_{X\subseteq S} |X|/r(X)$. Let $M_1=(S,r_1)$ and $M_2=(S,r_2)$ be two arbitrary loopless matroids...

Graham: A set of points S is Euclidean Ramsey if, for every k, there exists an N so that every k-coloring of Euclidean N-space contains a monochromati...

Pach : Suppose a geometric graph has no pairwise k-crossing lines. That is, no k edges all cross each other. Must the graph have O_(k)(n) edges?...

: Suppose we begin with a set of points S in the plane. Let T(S) be the set of points one gets by taking all lines through pairs of points in S, and t...

Solymosi : Suppose a family V of n points are chosen in R^(3) and L is a collection of lines so that every triangle spanned by three points of V is pi...

What is the minimum number of n-simplexes needed to triangulate the n-cube? See this....

How many congruent regular tetrahedra can touch at a point? Easy to show it's at least 20, and at most 22. Apparently, this has been open a long time....

Erdős: Does lim R(k,k)^(1/k) exist? What is it? (If it exists, it's between sqrt(2) and 4.) See "Small Ramsey Numbers" by Stanislaw Radziszowski....

Pach, Tóth: Define the "crossing number" of a graph to be the minimum number of (topological) crossings of edges in any straight-line embedding in the...

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

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

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