Graph Theory » Directed Graphs

Non-edges vs. feedback edge sets in digraphs ★★★

Author(s): Chudnovsky; Seymour; Sullivan

For any simple digraph $ G $, we let $ \gamma(G) $ be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and $ \beta(G) $ be the size of the smallest feedback edge set.

Conjecture  If $ G $ is a simple digraph without directed cycles of length $ \le 3 $, then $ \beta(G) \le \frac{1}{2} \gamma(G) $.

Keywords: acyclic; digraph; feedback edge set; triangle free

Posted by mdevos
updated July 8th, 2008
add new comment
Logic

Tarski's exponential function problem ★★

Author(s): Tarski

Conjecture   Is the theory of the real numbers with the exponential function decidable?

Keywords: Decidability

Posted by Charles
updated July 8th, 2008
add new comment
Number Theory » Analytic N.T.

Schanuel's Conjecture ★★★★

Author(s): Schanuel

Conjecture   Given any $ n $ complex numbers $ z_1,...,z_n $ which are linearly independent over the rational numbers $ \mathbb{Q} $, then the extension field $ \mathbb{Q}(z_1,...,z_n,\exp(z_1),...,\exp(z_n)) $ has transcendence degree of at least $ n $ over $ \mathbb{Q} $.

Keywords: algebraic independence

Posted by Charles
updated January 19th, 2010
3 comments