Erdos, Paul

Graph Theory » Coloring » Vertex coloring

Double-critical graph conjecture ★★

A simple graph $G$ is called double-critical, if removing any pair of adjacent vertexes lowers the chromatic number by two.

Conjecture $K_n$ is the only $n$ -chromatic double-critical graph

Keywords: coloring; complete graph

Posted by DFR
updated November 30th, 2009

1 comment

Geometry

Erdos-Szekeres conjecture ★★★

Author(s): Erdos; Szekeres

Conjecture Every set of $2^{n-2} + 1$ points in the plane in general position contains a subset of $n$ points which form a convex $n$ -gon.

Keywords: combinatorial geometry; Convex Polygons; ramsey theory

Posted by mdevos
updated October 7th, 2008

add new comment

Graph Theory » Basic G.T. » Cycles

Conjecture Let $G_n$ be the bipartite graph whose vertices are the $n$ -subsets and the $(n+1)$ -subsets of a $(2n+1)$ -element set, and with inclusion as the adjacency relationship. Then $G_n$ is Hamiltonian.

Keywords:

Posted by tchow
updated September 24th, 2008

add new comment

Number Theory

Sum-product problem ★★★

Author(s): Erdos; Szemeredi

For every $A \subseteq {\mathbb R}$ we let $A + A = \{ a+b : a,b \in A\}$ and $A \cdot A = \{ ab : a,b \in A \}$ .

Conjecture For every $\epsilon > 0$ , every sufficiently large finite set $A \subseteq {\mathbb R}$ satisfies

$\max \{ |A \cdot A|, |A + A| \} \ge |A|^{2 - \epsilon}$

Keywords: product set; sumset

Posted by mdevos
updated August 7th, 2008

add new comment

Graph Theory » Directed Graphs

Monochromatic reachability in edge-colored tournaments ★★★

Author(s): Erdos

Problem For every $n$ , is there a (least) positive integer $f(n)$ so that whenever a tournament has its edges colored with $n$ colors, there exists a set $S$ of at most $f(n)$ vertices so that every vertex has a monochromatic path to some point in $S$ ?

Keywords: digraph; edge-coloring; tournament

Posted by mdevos
updated July 9th, 2008

add new comment

Number Theory » Combinatorial N.T.

Covering systems with big moduli ★★

Author(s): Erdos; Selfridge

Problem Does for every integer $N$ exist a covering system with all moduli distinct and at least equal to $N$ ?

Keywords: covering system

Posted by Robert Samal
updated August 4th, 2007

add new comment

Number Theory » Combinatorial N.T.

Odd incongruent covering systems ★★★

Author(s): Erdos; Selfridge

Conjecture There is no covering system whose moduli are odd, distinct, and greater than 1.

Keywords: covering system

Posted by Robert Samal
updated August 4th, 2007

add new comment

Number Theory » Combinatorial N.T.

Sets with distinct subset sums ★★★

Author(s): Erdos

Say that a set $S \subseteq {\mathbb Z}$ has distinct subset sums if distinct subsets of $S$ have distinct sums.

Conjecture There exists a fixed constant $c$ so that $|S| \le \log_2(n) + c$ whenever $S \subseteq \{1,2,\ldots,n\}$ has distinct subset sums.

Keywords: subset sum

Posted by mdevos
updated June 23rd, 2007

add new comment

Number Theory » Additive N.T.

The Erdos-Turan conjecture on additive bases ★★★★

Author(s): Erdos; Turan

Let $B \subseteq {\mathbb N}$ . The representation function $r_B : {\mathbb N} \rightarrow {\mathbb N}$ for $B$ is given by the rule $r_B(k) = \#\{ (i,j) \in B \times B : i + j = k \}$ . We call $B$ an additive basis if $r_B$ is never $0$ .