Search

Results 21-40 of 43

Graph Theory » Coloring » Vertex coloring

Mixing Circular Colourings ★

Author(s): Brewster; Noel

Question Is $\mathfrak{M}_c(G)$ always rational?

Keywords: discrete homotopy; graph colourings; mixing

Posted by Jon Noel
updated September 22nd, 2012

add new comment

Topology

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

Logic » Finite Model Theory

Blatter-Specker Theorem for ternary relations ★★

Author(s): Makowsky

Let $C$ be a class of finite relational structures. We denote by $f_C(n)$ the number of structures in $C$ over the labeled set $\{0, \dots, n-1 \}$ . For any class $C$ definable in monadic second-order logic with unary and binary relation symbols, Specker and Blatter showed that, for every $m \in \mathbb{N}$ , the function $f_C(n)$ is ultimately periodic modulo $m$ .

Question Does the Blatter-Specker Theorem hold for ternary relations.

Keywords: Blatter-Specker Theorem; FMT00-Luminy

Posted by dberwanger
updated May 18th, 2012

add new comment

Combinatorics

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

Keywords:

Posted by Vadim Lioubimov
updated November 27th, 2009

add new comment

Theoretical Comp. Sci. » Complexity » Hardness of Approximation

Refuting random 3SAT-instances on $O(n)$ clauses (weak form) ★★★

Author(s): Feige

Conjecture For every rational $\epsilon > 0$ and every rational $\Delta$ , there is no polynomial-time algorithm for the following problem.

Given is a 3SAT (3CNF) formula $I$ on $n$ variables, for some $n$ , and $m = \floor{\Delta n}$ clauses drawn uniformly at random from the set of formulas on $n$ variables. Return with probability at least 0.5 (over the instances) that $I$ is typical without returning typical for any instance with at least $(1 - \epsilon)m$ simultaneously satisfiable clauses.

Keywords: NP; randomness in TCS; satisfiability

Posted by cwenner
updated February 27th, 2009

add new comment

Graph Theory » Coloring » Vertex coloring

Ohba's Conjecture ★★

Author(s): Ohba

Conjecture If $|V(G)|\leq 2\chi(G)+1$ , then $\chi_\ell(G)=\chi(G)$ .

Keywords: choosability; chromatic number; complete multipartite graph; list coloring

Posted by Jon Noel
updated May 18th, 2011

add new comment | 2 attachments

Graph Theory

Beneš Conjecture (graph-theoretic form) ★★★

Author(s): Beneš

Problem ( $\dag$ ) Find a sufficient condition for a straight $\ell$ -stage graph to be rearrangeable. In particular, what about a straight uniform graph?

Conjecture ( $\diamond$ ) Let $L$ be a simple regular ordered $2$ -stage graph. Suppose that the graph $L^m$ is externally connected, for some $m\ge1$ . Then the graph $L^{2m}$ is rearrangeable.

Keywords:

Posted by Vadim Lioubimov
updated April 17th, 2010

add new comment | 3 attachments

Combinatorics

Beneš Conjecture ★★★

Author(s): Beneš

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

Problem ( $\star$ ) Find a sufficient condition for a sequence of partitions ${\bf h}_1, \dots, {\bf h}_\ell$ of $E$ to be complete, i.e. such that the product of their stabilizers $S({\bf h}_1) S({\bf h}_2) \dots S({\bf h}_\ell)$ is equal to the whole symmetric group $\frak S(E)$ on $E$ . In particular, what about completeness of the sequence $\bf h,\delta(\bf h),\dots,\delta^{\ell-1}(\bf h)$ , given a partition $\bf h$ of $E$ and a permutation $\delta$ 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}.$

Keywords:

Posted by Vadim Lioubimov
updated January 3rd, 2010

add new comment

Topology

Set of connected components of a filter ★★

Author(s): Porton

Conjecture The set of connected components (regarding a funcoid or a reloid) is a partition of a filter.

Keywords: filter; funcoid; reloid

Posted by porton
updated September 2nd, 2007

1 comment

Topology

Inward reloid corresponding to a funcoid corresponding to convex reloid ★★

Author(s): Porton

Conjecture $( \mathsf{\tmop{RLD}})_{\tmop{in}} ( \mathsf{\tmop{FCD}}) f = f$ for any convex reloid $f$ .

Keywords: convex reloid; funcoid; functor; inward reloid; reloid

Posted by porton
updated September 2nd, 2007

1 comment

Topology

Distributivity of union of funcoids corresponding to reloids ★★

Author(s): Porton

Conjecture $\bigcup \left\langle ( \mathsf{\tmop{FCD}}) \right\rangle S = ( \mathsf{\tmop{FCD}}) \bigcup S$ if $S\in\mathscr{P}\mathsf{RLD}(A;B)$ is a set of reloids from a set $A$ to a set $B$ .

Keywords: funcoid; infinite distributivity; reloid

Posted by porton
updated September 2nd, 2007

1 comment

Combinatorics

Square achievement game on an n x n grid ★★

Author(s): Erickson

Problem Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an $n \times n$ grid. The first player (if any) to occupy four cells at the vertices of a square with horizontal and vertical sides is the winner. What is the outcome of the game given optimal play? Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15.

Keywords: game

Posted by Martin Erickson
updated September 13th, 2011

9 comments

Topology

Outward reloid corresponding to a funcoid corresponding to convex reloid ★★

Author(s): Porton

Conjecture $( \mathsf{\tmop{RLD}})_{\tmop{out}} ( \mathsf{\tmop{FCD}}) f = f$ for any convex reloid $f$ .

Keywords: convex reloid; funcoid; functor; outward reloid; reloid

Posted by porton
updated September 2nd, 2007

1 comment

Geometry

Covering a square with unit squares ★★

Author(s):

Conjecture For any integer $n \geq 1$ , it is impossible to cover a square of side greater than $n$ with $n^2+1$ unit squares.

Keywords:

Posted by Martin Erickson
updated August 1st, 2011

10 comments

Topology

Reloid corresponding to funcoid is between outward and inward reloid ★★

Author(s): Porton

Conjecture For any funcoid $f$ and reloid $g$ having the same source and destination $( \mathsf{\tmop{RLD}})_{\tmop{out}} f \subseteq g \subseteq ( \mathsf{\tmop{RLD}})_{\tmop{in}} f \Leftrightarrow ( \mathsf{\tmop{FCD}}) g = f.$

Keywords: funcoid; inward reloid; outward reloid; reloid

Posted by porton
updated September 2nd, 2007

1 comment

Topology

Monovalued reloid and its restrictions ★★

Author(s): Porton

Conjecture A reloid $f$ is monovalued iff $\forall g \in \mathsf{\tmop{RLD}} : (g \subseteq f \Rightarrow \exists \mathcal{A \in \mathscr{F}} : g = f|_{\mathcal{A}})$ .

Keywords: monovalued morphism; monovalued reloid; reloid

Posted by porton
updated September 2nd, 2007

1 comment

Topology

Intersection of complete funcoids ★★

Author(s): Porton

Conjecture If $f$ , $g$ are complete funcoids (generalized closures) then $f \cap^{\mathsf{\tmop{FCD}}} g$ is a complete funcoid (generalized closure).

Keywords: complete funcoid; funcoid; generalized closure

Posted by porton
updated September 2nd, 2007

1 comment

Graph Theory » Basic G.T. » Matchings

The Berge-Fulkerson conjecture ★★★★

Author(s): Berge; Fulkerson

Conjecture If $G$ is a bridgeless cubic graph, then there exist 6 perfect matchings $M_1,\ldots,M_6$ of $G$ with the property that every edge of $G$ is contained in exactly two of $M_1,\ldots,M_6$ .

Keywords: cubic; perfect matching

Posted by mdevos
updated November 23rd, 2011

9 comments

Topology