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

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

Keywords:

Posted by eyoong
updated May 12th, 2012
add new comment
Graph Theory

Minimal graphs with a prescribed number of spanning trees ★★

Author(s): Azarija; Skrekovski

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

Keywords: number of spanning trees, asymptotics

Posted by azi
updated April 22nd, 2012
add new comment | 1 attachment