Recent Activity

Graph Theory » Algebraic G.T.

Does the chromatic symmetric function distinguish between trees? ★★

Author(s): Stanley

Problem Do there exist non-isomorphic trees which have the same chromatic symmetric function?

Keywords: chromatic polynomial; symmetric function; tree

Posted by mdevos
updated February 25th, 2009

add new comment

Graph Theory

Shannon capacity of the seven-cycle ★★★

Author(s):

Problem What is the Shannon capacity of $C_7$ ?

Keywords:

Posted by tchow
updated February 19th, 2009

add new comment

Number Theory » Combinatorial N.T.

Frobenius number of four or more integers ★★

Author(s):

Problem Find an explicit formula for Frobenius number $g(a_1, a_2, \dots, a_n)$ of co-prime positive integers $a_1, a_2, \dots, a_n$ for $n\geq 4$ .

Keywords:

Posted by maxal
updated November 26th, 2008

add new comment

Number Theory » Computational N.T.

Magic square of squares ★★

Author(s): LaBar

Question Does there exist a $3\times 3$ magic square composed of distinct perfect squares?

Keywords:

Posted by maxal
updated November 23rd, 2008

add new comment

Group Theory

Inverse Galois Problem ★★★★

Author(s): Hilbert

Conjecture Every finite group is the Galois group of some finite algebraic extension of $\mathbb Q$ .

Keywords:

Posted by tchow
updated October 13th, 2008

add new comment

Graph Theory » Coloring » Edge coloring

Seymour's r-graph conjecture ★★★

Author(s): Seymour

An $r$ -graph is an $r$ -regular graph $G$ with the property that $|\delta(X)| \ge r$ for every $X \subseteq V(G)$ with odd size.

Conjecture $\chi'(G) \le r+1$ for every $r$ -graph $G$ .

Keywords: edge-coloring; r-graph

Posted by mdevos
updated October 3rd, 2008

add new comment

Graph Theory » Coloring » Edge coloring

Edge list coloring conjecture ★★★

Author(s):

Conjecture Let $G$ be a loopless multigraph. Then the edge chromatic number of $G$ equals the list edge chromatic number of $G$ .

Keywords:

Posted by tchow
updated September 25th, 2008

add new comment

Geometry

Conjecture If a finite set of unit balls in $\mathbb{R}^n$ is rearranged so that the distance between each pair of centers does not decrease, then the volume of the union of the balls does not decrease.

Keywords: pushing disks

Posted by tchow
updated September 25th, 2008

add new comment

Combinatorics

Wide partition conjecture ★★

Author(s): Chow; Taylor

Conjecture An integer partition is wide if and only if it is Latin.

Keywords:

Posted by tchow
updated September 24th, 2008

add new comment

Combinatorics

3-accessibility of Fibonacci numbers ★★

Author(s): Landman; Robertson

Question Is the set of Fibonacci numbers 3-accessible?

Keywords: Fibonacci numbers; monochromatic diffsequences

Posted by vjungic
updated August 24th, 2008

add new comment

Geometry

Simplexity of the n-cube ★★★

Author(s):

Question What is the minimum cardinality of a decomposition of the $n$ -cube into $n$ -simplices?

Keywords: cube; decomposition; simplex

Posted by mdevos
updated August 6th, 2008

add new comment | 1 attachment

Graph Theory » Topological G.T. » Crossing numbers

Crossing sequences ★★

Author(s): Archdeacon; Bonnington; Siran

Conjecture Let $(a_0,a_1,a_2,\ldots,0)$ be a sequence of nonnegative integers which strictly decreases until $0$ .

Then there exists a graph that be drawn on a surface with orientable (nonorientable, resp.) genus $i$ with $a_i$ crossings, but not with less crossings.

Keywords: crossing number; crossing sequence

Posted by Robert Samal
updated July 30th, 2008

add new comment

Graph Theory » Topological G.T. » Crossing numbers

The Crossing Number of the Complete Graph ★★★

Author(s):

The crossing number $cr(G)$ of $G$ is the minimum number of crossings in all drawings of $G$ in the plane.

Conjecture $\displaystyle cr(K_n) = \frac 14 \floor{\frac n2} \floor{\frac{n-1}2} \floor{\frac{n-2}2} \floor{\frac{n-3}2}$

Keywords: complete graph; crossing number

Posted by Robert Samal
updated July 28th, 2008

3 comments

Graph Theory » Topological G.T. » Crossing numbers

The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

The crossing number $cr(G)$ of $G$ is the minimum number of crossings in all drawings of $G$ in the plane.

The $d$ -dimensional (hyper)cube $Q_d$ is the graph whose vertices are all binary sequences of length $d$ , and two of the sequences are adjacent in $Q_d$ if they differ in precisely one coordinate.

Conjecture $\displaystyle \lim \frac{cr(Q_d)}{4^d} = \frac{5}{32}$

Keywords: crossing number; hypercube

Posted by Robert Samal
updated July 18th, 2008

1 comment

Graph Theory » Directed Graphs » Tournaments

Monochromatic reachability or rainbow triangles ★★★

Author(s): Sands; Sauer; Woodrow

In an edge-colored digraph, we say that a subgraph is rainbow if all its edges have distinct colors, and monochromatic if all its edges have the same color.

Problem Let $G$ be a tournament with edges colored from a set of three colors. Is it true that $G$ must have either a rainbow directed cycle of length three or a vertex $v$ so that every other vertex can be reached from $v$ by a monochromatic (directed) path?

Keywords: digraph; edge-coloring; tournament

Posted by mdevos
updated July 15th, 2008

add new comment

Topology

Rank vs. Genus ★★★

Author(s): Johnson

Question Is there a hyperbolic 3-manifold whose fundamental group rank is strictly less than its Heegaard genus? How much can the two differ by?

Keywords:

Posted by Jesse Johnson
updated July 13th, 2008

1 comment

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.