Recent Activity

The stubborn list partition problem ★★

Author(s): Cameron; Eschen; Hoang; Sritharan

Problem   Does there exist a polynomial time algorithm which takes as input a graph and for every vertex a subset of , and decides if there exists a partition of into so that only if and so that are independent, is a clique, and there are no edges between and ?

Keywords: list partition; polynomial algorithm

Long rainbow arithmetic progressions ★★

Author(s): Fox; Jungic; Mahdian; Nesetril; Radoicic

For let denote the minimal number such that there is a rainbow in every equinumerous -coloring of for every

Conjecture   For all , .

Keywords: arithmetic progression; rainbow

Reconstruction conjecture ★★★★

Author(s): Kelly; Ulam

The deck of a graph is the multiset consisting of all unlabelled subgraphs obtained from by deleting a vertex in all possible ways (counted according to multiplicity).

Conjecture   If two graphs on vertices have the same deck, then they are isomorphic.

Keywords: reconstruction

Finding k-edge-outerplanar graph embeddings ★★

Author(s): Bentz

Conjecture   It has been shown that a -outerplanar embedding for which is minimal can be found in polynomial time. Does a similar result hold for -edge-outerplanar graphs?

Keywords: planar graph; polynomial algorithm

Approximation ratio for k-outerplanar graphs ★★

Author(s): Bentz

Conjecture   Is the approximation ratio for the Maximum Edge Disjoint Paths (MaxEDP) or the Maximum Integer Multiflow problem (MaxIMF) bounded by a constant in -outerplanar graphs or tree-width graphs?

Approximation Ratio for Maximum Edge Disjoint Paths problem ★★

Author(s): Bentz

Conjecture   Can the approximation ratio be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than -hardness?

Beneš Conjecture (graph-theoretic form) ★★★

Author(s): Beneš

Problem  ()   Find a sufficient condition for a straight -stage graph to be rearrangeable. In particular, what about a straight uniform graph?
Conjecture  ()   Let be a simple regular ordered -stage graph. Suppose that the graph is externally connected, for some . Then the graph is rearrangeable.

Keywords:

Seymour's self-minor conjecture ★★★

Author(s): Seymour

Conjecture   Every infinite graph is a proper minor of itself.

Keywords: infinite graph; minor

Stable matching in the couples problem ★★

Author(s): Bianco; Hartke; Larimer

Conjecture 1 In the couples problem, if the acceptability graph is a tree, then a stable matching exists for any set of preference lists.

Keywords: acceptability graph; couples matching; cycle; tree

Perfect 2-error-correcting codes over arbitrary finite alphabets. ★★

Author(s):

Conjecture   Does there exist a nontrivial perfect 2-error-correcting code over any finite alphabet, other than the ternary Golay code?

Keywords: 2-error-correcting; code; existence; perfect; perfect code

Are there an infinite number of lucky primes? ★

Author(s): Lazarus: Gardiner: Metropolis; Ulam

Conjecture   If every second positive integer except 2 is remaining, then every third remaining integer except 3, then every fourth remaining integer etc. , an infinite number of the remaining integers are prime.

Keywords: lucky; prime; seive

Something like Picard for 1-forms ★★

Author(s): Elsner

Conjecture   Let be the open unit disk in the complex plane and let be open sets such that . Suppose there are injective holomorphic functions such that for the differentials we have on any intersection . Then those differentials glue together to a meromorphic 1-form on .

The robustness of the tensor product ★★★

Author(s): Ben-Sasson; Sudan

Problem   Given two codes , their Tensor Product is the code that consists of the matrices whose rows are codewords of and whose columns are codewords of . The product is said to be robust if whenever a matrix is far from , the rows (columns) of are far from (, respectively).

The problem is to give a characterization of the pairs whose tensor product is robust.

Keywords: codes; coding; locally testable; robustness

Schanuel's Conjecture ★★★

Author(s): Schanuel

Conjecture   Given any complex numbers which are linearly independent over the rational numbers , then the extension field has transcendence degree of at least over .

Keywords: algebraic independence

Beneš Conjecture ★★★

Author(s): Beneš

Given a partition of a finite set , stabilizer of , denoted , is the group formed by all permutations of preserving each block in .

Problem  ()   Find a sufficient condition for a sequence of partitions of to be universal, i.e. to yield the following decomposition of the symmetric group on :

In particular, what about the sequence , where is a permutation of ?

Conjecture  (Beneš)   Let be a uniform partition of and be a permutation of such that . Suppose that the set is transitive, for some integer . Then

Keywords:

Separators in string graphs ★★

Author(s): Fox; Pach; Tóth

Conjecture   Every string graph with edges has a separator of size .

Keywords: separator; string graphs

Frankl's union-closed sets conjecture ★★

Author(s): Frankl

Conjecture   Let be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists such that is an element of at least half the members of .

Keywords:

Double-critical graph conjecture ★★

Author(s): Erdos; Lovasz

A connected simple graph is called double-critical, if removing any pair of adjacent vertexes lowers the chromatic number by two.

Conjecture   is the only -chromatic double-critical graph

Keywords: coloring; complete graph

Shuffle-Exchange Conjecture ★★★

Author(s): Beneš; Folklore; Stone

Given integers , let be the smallest integer such that the symmetric group on the set of all words of length over a -letter alphabet can be generated as , where is the shuffle permutation defined by , and is the exchange group consisting of all permutations in preserving the first letters in the words.

Problem  (SE)   Find .
Conjecture  (SE)   .

Keywords:

Strong colorability ★★★

Author(s): Aharoni; Alon; Haxell

Let be a positive integer. We say that a graph is strongly -colorable if for every partition of the vertices to sets of size at most there is a proper -coloring of in which the vertices in each set of the partition have distinct colors.

Conjecture   If is the maximal degree of a graph , then is strongly -colorable.

Keywords: strong coloring