# Recent Activity

## Unsolvability of word problem for 2-knot complements ★★★

Author(s): Gordon

Problem   Does there exist a smooth/PL embedding of in such that the fundamental group of the complement has an unsolvable word problem?

Keywords: 2-knot; Computational Complexity; knot theory

## Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

Question

Is there an algorithm that decides, for input graphs and , whether there exists a homomorphism from to in time for some constant ?

## Exact colorings of graphs ★★

Author(s): Erickson

Conjecture   For , let be the statement that given any exact -coloring of the edges of a complete countably infinite graph (that is, a coloring with colors all of which must be used at least once), there exists an exactly -colored countably infinite complete subgraph. Then is true if and only if , , or .

Keywords: graph coloring; ramsey theory

## Dividing up the unrestricted partitions ★★

Author(s): David S.; Newman

Begin with the generating function for unrestricted partitions:

(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...

Now change some of the plus signs to minus signs. The resulting series will have coefficients congruent, mod 2, to the coefficients of the generating series for unrestricted partitions. I conjecture that the signs may be chosen such that all the coefficients of the series are either 1, -1, or zero.

Keywords: congruence properties; partition

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

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

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