Mathematics Problem Archive

Give an algorithm and/or a good characterization to decide if a red-blue edge-coloured bipartite graph contains a perfect matching with exactly k red ...

Decide whether a graph is globally rigid in three-dimensional space....

Can we decide in polynomial time whether a given graph is rigid in 3-dimensional space?...

In a graph G=(V,E) with a root node r, two spanning trees $T_1$ and $T_2$ are called r-independent if for any node x in V-r, the unique paths between ...

Is it true that every smooth polytope has the integer decomposition property?...

Given an undirected graph G=(V,E), find a maximum cardinality 2-matching containing no cycles of length 4 in polynomial time....

Given a graph G=(V,E), and weight and capacity functions $w,u: E \to {\mathbb R_+}$ defined on the edge set, is there a combinatorial, strongly polyno...

Given a bipartite graph G with edge weights, can we find in polynomial time a maximum weight k-element matching in G that can be extended to a perfect...

Let G=(V,E) be an undirected graph and let $(s_1,t_1), (s_2,t_2)$ be two node pairs. Give a combinatorial, polynomial-time algorithm to find edge-disj...

Can we find a minimum k-way cut in a capacitated hypergraph in polynomial time, if k is fixed?...

For a plane graph $G$, let $g(G)$ denote the length of the shortest face in $G$. For a (not necessarily proper) $k$-coloring of $V(G)$ we say that a f...

Any $2k$-edge-connected (possibly infinite) multigraph admits a $k$-edge-connected orientation....

Find a good characterization for undirected graphs having a strongly connected (more generally k-edge-connected) orientation so that the in-degree of ...

Given a directed graph whose arcs are coloured red and blue and integers r and b, can we decide in polynomial time whether the digraph has a cut with ...

The rotor-routing halting problem asks the following: Given an initial chip-and-rotor configuration on a digraph, does the rotor-routing game eventual...

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

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

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

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

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

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

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

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

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

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 two permutations σ and τ, what is the expected number of copies of σ in a permutation chosen uniformly at random from those permutations on n ...

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

Is the poset of integer partitions ordered by refinement Sperner?...

Griggs, Lu: ("Diamond-Free Posets Problem") What is the size of the largest subset of the Boolean lattice B_(n) which includes no B_(2) as a subposet?...

Griggs, Lu: For any poset P, define ex(n,P) to be the size of the largest subset of the Boolean lattice B_(n) which includes no (injective) copy of P ...

Kislitsyn: "1/3 - 2/3 Conjecture" For every poset that is not a chain, there is some pair of elements x and y so that x appears above y in a random li...

Erdős: In the binary expansion of sqrt(2), are there arbitrarily long sequences of 0's? Can you find a single algebraic number with this property?...

Alon, Peres: Given any subset S of the integers modulo a prime p, what is the least K=K(p) for which there always exists an m so that mS has no gap of...

/Solymosi: Finite field Sylvester-Gallai: Suppose S is a tranversal of Z_(p)^(2), i.e., a set of points in the affine plane so that every row and colu...

Erdős-Turán: Suppose that S is a set of positive integers with the property that S+S -- that is, all sums of the form s_(1)+s_(2) for s_(1), s_(2) in ...

Olson: Every sequence of 2n-1 elements from a group of order n (written multiplicatively) has an n element subsequence with product 1 (in the given or...

Wills, Cusick: Suppose k runners having distinct constant speeds start at a common point and run laps on a unit length circular track. Then for any gi...

Erdős: Suppose that S is a set of positive integers with the property that no element is the sum of a nonempty set of other elements. Such a set is ca...