Home

Recent Activity

Geometry

Convex uniform 5-polytopes ★★

Author(s):

Problem   Enumerate all convex uniform 5-polytopes.

Keywords:

Posted by ACW
updated May 24th, 2012
add new comment
Logic » Finite Model Theory

MSO alternation hierarchy over pictures ★★

Author(s): Grandjean

Question   Is the MSO-alternation hierarchy strict for pictures that are balanced, in the sense that the width and the length are polynomially (or linearly) related.

Keywords: FMT12-LesHouches; MSO, alternation hierarchy; picture languages

Posted by dberwanger
updated May 18th, 2012
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
Logic » Finite Model Theory

Monadic second-order logic with cardinality predicates ★★

Author(s): Courcelle

The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic formulas:

    \item $ \text{``}\,\mathrm{Card}(X) = \mathrm{Card}(Y)\,\text{''} $ \item $ \text{``}\,\mathrm{Card}(X) \text{ belongs to } A\,\text{''} $

where $ A $ is a fixed recursive set of integers.

Let us fix $ k $ and a closed formula $ F $ in this language.

Conjecture   Is it true that the validity of $ F $ for a graph $ G $ of tree-width at most $ k $ can be tested in polynomial time in the size of $ G $?

Keywords: bounded tree width; cardinality predicates; FMT03-Bedlewo; MSO

Posted by dberwanger
updated May 18th, 2012
add new comment
Logic » Finite Model Theory

Order-invariant queries ★★

Author(s): Segoufin

Question  
    \item Does $ {<}\text{-invariant\:FO} = \text{FO} $ hold over graphs of bounded tree-width? \item Is $ {<}\text{-invariant\:FO} $ included in $ \text{MSO} $ over graphs? \item Does $ {<}\text{-invariant\:FO} $ have a 0-1 law? \item Are properties of $ {<}\text{-invariant\:FO} $ Hanf-local? \item Is there a logic (with an effective syntax) that captures $ {<}\text{-invariant\:FO} $?

Keywords: Effective syntax; FMT12-LesHouches; Locality; MSO; Order invariance

Posted by dberwanger
updated May 18th, 2012
add new comment
Logic » Finite Model Theory

Fixed-point logic with counting ★★

Author(s): Blass

Question   Can either of the following be expressed in fixed-point logic plus counting:
    \item Given a graph, does it have a perfect matching, i.e., a set $ M $ of edges such that every vertex is incident to exactly one edge from $ M $? \item Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant?

Keywords: Capturing PTime; counting quantifiers; Fixed-point logic; FMT03-Bedlewo

Posted by dberwanger
updated May 18th, 2012
add new comment
Number Theory

Birch & Swinnerton-Dyer conjecture ★★★★

Author(s):

Conjecture   Let $ E/K $ be an elliptic curve over a number field $ K $. Then the order of the zeros of its $ L $-function, $ L(E, s) $, at $ s = 1 $ is the Mordell-Weil rank of $ E(K) $.

Keywords:

Posted by eyoong
updated May 12th, 2012
add new comment
Number Theory

Algebraic independence of pi and e ★★★

Author(s):

Conjecture   $ \pi $ and $ e $ are algebraically independent

Keywords: algebraic independence

Posted by porton
updated April 29th, 2012
6 comments
Number Theory » Analytic N.T.

Is Skewes' number e^e^e^79 an integer? ★★

Author(s):

Conjecture  

Skewes' number $ e^{e^{e^{79}}} $ is not an integer.

Keywords:

Posted by VladimirReshetnikov
updated April 29th, 2012
1 comment
Graph Theory

Minimal graphs with a prescribed number of spanning trees ★★

Author(s): Azarija; Skrekovski

Conjecture   Let $ n \geq 3 $ be an integer and let $ \alpha(n) $ denote the least integer $ k $ such that there exists a simple graph on $ k $ vertices having precisely $ n $ spanning trees. Then $ \alpha(n) = o(\log{n}). $

Keywords: number of spanning trees, asymptotics

Posted by azi
updated April 22nd, 2012
add new comment | 1 attachment
Topology

Sticky Cantor sets ★★

Author(s):

Conjecture   Let $ C $ be a Cantor set embedded in $ \mathbb{R}^n $. Is there a self-homeomorphism $ f $ of $ \mathbb{R}^n $ for every $ \epsilon $ greater than $ 0 $ so that $ f $ moves every point by less than $ \epsilon $ and $ f(C) $ does not intersect $ C $? Such an embedded Cantor set for which no such $ f $ exists (for some $ \epsilon $) is called "sticky". For what dimensions $ n $ do sticky Cantor sets exist?

Keywords: Cantor set

Posted by porton
updated April 10th, 2012
2 comments
Group Theory

Subgroup formed by elements of order dividing n ★★

Author(s): Frobenius

Conjecture  

Suppose $ G $ is a finite group, and $ n $ is a positive integer dividing $ |G| $. Suppose that $ G $ has exactly $ n $ solutions to $ x^{n} = 1 $. Does it follow that these solutions form a subgroup of $ G $?

Keywords: order, dividing

Posted by dlh12
updated March 30th, 2012
4 comments
Number Theory

Giuga's Conjecture on Primality ★★

Author(s): Giuseppe Giuga

Conjecture   $ p $ is a prime iff $ ~\displaystyle \sum_{i=1}^{p-1} i^{p-1} \equiv -1 \pmod p $

Keywords: primality

Posted by princeps
updated March 27th, 2012
add new comment
Graph Theory » Coloring » Vertex coloring

Coloring the Odd Distance Graph ★★★

Author(s): Rosenfeld

The Odd Distance Graph, denoted $ {\mathcal O} $, is the graph with vertex set $ {\mathbb R}^2 $ and two points adjacent if the distance between them is an odd integer.

Question   Is $ \chi({\mathcal O}) = \infty $?

Keywords: coloring; geometric graph; odd distance

Posted by mdevos
updated March 19th, 2012
8 comments
Graph Theory » Coloring » Homomorphisms

Cores of Cayley graphs ★★

Author(s): Samal

Conjecture   Let $ M $ be an abelian group. Is the core of a Cayley graph (on some power of $ M $) a Cayley graph (on some power of $ M $)?

Keywords: Cayley graph; core

Posted by Robert Samal
updated February 29th, 2012
3 comments
Topology

Graph product of multifuncoids ★★

Author(s): Porton

Conjecture   Let $ F $ is a family of multifuncoids such that each $ F_i $ is of the form $ \lambda j \in N \left( i \right) : \mathfrak{F} \left( U_j \right) $ where $ N \left( i \right) $ is an index set for every $ i $ and $ U_j $ is a set for every $ j $. Let every $ F_i = E^{\ast} f_i $ for some multifuncoid $ f_i $ of the form $ \lambda j \in N \left( i \right) : \mathfrak{P} \left( U_j \right) $ regarding the filtrator $ \left( \prod_{j \in N \left( i \right)} \mathfrak{F} \left( U_j \right) ; \prod_{j \in N \left( i \right)} \mathfrak{P} \left( U_j \right) \right) $. Let $ H $ is a graph-composition of $ F $ (regarding some partition $ G $ and external set $ Z $). Then there exist a multifuncoid $ h $ of the form $ \lambda j \in Z : \mathfrak{P} \left( U_j \right) $ such that $ H = E^{\ast} h $ regarding the filtrator $ \left( \prod_{j \in Z} \mathfrak{F} \left( U_j \right) ; \prod_{j \in Z} \mathfrak{P} \left( U_j \right) \right) $.

Keywords: graph-product; multifuncoid

Posted by porton
updated February 12th, 2012
add new comment
Topology

Atomicity of the poset of multifuncoids ★★

Author(s): Porton

Conjecture   The poset of multifuncoids of the form $ (\mathscr{P}\mho)^n $ is for every sets $ \mho $ and $ n $:
    \item atomic; \item atomistic.

See below for definition of all concepts and symbols used to in this conjecture.

Refer to this Web site for the theory which I now attempt to generalize.

Keywords: multifuncoid

Posted by porton
updated February 12th, 2012
add new comment
Topology

Atomicity of the poset of completary multifuncoids ★★

Author(s): Porton

Conjecture   The poset of completary multifuncoids of the form $ (\mathscr{P}\mho)^n $ is for every sets $ \mho $ and $ n $:
    \item atomic; \item atomistic.

See below for definition of all concepts and symbols used to in this conjecture.

Refer to this Web site for the theory which I now attempt to generalize.

Keywords: multifuncoid

Posted by porton
updated February 12th, 2012
add new comment
Graph Theory » Basic G.T. » Cycles

Cycle double cover conjecture ★★★★

Author(s): Seymour; Szekeres

Conjecture   For every graph with no bridge, there is a list of cycles so that every edge is contained in exactly two.

Keywords: cover; cycle

Posted by mdevos
updated February 7th, 2012
3 comments
Topology

Upgrading a completary multifuncoid ★★

Author(s): Porton

Let $ \mho $ be a set, $ \mathfrak{F} $ be the set of filters on $ \mho $ ordered reverse to set-theoretic inclusion, $ \mathfrak{P} $ be the set of principal filters on $ \mho $, let $ n $ be an index set. Consider the filtrator $ \left( \mathfrak{F}^n ; \mathfrak{P}^n \right) $.

Conjecture   If $ f $ is a completary multifuncoid of the form $ \mathfrak{P}^n $, then $ E^{\ast} f $ is a completary multifuncoid of the form $ \mathfrak{F}^n $.

See below for definition of all concepts and symbols used to in this conjecture.

Refer to this Web site for the theory which I now attempt to generalize.

Keywords:

Posted by porton
updated February 4th, 2012
add new comment