Mathematics Problem Archive

Given a digraph D=(V,A), two (not necessarily disjoint) subsets $S,T\subseteq V$ and a connectivity requirement k, develop a strongly polynomial time ...

Let G=(V,E) be an Eulerian graph with minimum degree at least 4, and let W be a closed Eulerian walk of G. Is it true that G has a cycle decomposition...

Let $M=(S,r)$ be a loopless matroid of rank k whose ground set can be partitioned into k bases. Is it true that no matter how we partition S into sets...

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

Is it true that if D=(V,A) is a digraph where every node has positive out-degree, then D has a quasi-kernel of size at most |V|/2?...

Let $G=(V,E)$ be an undirected graph, and $T \subseteq V$ a set of nodes of odd degree. When does an orientation $D$ of $G$ exist which is i) smooth (...

Devise combinatorial polynomial-time algorithms for the following two problems. Given a graph G, find a subgraph H with $O(n)$ edges such that $d_H(X)...

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

Let the graphs $G=(V,E)$ and $H$ be fixed. An edge set $F\subseteq E$ is called $H$-free if $(V,F)$ does not contain $H$ as a subgraph. We say that $F...

Is it true that if all the hyperedges of a hypergraph $H$ have size at most $k$ for some $k\in \mathbb{N}$, then $H$ admits a strongly maximal matchin...

Is it true that if the hypergraph $H$ has no isolated vertices and all of its hyperedges are finite, then $H$ admits a strongly minimal edge cover?...

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

$\rm{gon}(G) \leq \frac{|E(G)|-|V(G)|}{2} + 2$, where $\rm{gon}(G)$ the denotes the divisorial gonality of graph $G$....

Let G=(S,T;E) be a bipartite graph, with weights $w:E \to [0,1]$. A proper weighted edge colouring is a colouring of the edges such that at each verte...

When can we characterize hypergraphs that have an orientation satisfying a prescribed symmetric local edge-connectivity requirement? Special case: can...

Erdős: How many colors is it necessary to use so that, if you paint every single point of the two-dimensional plane some color, no two points which ar...

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

Kalai : Suppose H is a linear 3-uniform hypergraph, i.e., a subset of the set of all triples of n points with the property that no two edges intersect...

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

Conway : Does every thrackle have average degree at most 2? A thrackle is a drawing of a graph in the plane so that every two edges share exactly one ...

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-Gyárfás: Is it true that every graph whose vertices have odd degree greater than one contains a cycle of length 2^(n) for some n? This one has k...

Beck: Show that the discrepancy of any hypergraph H is at most c|E(H)|^(1/2)...

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

Erdős, Hajnal: Suppose G has n vertices and no induced copy of H. Is there an ľ > 0, depending only on H, so that the homogeneous number of G (i.e., t...

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

Chung, Graham: Define the discrepancy of a graph to be the largest value of D(S,T) = | |S||T|/2 - e(S,T) |, over all disjoint vertex sets S and T. Sup...

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

Seymour/Szekeres: The "cycle double cover conjecture" states that every bridgeless graph contains a set of cycles which cover each edge of the graph e...

Seymour: "Seymour's Second Neighborhood Conjecture" Any oriented graph has a vertex whose outdegree is at most its second outdegree (vertices at direc...

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

Brouwer : Is it true that the sum of the k largest Laplacian eigenvalues of a graph with m edges is at most k(k+1)/2+m?...

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

: Given two permutations σ and τ, what is the expected number of copies of σ in a permutation chosen uniformly at random from those permutations on n ...

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

Propp: Show that the inversion permutation, i.e., the one which takes s to 1/s mod p, has longest increasing subsequence of length 2√ p(1+o(1)), i.e.,...

What is the length of the shortest sequence in [n]* containing, as a (consecutive) subword, each permutation of [n]? See this, this, this, this, and t...

Linal/Luria: A d-dimensional permutation of order n is an n-by-n-by-...-by-n (d+1)-dimensional array of zeroes and ones, with the property that every ...