Recent Activity

The Borodin-Kostochka Conjecture ★★

Author(s): Borodin; Kostochka

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

Keywords:

Chromatic number of random lifts of complete graphs ★★

Author(s): Amit

\begin{question} Is the chromatic number of a random lift of $K_5$ concentrated on a single value? \end{question}

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):

\begin{conjecture} $3~$ is a \Def[primitive root]{Primitive_root_modulo_n} modulo $~p$ for all primes $~p=16\cdot q^4+1$, where $~q>3$ is prime. \end{conjecture}

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

\begin{problem} What is the best upper bound on circular choosability for planar graphs? \end{problem}

Keywords: choosability; circular colouring; planar graphs

A conjecture about direct product of funcoids ★★

Author(s): Porton

\begin{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.) \end{conjecture}

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

\begin{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}$. \end{question}

Keywords: boundedness; power series; real analysis

Length of surreal product

Author(s): Gonshor

\begin{conjecture} Every \Def{surreal number} has a unique sign expansion, i.e. function $f: o\rightarrow \{-, +\}$, where $o$ is some ordinal. This $o$ is the \emph{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) $$

? \end{conjecture}

Keywords: surreal numbers

Durer's Conjecture ★★★

Author(s): Durer; Shephard

\begin{conjecture} Every convex polytope has a non-overlapping edge unfolding. \end{conjecture}

Keywords: folding; polytope

Convex uniform 5-polytopes ★★

Author(s):

\begin{problem} Enumerate all convex uniform 5-polytopes. \end{problem}

Keywords:

MSO alternation hierarchy over pictures ★★

Author(s): Grandjean

\begin{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. \end{question}

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

\begin{question} Does the Blatter-Specker Theorem hold for ternary relations. \end{question}

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: \begin{itemize} \item $\text{``}\,\mathrm{Card}(X) = \mathrm{Card}(Y)\,\text{''}$ \item $\text{``}\,\mathrm{Card}(X) \text{ belongs to } A\,\text{''}$ \end{itemize} where $A$ is a fixed recursive set of integers.

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

\begin{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$? \end{conjecture}

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

Order-invariant queries ★★

Author(s): Segoufin

\begin{question} \begin{enumerate} \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}$? \end{enumerate} \end{question}

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

Fixed-point logic with counting ★★

Author(s): Blass

\begin{question} Can either of the following be expressed in fixed-point logic plus counting: \begin{enumerate} \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? \end{enumerate} \end{question}

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

Birch & Swinnerton-Dyer conjecture ★★★★

Author(s):

\begin{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)$. \end{conjecture}

Keywords:

Algebraic independence of pi and e ★★★

Author(s):

\begin{conjecture} $\pi$ and $e$ are \Def[algebraically independent]{Algebraic_independence} \end{conjecture}

Keywords: algebraic independence

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

Author(s):

\begin{conjecture} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. Skewes' number $e^{e^{e^{79}}}$ is not an integer. \end{conjecture}

Keywords:

Minimal graphs with a prescribed number of spanning trees ★★

Author(s): Azarija; Skrekovski

\begin{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}).$ \end{conjecture}

Keywords: number of spanning trees, asymptotics

Sticky Cantor sets ★★

Author(s):

\begin{conjecture} Let $C$ be a \Def{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? \end{conjecture}

Keywords: Cantor set

Subgroup formed by elements of order dividing n ★★

Author(s): Frobenius

\begin{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$?

\end{conjecture}

Keywords: order, dividing