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

Keywords: algorithm; Exponential-time algorithm; homomorphism

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

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

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?

Keywords: approximation algorithms; planar graph; polynomial algorithm

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

Keywords: approximation algorithms; Disjoint paths; planar graph; polynomial algorithm

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

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

Keywords: Essential singularity; Holomorphic functions; Picard's theorem; Residue of 1-form; Riemann surfaces

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

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