Mathematics Problem Archive

Is it true that if all vertices of a base polyhedron B are in $\{0,1,-1\}^n$ and $0 \in B$, then B has a vertex v such that -v is also a vertex?...

Let $\mathcal{C}$ be a clutter on ground set V, and let $\mathcal{B}$ be its blocker. Is it true that $\mathcal{C}$ is nonideal if and only if there e...

Let G=(V,E) be a mixed graph with non-negative edge-lengths and let $s,t \in V$. Can we find in polynomial time an orientation where the sum of the le...

Given a digraph D=(V,A) and non-negative even-valued arc weights $w_a\ (a \in A)$, can we find in polynomial time a w-vertex cover $x$ of the underlyi...

Let P be the set of partitions of a ground set S. We allow two operations on P: (1) splitting a class into two arbitrary classes and (2) joining two c...

Let G=(V,E) be a bipartite graph, and $c_1,\dots c_k$ positive reals whose sum is 1. Can E always be partitioned into k parts $E_1,\dots,E_k,$ so that...

For which classes of digraphs can we explicitly give a linear description of the convex hull of kernels?...

A quasi-kernel of a digraph $D$ is an independent vertex set $K$ sucht that every vertex is reachable from $K$ in $D$ by a path of length at most two....

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

Graham: For every non-equilateral triangle T, show that it is possible to color the plane with three colors so that there is no monochromatic (congrue...

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

Straus: Is every polygonal room in the plane illuminable from some point? See this....

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

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