# Recent Activity

## Vertex Cover Integrality Gap ★★

Author(s): Atserias

Conjecture   For every there is such that, for every large , there are -vertex graphs and such that and .

Keywords: counting quantifiers; FMT12-LesHouches

## Big Line or Big Clique in Planar Point Sets ★★

Author(s): Kara; Por; Wood

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

Conjecture   For all integers there is an integer such that every set of at least points in the plane contains at least collinear points or pairwise visible points.

## Mixing Circular Colourings ★

Author(s): Brewster; Noel

Question   Is 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 . Does the fragment 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 has chromatic number at most .

Keywords:

## Chromatic number of random lifts of complete graphs ★★

Author(s): Amit

Question   Is the chromatic number of a random lift of 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   is a primitive root modulo for all primes , where is prime.

Keywords:

## Circular choosability of planar graphs ★

Author(s): Mohar

Let be a graph. If and are two integers, a -colouring of is a function from to such that for each edge . Given a list assignment of , i.e.~a mapping that assigns to every vertex a set of non-negative integers, an -colouring of is a mapping such that for every . A list assignment is a --list-assignment if and for each vertex . Given such a list assignment , the graph G is --colourable if there exists a --colouring , i.e. is both a -colouring and an -colouring. For any real number , the graph is --choosable if it is --colourable for every --list-assignment . Last, is circularly -choosable if it is --choosable for any , . The circular choosability (or circular list chromatic number or circular choice number) of G is

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 and are monovalued, entirely defined funcoids with . Then there exists a pointfree funcoid such that (for every filter on ) (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 so that the power series is bounded for all .

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 , where is some ordinal. This is the length of given sign expansion and also the birthday of the corresponding surreal number. Let us denote this length of as .

It is easy to prove that

?

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.

## Blatter-Specker Theorem for ternary relations ★★

Author(s): Makowsky

Let be a class of finite relational structures. We denote by the number of structures in over the labeled set . For any class definable in monadic second-order logic with unary and binary relation symbols, Specker and Blatter showed that, for every , the function is ultimately periodic modulo .

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

where is a fixed recursive set of integers.

Let us fix and a closed formula in this language.

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

## Order-invariant queries ★★

Author(s): Segoufin

Question
\item Does hold over graphs of bounded tree-width? \item Is included in over graphs? \item Does have a 0-1 law? \item Are properties of Hanf-local? \item Is there a logic (with an effective syntax) that captures ?

## 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 of edges such that every vertex is incident to exactly one edge from ? \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?

## Birch & Swinnerton-Dyer conjecture ★★★★

Author(s):

Conjecture   Let be an elliptic curve over a number field . Then the order of the zeros of its -function, , at is the Mordell-Weil rank of .

Keywords:

## Algebraic independence of pi and e ★★★

Author(s):

Conjecture   and are algebraically independent

Keywords: algebraic independence