Home

Recent Activity

Geometry » Algebraic Geometry

The Hodge Conjecture ★★★★

Author(s): Hodge

Conjecture   Let $ X $ be a complex projective variety. Then every Hodge class is a rational linear combination of the cohomology classes of complex subvarieties of $ X $.

Keywords: Hodge Theory; Millenium Problems

Posted by Charles
updated July 13th, 2008
add new comment
Combinatorics

2-accessibility of primes ★★

Author(s): Landman; Robertson

Question   Is the set of prime numbers 2-accessible?

Keywords: monochromatic diffsequences; primes

Posted by vjungic
updated July 9th, 2008
add new comment
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
Graph Theory » Coloring » Vertex coloring

Counting 3-colorings of the hex lattice ★★

Author(s): Thomassen

Problem   Find $ \lim_{n \rightarrow \infty} (\chi( H_n , 3)) ^{ 1 / |V(H_n)| } $.

Keywords: coloring; Lieb's Ice Constant; tiling; torus

Posted by mdevos
updated July 5th, 2008
add new comment
Geometry

Dense rational distance sets in the plane ★★★

Author(s): Ulam

Problem   Does there exist a dense set $ S \subseteq {\mathbb R}^2 $ so that all pairwise distances between points in $ S $ are rational?

Keywords: integral distance; rational distance

Posted by mdevos
updated July 4th, 2008
add new comment
Graph Theory » Probabilistic G.T.

Negative association in uniform forests ★★

Author(s): Pemantle

Conjecture   Let $ G $ be a finite graph, let $ e,f \in E(G) $, and let $ F $ be the edge set of a forest chosen uniformly at random from all forests of $ G $. Then \[ {\mathbb P}(e \in F \mid f \in F}) \le {\mathbb P}(e \in F) \]

Keywords: forest; negative association

Posted by mdevos
updated June 30th, 2008
add new comment
Number Theory » Computational N.T.

Wall-Sun-Sun primes and Fibonacci divisibility ★★

Author(s):

Conjecture   For any prime $ p $, there exists a Fibonacci number divisible by $ p $ exactly once.

Equivalently:

Conjecture   For any prime $ p>5 $, $ p^2 $ does not divide $ F_{p-\left(\frac p5\right)} $ where $ \left(\frac mn\right) $ is the Legendre symbol.

Keywords: Fibonacci; prime

Posted by adudzik
updated June 14th, 2008
add new comment
Graph Theory » Coloring

Total Colouring Conjecture ★★★

Author(s): Behzad

Conjecture   A total coloring of a graph $ G = (V,E) $ is an assignment of colors to the vertices and the edges of $ G $ such that every pair of adjacent vertices, every pair of adjacent edges and every vertex and incident edge pair, receive different colors. The total chromatic number of a graph $ G $, $ \chi''(G) $, equals the minimum number of colors needed in a total coloring of $ G $. It is an old conjecture of Behzad that for every graph $ G $, the total chromatic number equals the maximum degree of a vertex in $ G $, $ \Delta(G) $ plus one or two. In other words, \[\chi''(G)=\Delta(G)+1\ \ or \ \ \Delta(G)+2.\]

Keywords: Total coloring

Posted by Iradmusa
updated June 4th, 2008
add new comment
Graph Theory

Edge Reconstruction Conjecture ★★★

Author(s): Harary

Conjecture  

Every simple graph with at least 4 edges is reconstructible from it's edge deleted subgraphs

Keywords: reconstruction

Posted by melch
updated May 23rd, 2008
add new comment
Graph Theory » Basic G.T.

Nearly spanning regular subgraphs ★★★

Author(s): Alon; Mubayi

Conjecture   For every $ \epsilon > 0 $ and every positive integer $ k $, there exists $ r_0 = r_0(\epsilon,k) $ so that every simple $ r $-regular graph $ G $ with $ r \ge r_0 $ has a $ k $-regular subgraph $ H $ with $ |V(H)| \ge (1- \epsilon) |V(G)| $.

Keywords: regular; subgraph

Posted by mdevos
updated May 22nd, 2008
add new comment
Graph Theory » Topological G.T. » Coloring

Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph $ G $ is $ k $-degenerate if every subgraph of $ G $ has a vertex of degree $ \le k $.

Conjecture   Every simple planar graph has a 5-coloring so that for $ 1 \le k \le 4 $, the union of any $ k $ color classes induces a $ (k-1) $-degenerate graph.

Keywords: coloring; degenerate; planar

Posted by mdevos
updated May 21st, 2008
add new comment
Graph Theory » Coloring » Vertex coloring

Partial List Coloring ★★★

Author(s): Iradmusa

Let $ G $ be a simple graph, and for every list assignment $ \mathcal{L} $ let $ \lambda_{\mathcal{L}} $ be the maximum number of vertices of $ G $ which are colorable with respect to $ \mathcal{L} $. Define $ \lambda_t = \min{ \lambda_{\mathcal{L}} } $, where the minimum is taken over all list assignments $ \mathcal{L} $ with $ |\mathcal{L}| = t $ for all $ v \in V(G) $.

Conjecture   [2] Let $ G $ be a graph with list chromatic number $ \chi_\ell $ and $ 1\leq r\leq s\leq \chi_\ell $. Then \[\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.\]

Keywords: list assignment; list coloring

Posted by Iradmusa
updated May 12th, 2008
add new comment
Geometry » Polytopes

Cube-Simplex conjecture ★★★

Author(s): Kalai

Conjecture   For every positive integer $ k $, there exists an integer $ d $ so that every polytope of dimension $ \ge d $ has a $ k $-dimensional face which is either a simplex or is combinatorially isomorphic to a $ k $-dimensional cube.

Keywords: cube; facet; polytope; simplex

Posted by mdevos
updated May 9th, 2008
add new comment
Topology

S(S(f)) = S(f) for reloids ★★

Author(s): Porton

Question   $ S(S(f)) = S(f) $ for every endo-reloid $ f $?

Keywords: reloid

Posted by porton
updated May 8th, 2008
1 comment
Graph Theory » Coloring » Vertex coloring

Partial List Coloring ★★★

Author(s): Albertson; Grossman; Haas

Conjecture   Let $ G $ be a simple graph with $ n $ vertices and list chromatic number $ \chi_\ell(G) $. Suppose that $ 0\leq t\leq \chi_\ell $ and each vertex of $ G $ is assigned a list of $ t $ colors. Then at least $ \frac{tn}{\chi_\ell(G)} $ vertices of $ G $ can be colored from these lists.

Keywords: list assignment; list coloring

Posted by Iradmusa
updated May 5th, 2008
add new comment
Combinatorics » Designs

Combinatorial covering designs ★

Author(s): Gordon; Mills; Rödl; Schönheim

A $ (v, k, t) $ covering design, or covering, is a family of $ k $-subsets, called blocks, chosen from a $ v $-set, such that each $ t $-subset is contained in at least one of the blocks. The number of blocks is the covering’s size, and the minimum size of such a covering is denoted by $ C(v, k, t) $.

Problem   Find a closed form, recurrence, or better bounds for $ C(v,k,t) $. Find a procedure for constructing minimal coverings.

Keywords: recreational mathematics

Posted by Pseudonym
updated April 11th, 2008
add new comment
Group Theory

Burnside problem ★★★★

Author(s): Burnside

Conjecture   If a group has $ r $ generators and exponent $ n $, is it necessarily finite?

Keywords:

Posted by dlh12
updated April 11th, 2008
add new comment
Graph Theory » Algebraic G.T.

Laplacian Degrees of a Graph ★★

Author(s): Guo

Conjecture   If $ G $ is a connected graph on $ n $ vertices, then $ c_k(G) \ge d_k(G) $ for $ k = 1, 2, \dots, n-1 $.

Keywords: degree sequence; Laplacian matrix

Posted by Robert Samal
updated February 29th, 2008
2 comments
Graph Theory » Basic G.T. » Matchings

Random stable roommates ★★

Author(s): Mertens

Conjecture   The probability that a random instance of the stable roommates problem on $ n \in 2{\mathbb N} $ people admits a solution is $ \Theta( n ^{-1/4} ) $.

Keywords: stable marriage; stable roommates

Posted by mdevos
updated February 26th, 2008
add new comment