# Erdos, Paul

## Monochromatic reachability in edge-colored tournaments ★★★

Author(s): Erdos

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

Keywords: digraph; edge-coloring; tournament

## Covering systems with big moduli ★★

Author(s): Erdos; Selfridge

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

Keywords: covering system

## 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

## Sets with distinct subset sums ★★★

Author(s): Erdos

Say that a set has distinct subset sums if distinct subsets of have distinct sums.

Conjecture   There exists a fixed constant so that whenever has distinct subset sums.

Keywords: subset sum

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

Author(s): Erdos; Turan

Let . The representation function for is given by the rule . We call an additive basis if is never .

Conjecture   If is an additive basis, then is unbounded.

Keywords: additive basis; representation function

## Diagonal Ramsey numbers ★★★★

Author(s): Erdos

Let denote the diagonal Ramsey number.

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

Keywords: Ramsey number

## Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

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

## The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

The crossing number of is the minimum number of crossings in all drawings of in the plane.

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

Conjecture Keywords: crossing number; hypercube

## The Erdös-Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

Conjecture   For every fixed graph , there exists a constant , so that every graph without an induced subgraph isomorphic to contains either a clique or an independent set of size .

Keywords: induced subgraph 