# Recent Activity

## Graham's conjecture on tree reconstruction ★★

Author(s): Graham

**Problem**for every graph , we let denote the line graph of . Given that is a tree, can we determine it from the integer sequence ?

Keywords: reconstruction; tree

## 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 ★★

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.

Keywords: Discrete Geometry; Geometric Ramsey Theory

## Mixing Circular Colourings ★

**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 ★★

**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

What about

?

Keywords: surreal numbers

## Durer's Conjecture ★★★

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

## 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 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 ?

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

## 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 ?

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 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?

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

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