Recent Activity

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


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 $ D $ be the open unit disk in the complex plane and let $ U_1,\dots,U_n $ be open sets such that $ \bigcup_{j=1}^nU_j=D\setminus\{0\} $. Suppose there are injective holomorphic functions $ f_j : U_j \to \mathbb{C}, $ $ j=1,\ldots,n, $ such that for the differentials we have $ {\rm d}f_j={\rm d}f_k $ on any intersection $ U_j\cap U_k $. Then those differentials glue together to a meromorphic 1-form on $ D $.

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 $ R,C $, their Tensor Product $ R \otimes C $ is the code that consists of the matrices whose rows are codewords of $ R $ and whose columns are codewords of $ C $. The product $ R \otimes C $ is said to be robust if whenever a matrix $ M $ is far from $ R \otimes C $, the rows (columns) of $ M $ are far from $ R $ ($ C $, respectively).

The problem is to give a characterization of the pairs $ R,C $ whose tensor product is robust.

Keywords: codes; coding; locally testable; robustness

Schanuel's Conjecture ★★★★

Author(s): Schanuel

Conjecture   Given any $ n $ complex numbers $ z_1,...,z_n $ which are linearly independent over the rational numbers $ \mathbb{Q} $, then the extension field $ \mathbb{Q}(z_1,...,z_n,\exp(z_1),...,\exp(z_n)) $ has transcendence degree of at least $ n $ over $ \mathbb{Q} $.

Keywords: algebraic independence

Beneš Conjecture ★★★

Author(s): Beneš

Given a partition $ \bf h $ of a finite set $ E $, stabilizer of $ \bf h $, denoted $ S(\bf h) $, is the group formed by all permutations of $ E $ preserving each block in $ \mathbf h $.

Problem  ($ \star $)   Find a sufficient condition for a sequence of partitions $ {\bf h}_1, \dots, {\bf h}_\ell $ of $ E $ to be universal, i.e. to yield the following decomposition of the symmetric group $ \frak S(E) $ on $ E $: $$ (1)\quad \frak S(E) = S({\bf h}_1) S({\bf h}_2) \dots S({\bf h}_\ell).  $$ In particular, what about the sequence $ \bf h,\delta(\bf h),\dots,\delta^{\ell-1}(\bf h) $, where $ \delta $ is a permutation of $ E $?
Conjecture  (Beneš)   Let $ \bf u $ be a uniform partition of $ E $ and $ \varphi $ be a permutation of $ E $ such that $ \bf u\wedge\varphi(\bf u)=\bf 0 $. Suppose that the set $ \big(\varphi S({\bf u})\big)^{n} $ is transitive, for some integer $ n\ge2 $. Then $$ \frak S(E) = \big(\varphi S({\bf u})\big)^{2n-1}. $$


Frankl's union-closed sets conjecture ★★

Author(s): Frankl

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


Double-critical graph conjecture ★★

Author(s): Erdos; Lovasz

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

Conjecture   $ K_n $ is the only $ n $-chromatic double-critical graph

Keywords: coloring; complete graph

Shuffle-Exchange Conjecture ★★★

Author(s): Beneš; Folklore; Stone

Given integers $ k,n\ge2 $, let $ d(k,n) $ be the smallest integer $ d\ge2 $ such that the symmetric group $ \frak S $ on the set of all words of length $ n $ over a $ k $-letter alphabet can be generated as $ \frak S = (\sigma \frak G)^d:=\sigma\frak G \sigma\frak G \dots \sigma\frak G $ ($ d $ times), where $ \sigma\in \frak S $ is the shuffle permutation defined by $ \sigma(x_1 x_2 \dots x_{n}) = x_2 \dots x_{n} x_1 $, and $ \frak G $ is the exchange group consisting of all permutations in $ \frak S $ preserving the first $ n-1 $ letters in the words.

Problem  (SE)   Evaluate $ d(k,n) $.
Conjecture  (SE)   $ d(k,n)=2n-1 $, for all $ k,n\ge2 $.


Strong colorability ★★★

Author(s): Aharoni; Alon; Haxell

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

Conjecture   If $ \Delta $ is the maximal degree of a graph $ G $, then $ G $ is strongly $ 2 \Delta $-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 $ r $, all but finitely many $ r $-regular graphs have friendly partitions?

Keywords: edge-cut; partition; regular

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?

Keywords: 4-sphere; algorithm

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

Author(s): Smale

Problem   $ Diff(S^4) $ has the homotopy-type of a product space $ Diff(S^4) \simeq \mathbb O_5 \times Diff(D^4) $ where $ Diff(D^4) $ 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 $ Diff(D^4) $.

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 $ \mathbb R^3 $ 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 $ 3 $-spheres bound (rational) homology $ 4 $-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 $ L $ in $ S^3 $, let the symmetry group of $ L $ be denoted $ Sym(L) = \pi_0 Diff(S^3,L) $ ie: isotopy classes of diffeomorphisms of $ S^3 $ which preserve $ L $, where the isotopies are also required to preserve $ L $.

Now let $ L $ be a hyperbolic link. Assume $ L $ has the further `Brunnian' property that there exists a component $ L_0 $ of $ L $ such that $ L \setminus L_0 $ is the unlink. Let $ A_L $ be the subgroup of $ Sym(L) $ consisting of diffeomorphisms of $ S^3 $ which preserve $ L_0 $ together with its orientation, and which preserve the orientation of $ S^3 $.

There is a representation $ A_L \to \pi_0 Diff(L \setminus L_0) $ given by restricting the diffeomorphism to the $ L \setminus L_0 $. It's known that $ A_L $ is always a cyclic group. And $ \pi_0 Diff(L \setminus L_0) $ is a signed symmetric group -- the wreath product of a symmetric group with $ \mathbb Z_2 $.

Problem: What representations can be obtained?

Keywords: knot space; symmetry

Slice-ribbon problem ★★★★

Author(s): Fox

Conjecture   Given a knot in $ S^3 $ which is slice, is it a ribbon knot?

Keywords: cobordism; knot; ribbon; slice

Smooth 4-dimensional Poincare conjecture ★★★★

Author(s): Poincare; Smale; Stallings

Conjecture   If a $ 4 $-manifold has the homotopy type of the $ 4 $-sphere $ S^4 $, is it diffeomorphic to $ S^4 $?

Keywords: 4-manifold; poincare; sphere

Smooth 4-dimensional Schoenflies problem ★★★★

Author(s): Alexander

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

Keywords: 4-dimensional; Schoenflies; sphere