Recent Activity

Graham's conjecture on tree reconstruction ★★

Author(s): Graham

Problem   for every graph $ G $, we let $ L(G) $ denote the line graph of $ G $. Given that $ G $ is a tree, can we determine it from the integer sequence $ |V(G)|, |V(L(G))|, |V(L(L(G)))|, \ldots $?

Keywords: reconstruction; tree

Vertex Cover Integrality Gap ★★

Author(s): Atserias

Conjecture   For every $ \varepsilon > 0 $ there is $ \delta > 0 $ such that, for every large $ n $, there are $ n $-vertex graphs $ G $ and $ H $ such that $ G \equiv_{\delta n}^{\mathrm{C}} H $ and $ \mathrm{vc}(G) \ge (2 - \varepsilon) \cdot \mathrm{vc}(H) $.

Keywords: counting quantifiers; FMT12-LesHouches

Big Line or Big Clique in Planar Point Sets ★★

Author(s): Kara; Por; Wood

Let $ S $ be a set of points in the plane. Two points $ v $ and $ w $ in $ S $ are visible with respect to $ S $ if the line segment between $ v $ and $ w $ contains no other point in $ S $.

Conjecture   For all integers $ k,\ell\geq2 $ there is an integer $ n $ such that every set of at least $ n $ points in the plane contains at least $ \ell $ collinear points or $ k $ pairwise visible points.

Keywords: Discrete Geometry; Geometric Ramsey Theory

Mixing Circular Colourings

Author(s): Brewster; Noel

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

Keywords: discrete homotopy; graph colourings; mixing

Finite entailment of Positive Horn logic ★★

Author(s): Martin

Question   Positive Horn logic (pH) is the fragment of FO involving exactly $ \exists, \forall, \wedge, = $. Does the fragment $ pH \wedge \neg pH $ have the finite model property?

Keywords: entailment; finite satisfiability; horn logic

The Borodin-Kostochka Conjecture ★★

Author(s): Borodin; Kostochka

Conjecture   Every graph with maximum degree $ \Delta \geq 9 $ has chromatic number at most $ \max\{\Delta-1, \omega\} $.

Keywords:

Chromatic number of random lifts of complete graphs ★★

Author(s): Amit

Question   Is the chromatic number of a random lift of $ K_5 $ concentrated on a single value?

Keywords: random lifts, coloring

3 is a primitive root modulo primes of the form 16 q^4 + 1, where q>3 is prime ★★

Author(s):

Conjecture   $ 3~ $ is a primitive root modulo $ ~p $ for all primes $ ~p=16\cdot q^4+1 $, where $ ~q>3 $ is prime.

Keywords:

Circular choosability of planar graphs

Author(s): Mohar

Let $ G = (V, E) $ be a graph. If $ p $ and $ q $ are two integers, a $ (p,q) $-colouring of $ G $ is a function $ c $ from $ V $ to $ \{0,\dots,p-1\} $ such that $ q \le |c(u)-c(v)| \le p-q $ for each edge $ uv\in E $. Given a list assignment $ L $ of $ G $, i.e.~a mapping that assigns to every vertex $ v $ a set of non-negative integers, an $ L $-colouring of $ G $ is a mapping $ c : V \to N $ such that $ c(v)\in L(v) $ for every $ v\in V $. A list assignment $ L $ is a $ t $-$ (p,q) $-list-assignment if $ L(v) \subseteq \{0,\dots,p-1\} $ and $ |L(v)| \ge tq $ for each vertex $ v \in V $ . Given such a list assignment $ L $, the graph G is $ (p,q) $-$ L $-colourable if there exists a $ (p,q) $-$ L $-colouring $ c $, i.e. $ c $ is both a $ (p,q) $-colouring and an $ L $-colouring. For any real number $ t \ge 1 $, the graph $ G $ is $ t $-$ (p,q) $-choosable if it is $ (p,q) $-$ L $-colourable for every $ t $-$ (p,q) $-list-assignment $ L $. Last, $ G $ is circularly $ t $-choosable if it is $ t $-$ (p,q) $-choosable for any $ p $, $ q $. The circular choosability (or circular list chromatic number or circular choice number) of G is $$cch(G) := \inf\{t \ge 1 : G \text{ is circularly $t$-choosable}\}.$$

Problem   What is the best upper bound on circular choosability for planar graphs?

Keywords: choosability; circular colouring; planar graphs

A conjecture about direct product of funcoids ★★

Author(s): Porton

Conjecture   Let $ f_1 $ and $ f_2 $ are monovalued, entirely defined funcoids with $ \operatorname{Src}f_1=\operatorname{Src}f_2=A $. Then there exists a pointfree funcoid $ f_1 \times^{\left( D \right)} f_2 $ such that (for every filter $ x $ on $ A $) $$\left\langle f_1 \times^{\left( D \right)} f_2 \right\rangle x = \bigcup \left\{ \langle f_1\rangle X \times^{\mathsf{FCD}} \langle f_2\rangle X \hspace{1em} | \hspace{1em} X \in \mathrm{atoms}^{\mathfrak{A}} x \right\}.$$ (The join operation is taken on the lattice of filters with reversed order.)

A positive solution of this problem may open a way to prove that some funcoids-related categories are cartesian closed.

Keywords: category theory; general topology

Criterion for boundedness of power series

Author(s): Rüdinger

Question   Give a necessary and sufficient criterion for the sequence $ (a_n) $ so that the power series $ \sum_{n=0}^{\infty} a_n x^n $ is bounded for all $ x \in \mathbb{R} $.

Keywords: boundedness; power series; real analysis

Length of surreal product

Author(s): Gonshor

Conjecture   Every surreal number has a unique sign expansion, i.e. function $ f: o\rightarrow \{-, +\} $, where $ o $ is some ordinal. This $ o $ is the length of given sign expansion and also the birthday of the corresponding surreal number. Let us denote this length of $ s $ as $ \ell(s) $.

It is easy to prove that

$$ \ell(s+t) \leq \ell(s)+\ell(t) $$

What about

$$ \ell(s\times t) \leq \ell(s)\times\ell(t) $$

?

Keywords: surreal numbers

Durer's Conjecture ★★★

Author(s): Durer; Shephard

Conjecture   Every convex polytope has a non-overlapping edge unfolding.

Keywords: folding; polytope

Convex uniform 5-polytopes ★★

Author(s):

Problem   Enumerate all convex uniform 5-polytopes.

Keywords:

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

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

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

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

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

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: