Recent Activity

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

Number Theory

Chowla's cosine problem ★★★

Author(s): Chowla

Problem Let $A \subseteq {\mathbb N}$ be a set of $n$ positive integers and set $m(A) = - \min_x \sum_{a \in A} \cos(ax).$ What is $m(n) = \min_A m(A)$ ?

Keywords: circle; cosine polynomial

Posted by mdevos
updated February 22nd, 2008

add new comment

Graph Theory » Infinite Graphs

End-Devouring Rays ★

Author(s): Georgakopoulos

Problem Let $G$ be a graph, $\omega$ a countable end of $G$ , and $K$ an infinite set of pairwise disjoint $\omega$ -rays in $G$ . Prove that there is a set $K'$ of pairwise disjoint $\omega$ -rays that devours $\omega$ such that the set of starting vertices of rays in $K'$ equals the set of starting vertices of rays in $K$ .

Keywords: end; ray

Posted by Agelos
updated February 3rd, 2008

add new comment

Graph Theory » Basic G.T. » Minors