Recent Activity

Big Line or Big Clique in Planar Point Sets ★★

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

Posted by David Wood
updated September 25th, 2012

1 comment

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

Graph Theory

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:

Posted by Andrew King
updated September 10th, 2012

add new comment

Graph Theory » Probabilistic G.T.

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

Posted by DOT
updated September 3rd, 2012

add new comment

Number Theory

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:

Posted by princeps
updated August 24th, 2012

1 comment

Graph Theory » Coloring » Homomorphisms

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

Posted by rosskang
updated August 23rd, 2012

add new comment

Topology

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

Posted by porton
updated July 26th, 2012

add new comment

Number Theory

MacEachen Conjecture ★

Author(s): McEachen

Conjecture Every odd prime number must either be adjacent to, or a prime distance away from a primorial or primorial product.

Keywords: primality; prime distribution

Posted by billymac00
updated July 7th, 2012

4 comments | 1 attachment

Analysis

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

Posted by andreasruedinger
updated June 21st, 2012

5 comments

Combinatorics

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

Posted by Lukáš Lánský
updated June 5th, 2012

2 comments

Geometry » Polytopes

Durer's Conjecture ★★★

Author(s): Durer; Shephard

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

Keywords: folding; polytope

Posted by dmoskovich
updated June 4th, 2012

add new comment

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:

$\text{``}\,\mathrm{Card}(X) = \mathrm{Card}(Y)\,\text{''}$

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

${<}\text{-invariant\:FO} = \text{FO}$

${<}\text{-invariant\:FO}$

$\text{MSO}$

${<}\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:

$M$

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