Recent Activity
Vertex Cover Integrality Gap ★★
Author(s): Atserias
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 .
Keywords: Discrete Geometry; Geometric Ramsey Theory
Mixing Circular Colourings ★
Keywords: discrete homotopy; graph colourings; mixing
The Borodin-Kostochka Conjecture ★★
Keywords:
Chromatic number of random lifts of complete graphs ★★
Author(s): Amit
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):
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
Keywords: choosability; circular colouring; planar graphs
A conjecture about direct product of funcoids ★★
Author(s): Porton
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
MacEachen Conjecture ★
Author(s): McEachen
Keywords: primality; prime distribution
Criterion for boundedness of power series ★
Author(s): Rüdinger
Keywords: boundedness; power series; real analysis
Length of surreal product ★
Author(s): Gonshor
It is easy to prove that
What about
?
Keywords: surreal numbers
Durer's Conjecture ★★★
Convex uniform 5-polytopes ★★
Author(s):
Keywords:
MSO alternation hierarchy over pictures ★★
Author(s): Grandjean
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 .
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.
Keywords: bounded tree width; cardinality predicates; FMT03-Bedlewo; MSO
Order-invariant queries ★★
Author(s): Segoufin
- \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
- \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):
Keywords:
Algebraic independence of pi and e ★★★
Author(s):
Keywords: algebraic independence