Recent Activity

Graph Theory » Hypergraphs

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

Keywords:

Posted by tchow
updated December 17th, 2009

Graph Theory » Coloring » Vertex coloring

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

Posted by DFR
updated November 30th, 2009

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$ , 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) Find $d(k,n)$ .

Conjecture (SE) $d(k,n)=2n-1$ .

Keywords:

Posted by Vadim Lioubimov
updated November 27th, 2009

add new comment

Graph Theory » Coloring » Vertex coloring

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

Posted by berger
updated November 19th, 2009

Graph Theory » Basic G.T.

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

Posted by mdevos
updated November 8th, 2009

add new comment

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

Posted by rybu
updated November 7th, 2009

add new comment

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

Posted by rybu
updated November 7th, 2009

add new comment

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

Posted by rybu
updated November 7th, 2009

add new comment

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

Posted by rybu
updated November 7th, 2009

add new comment

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

Posted by rybu
updated November 7th, 2009

add new comment

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

Posted by rybu
updated November 7th, 2009

add new comment

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

Posted by rybu
updated November 6th, 2009

add new comment

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

Posted by rybu
updated November 6th, 2009

add new comment

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

Posted by rybu
updated November 6th, 2009

add new comment

Graph Theory » Topological G.T. » Crossing numbers

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

Author(s): Pach; Tóth

Problem Does the following equality hold for every graph $G$ ?

$\text{pair-cr}(G) = \text{cr}(G)$

The crossing number $\text{cr}(G)$ of a graph $G$ is the minimum number of edge crossings in any drawing of $G$ in the plane. In the pairwise crossing number $\text{pair-cr}(G)$ , we minimize the number of pairs of edges that cross.

Keywords: crossing number; pair-crossing number

Posted by cibulka
updated November 3rd, 2009

add new comment

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

Author(s): Beneš; Folklore; Stone

Given integers $k,n \ge 2$ , the 2-stage Shuffle-Exchange graph/network, denoted $\text{SE}(k,n)$ , is the simple $k$ -regular bipartite graph with the ordered pair $(U,V)$ of linearly labeled parts $U:=\{u_0,\dots,u_{t-1}\}$ and $V:=\{v_0,\dots,v_{t-1}\}$ , where $t:=k^{n-1}$ , such that vertices $u_i$ and $v_j$ are adjacent if and only if $(j - ki) \text{ mod } t < k$ (see Fig.1).

Given integers $k,n,r \ge 2$ , the $r$ -stage Shuffle-Exchange graph/network, denoted $(\text{SE}(k,n))^{r-1}$ , is the proper (i.e., respecting all the orders) concatenation of $r-1$ identical copies of $\text{SE}(k,n)$ (see Fig.1).

Let $r(k,n)$ be the smallest integer $r\ge 2$ such that the graph $(\text{SE}(k,n))^{r-1}$ is rearrangeable.

Problem Find $r(k,n)$ .

Conjecture $r(k,n)=2n-1$ .

Keywords:

Posted by Vadim Lioubimov
updated October 30th, 2009

add new comment | 1 attachment

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

Posted by David Wood
updated October 19th, 2009

add new comment

Edge-Colouring Geometric Complete Graphs ★★

Author(s): Hurtado

Question What is the minimum number of colours such that every complete geometric graph on $n$ vertices has an edge colouring such that:

[Variant A] crossing edges get distinct colours,
[Variant B] disjoint edges get distinct colours,
[Variant C] non-disjoint edges get distinct colours,
[Variant D] non-crossing edges get distinct colours.

Keywords: geometric complete graph, colouring

Posted by David Wood
updated October 19th, 2009

add new comment

Number of Cliques in Minor-Closed Classes ★★

Author(s): Wood

Question Is there a constant $c$ such that every $n$ -vertex $K_t$ -minor-free graph has at most $c^tn$ cliques?

Keywords: clique; graph; minor

Posted by David Wood
updated October 12th, 2009

add new comment

Graph Theory » Graph Algorithms

A gold-grabbing game ★★

Author(s): Rosenfeld

Setup Fix a tree $T$ and for every vertex $v \in V(T)$ a non-negative integer $g(v)$ which we think of as the amount of gold at $v$ .

2-Player game Players alternate turns. On each turn, a player chooses a leaf vertex $v$ of the tree, takes the gold at this vertex, and then deletes $v$ . The game ends when the tree is empty, and the winner is the player who has accumulated the most gold.

Problem Find optimal strategies for the players.

Keywords: game; tree

Posted by mdevos
updated October 4th, 2009