Open Problem Garden

sequence

A conjecture on iterated circumcentres ★★

Author(s): Goddyn

Conjecture Let $p_1,p_2,p_3,\ldots$ be a sequence of points in ${\mathbb R}^d$ with the property that for every $i \ge d+2$ , the points $p_{i-1}, p_{i-2}, \ldots p_{i-d-1}$ are distinct, lie on a unique sphere, and further, $p_i$ is the center of this sphere. If this sequence is periodic, must its period be $2d+4$ ?

Keywords: periodic; plane geometry; sequence

Posted by mdevos
updated June 8th, 2007

add new comment

Graph Theory » Algebraic G.T.

The sum of the two largest eigenvalues ★★

Author(s): Gernert

Problem Let $G$ be a graph on $n$ vertices and let $\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_n$ be the eigenvalues of $G$ . Is $\lambda_1 + \lambda_2 \le n$ ?

Keywords: eigenvalues; spectrum

Posted by mdevos
updated January 13th, 2009

4 comments

Gernert, Dieter

spectrum

Combinatorics » Ramsey Theory

Diagonal Ramsey numbers ★★★★

Author(s): Erdos

Let $R(k,k)$ denote the $k^{th}$ diagonal Ramsey number.

Conjecture $\lim_{k \rightarrow \infty} R(k,k) ^{\frac{1}{k}}$ exists.

Problem Determine the limit in the above conjecture (assuming it exists).

Keywords: Ramsey number

Posted by mdevos
updated September 13th, 2010

2 comments

Ramsey number

Graph Theory » Infinite Graphs

Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

Problem Does there exist a graph with no subgraph isomorphic to $K_4$ which cannot be expressed as a union of $\aleph_0$ triangle free graphs?

Keywords: forbidden subgraph; infinite graph; triangle free

Posted by mdevos
updated June 4th, 2007

add new comment

forbidden subgraph

Graph Theory » Algebraic G.T.

Half-integral flow polynomial values ★★

Author(s): Mohar

Let $\Phi(G,x)$ be the flow polynomial of a graph $G$ . So for every positive integer $k$ , the value $\Phi(G,k)$ equals the number of nowhere-zero $k$ -flows in $G$ .