# Recent Activity

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

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

## Friendly partitions ★★

Author(s): DeVos

A *friendly* partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.

**Problem**Is it true that for every , all but finitely many -regular graphs have friendly partitions?

## Is there an algorithm to determine if a triangulated 4-manifold is combinatorially equivalent to the 4-sphere? ★★★

Author(s): Novikov

**Problem**Is there an algorithm which takes as input a triangulated 4-manifold, and determines whether or not this manifold is combinatorially equivalent to the 4-sphere?

## What is the homotopy type of the group of diffeomorphisms of the 4-sphere? ★★★★

Author(s): Smale

**Problem**has the homotopy-type of a product space where is the group of diffeomorphisms of the 4-ball which restrict to the identity on the boundary. Determine some (any?) homotopy or homology groups of .

Keywords: 4-sphere; diffeomorphisms

## Which compact boundaryless 3-manifolds embed smoothly in the 4-sphere? ★★★

Author(s): Kirby

**Problem**Determine a computable set of invariants that allow one to determine, given a compact boundaryless 3-manifold, whether or not it embeds smoothly in the 4-sphere. This should include a constructive procedure to find an embedding if the manifold is embeddable.

Keywords: 3-manifold; 4-sphere; embedding

## Fundamental group torsion for subsets of Euclidean 3-space ★★

Author(s): Ancient/folklore

**Problem**Does there exist a subset of such that its fundamental group has an element of finite order?

Keywords: subsets of euclidean space; torsion

## Which homology 3-spheres bound homology 4-balls? ★★★★

Author(s): Ancient/folklore

**Problem**Is there a complete and computable set of invariants that can determine which (rational) homology -spheres bound (rational) homology -balls?

Keywords: cobordism; homology ball; homology sphere

## Realisation problem for the space of knots in the 3-sphere ★★

Author(s): Budney

**Problem**Given a link in , let the symmetry group of be denoted ie: isotopy classes of diffeomorphisms of which preserve , where the isotopies are also required to preserve .

Now let be a hyperbolic link. Assume has the further `Brunnian' property that there exists a component of such that is the unlink. Let be the subgroup of consisting of diffeomorphisms of which preserve together with its orientation, and which preserve the orientation of .

There is a representation given by restricting the diffeomorphism to the . It's known that is always a cyclic group. And is a signed symmetric group -- the wreath product of a symmetric group with .

Problem: What representations can be obtained?

Keywords: knot space; symmetry

## Slice-ribbon problem ★★★★

Author(s): Fox

**Conjecture**Given a knot in which is slice, is it a ribbon knot?

## Smooth 4-dimensional Poincare conjecture ★★★★

Author(s): Poincare; Smale; Stallings

**Conjecture**If a -manifold has the homotopy type of the -sphere , is it diffeomorphic to ?

Keywords: 4-manifold; poincare; sphere

## Smooth 4-dimensional Schoenflies problem ★★★★

Author(s): Alexander

**Problem**Let be a -dimensional smooth submanifold of , diffeomorphic to . By the Jordan-Brouwer separation theorem, separates into the union of two compact connected -manifolds which share as a common boundary. The Schoenflies problem asks, are these -manifolds diffeomorphic to ? ie: is unknotted?

Keywords: 4-dimensional; Schoenflies; sphere

## Are different notions of the crossing number the same? ★★★

**Problem**Does the following equality hold for every graph ?

The crossing number of a graph is the minimum number of edge crossings in any drawing of in the plane. In the *pairwise crossing number* , we minimize the number of pairs of edges that cross.

Keywords: crossing number; pair-crossing number

## Shuffle-Exchange Conjecture (graph-theoretic form) ★★★

Author(s): Beneš; Folklore; Stone

Given integers , the *2-stage Shuffle-Exchange graph/network*, denoted , is the simple -regular bipartite graph with the ordered pair of linearly labeled parts and , where , such that vertices and are adjacent if and only if (see Fig.1).

Given integers , the *-stage Shuffle-Exchange graph/network*, denoted , is the proper (i.e., respecting all the orders) concatenation of identical copies of (see Fig.1).

Let be the smallest integer such that the graph is rearrangeable.

**Problem**Find .

**Conjecture**.

Keywords:

## Partition of Complete Geometric Graph into Plane Trees ★★

Author(s):

**Conjecture**Every complete geometric graph with an even number of vertices has a partition of its edge set into plane (i.e. non-crossing) spanning trees.

Keywords: complete geometric graph, edge colouring