The catalog

All problems

Every statement in the catalog, readable in place. Filters apply instantly; search covers names, IDs, and the LaTeX statements themselves.

Showing 47 of 280 problems in Combinatorics

NT-ADD-005

Strong Goldbach Conjecture

IconicConjecture1742

For every even integer

N \geq 4

, there exist prime numbers

p, q

(not necessarily distinct) such that

N = p + q

ALG-ARR-020

Terao’s Freeness Conjecture

MajorConjecture1983

Let

A

be a finite central hyperplane arrangement in a finite-dimensional complex vector space

V

. For each

H \in A

, choose

α_{H} \in V^{*}

with

H = ker α_{H}

, and define the module of logarithmic derivations

D (A) = {θ \in Der_{C} C [V] : θ (α_{H}) \in α_{H} C [V] for every H \in A} .

Call

A

free when

D (A)

is a free

C [V]

-module, and let

L (A) = {H \in S ⋂ H : S \subseteq A}

be its intersection lattice, ordered by reverse inclusion. If two such arrangements

A

and

A^{'}

have isomorphic intersection lattices, then

A

is free if and only if

A^{'}

is free.

AG-CY-016

Clemens Conjecture

MajorConjecture1986

Let

X \subset P_{C}^{4}

be a very general smooth quintic hypersurface, meaning one outside a countable union of proper Zariski-closed subsets of the parameter space. For every

d \geq 1

X

contains only finitely many irreducible rational curves of degree

d

; every such curve is a smooth embedded

P^{1}

with normal bundle

O_{P^{1}} (- 1) \oplus O_{P^{1}} (- 1)

COMB-001

Hadamard Matrix Conjecture

LandmarkConjecture1893

For every integer

m \geq 1

, there is a matrix

H \in {- 1, 1}^{4 m \times 4 m}

such that

H H^{T} = 4 m I_{4 m} .

Here

I_{4 m}

is the

4 m \times 4 m

identity matrix.

COMB-002

Union-Closed Sets Conjecture (Frankl's Conjecture)

LandmarkConjecture1979

Let

F

be a finite, nonempty family of finite sets such that

A \cup B \in F

for all

A, B \in F

, and assume

⋃ F \neq = \emptyset

. Then some element

x \in ⋃ F

belongs to at least

∣ F ∣ /2

members of

F

COMB-003

Erdős–Rado Sunflower Conjecture

LandmarkConjecture1960

For every integer

r \geq 3

there is a constant

C_{r} > 0

such that, for every

k \geq 1

, every family of more than

C_{r}^{k}

distinct

k

-element sets contains distinct

A_{1}, \dots, A_{r}

satisfying

A_{i} \cap A_{j} = A_{i^{'}} \cap A_{j^{'}} for all i \neq = j, i^{'} \neq = j^{'} .

(Such a family is an

r

-sunflower.)

COMB-009

Erdős–Szekeres Convex Polygon Conjecture

LandmarkConjecture1935

For

k \geq 3

, let

f (k)

be the least integer

N

such that every

N

-point set in the plane with no three collinear contains

k

points that are the vertices of their convex hull. Then

f (k) = 2^{k - 2} + 1.

COMB-014

Brown–Erdős–Sós Conjecture

LandmarkConjecture1973

For every integer

k \geq 3

and every real

δ > 0

, there is an integer

n_{0} = n_{0} (k, δ)

such that every

3

-uniform hypergraph

H = (V, E)

with

∣ V ∣ = n \geq n_{0}

and

∣ E ∣ \geq δ n^{2}

has distinct edges

e_{1}, \dots, e_{k}

satisfying

e_{1} \cup \dots \cup e_{k} \leq k + 3.

Here

3

-uniform means that every edge has exactly three vertices.

COMB-004

Lonely Runner Conjecture

MajorConjecture1967

For every integer

n \geq 2

and every set of distinct positive integers

v_{1}, \dots, v_{n - 1}

, there exists

t \in R

such that

∥ t v_{i} ∥_{R / Z} \geq \frac{1}{n} (1 \leq i \leq n - 1),

where

∥ x ∥_{R / Z} = min_{z \in Z} ∣ x - z ∣

COMB-006

Ryser–Brualdi–Stein Latin Transversal Conjecture

MajorConjecture1967–1975

Let

L

be a Latin square of order

n

, meaning an

n \times n

array on

n

symbols in which every symbol occurs once in every row and every column. A partial transversal is a set of cells using no row, column, or symbol twice. Then:

every L has a partial transversal of size n - 1,

and, if

n

is odd, every

L

has a transversal of size

n

COMB-007

Rota's Basis Conjecture

MajorConjecturec. 1989

Let

V

be an

n

-dimensional vector space over a field, and let

B_{1}, \dots, B_{n}

n

(not necessarily distinct) bases of

V

. It is possible to order each

B_{i} = (b_{i 1}, \dots, b_{in})

so that

{b_{1 j}, \dots, b_{nj}}

is a basis of

V

for every

j \in {1, \dots, n}

COMB-008

Turán's Tetrahedron Conjecture

MajorConjecture1941

Let

K_{4}^{(3)}

be the

3

-uniform hypergraph consisting of all four triples on a four-element vertex set, and let

ex (n, K_{4}^{(3)})

be the largest number of edges in an

n

-vertex

K_{4}^{(3)}

-free

3

-uniform hypergraph. Then

n \to \infty lim \frac{ex ( n , K _{4}^{(3)} )}{( 3 n )} = \frac{5}{9} .

COMB-010

Ryser's Conjecture for $r$ -Partite Hypergraphs

MajorConjecturec. 1971

H

is an

r

-uniform

r

-partite hypergraph (its vertices split into

r

classes and every edge contains exactly one vertex from each class), let

ν (H)

be the largest size of a family of pairwise disjoint edges and let

τ (H)

be the smallest size of a vertex set meeting every edge. Then

τ (H) \leq (r - 1) ν (H) .

COMB-011

Alon–Tarsi Latin Square Conjecture

MajorConjecture1990

Let

n

be even. Regard every row and every column of a Latin square

L

of order

n

as a permutation of its symbol set, and define

sgn (L) = i = 1 \prod n sgn (row_{i}) j = 1 \prod n sgn (column_{j}) .

The number of Latin squares of order

n

with sign

+ 1

is different from the number with sign

- 1

COMB-012

Existence of a Finite Projective Plane of Order $12$

MajorCanonical finite caseUnknown

Do there exist sets

P

(points) and

L

(lines), each of size

1 2^{2} + 12 + 1 = 157

, and an incidence relation

I \subseteq P \times L

, such that every line is incident with exactly

13

points, every point is incident with exactly

13

lines, every two distinct points lie on exactly one common line, and every two distinct lines meet in exactly one point?

COMB-013

1/3–2/3 Conjecture for Posets

MajorConjecture1968

Let

P = (X, \leq_{P})

be a finite poset that is not a chain, and let

L (P)

be its set of linear extensions. For incomparable

x, y \in X

, put

p_{P} (x, y) = \frac{∣{ L \in L ( P ) : x < _{L} y }∣}{∣ L ( P )∣} .

Then some incomparable pair

x, y

satisfies

\frac{1}{3} \leq p_{P} (x, y) \leq \frac{2}{3} .

GRAPH-001

Hadwiger's Conjecture

LandmarkConjecture1943

Let

χ (G)

be the chromatic number of a finite simple graph

G

, and let

K_{q}

denote the complete graph on

q

vertices. Then

G

contains

K_{χ (G)}

as a minor; equivalently,

V (G)

has

χ (G)

pairwise-disjoint nonempty connected branch sets with at least one edge between every two branch sets.

GRAPH-003

Tutte's $5$ -Flow Conjecture

LandmarkConjecture1954

Every finite bridgeless loopless multigraph

G

admits an orientation of its edges and a function

φ : E (G) \to {1, 2, 3, 4}

such that, for every vertex

v

e \in δ^{+} (v) \sum φ (e) \equiv e \in δ^{-} (v) \sum φ (e) (mod 5) .

Here

δ^{+} (v)

and

δ^{-} (v)

are respectively the sets of edges directed out of and into

v

GRAPH-009

Caccetta–Häggkvist Conjecture

LandmarkConjecture1978

Let

D

be a finite simple loopless digraph on

n

vertices with minimum outdegree at least

r \geq 1

. Then

D

contains a directed cycle of length at most

⌈ \frac{n}{r} ⌉ .

GRAPH-010

Sidorenko's Conjecture

LandmarkConjecture1986–1991

For every finite bipartite graph

H

and every symmetric measurable

W : [0, 1]^{2} \to [0, 1]

t (H, W) := \int_{[0, 1]^{V (H)}} uv \in E (H) \prod W (x_{u}, x_{v}) v \in V (H) \prod d x_{v} \geq (\int_{[0, 1]^{2}} W (x, y) d x d y)^{∣ E (H) ∣} .

GRAPH-011

Erdős–Hajnal Conjecture

LandmarkConjecture1977–1989

For every finite graph

H

, there exists

ε (H) > 0

such that every

n

-vertex simple graph

G

with no induced subgraph isomorphic to

H

has either a clique or an independent set of size at least

n^{ε (H)}

GRAPH-025

Gyárfás–Sumner Conjecture

LandmarkConjecture1975–1981

For every finite tree

T

and integer

t \geq 2

, there is an integer

c = c (T, t)

such that every finite simple graph

G

with chromatic number

χ (G) > c

and no clique on

t

vertices contains an induced subgraph isomorphic to

T

. Here

χ (G)

is the least number of colors in a proper vertex coloring, and an induced copy uses exactly the edges of

G

between its chosen vertices.

GRAPH-026

Lovász Hamiltonian-Path Conjecture

LandmarkConjecture1969

Every finite connected vertex-transitive graph has a Hamiltonian path. A graph is vertex-transitive if, for every two vertices

u, v

, it has an automorphism sending

u

v

; a Hamiltonian path visits every vertex exactly once.

GRAPH-027

Multicolor Triangle Ramsey Growth

LandmarkOpen problemc. 1970

Let

R_{k} (3)

be the least

N

such that every coloring of the edges of

K_{N}

with

k

colors contains a monochromatic triangle. Determine its exponential order, in particular whether

R_{k} (3) = k^{Θ (k)} (k \to \infty) .

GRAPH-005

Barnette's Conjecture

MajorConjecture1969

Every finite simple, cubic, bipartite, planar,

3

-vertex-connected graph has a Hamiltonian cycle.

GRAPH-006

Total Coloring Conjecture

MajorConjecture1964–1965

A total coloring of a finite simple graph

G

assigns colors to

V (G) \cup E (G)

so that adjacent vertices, adjacent edges, and every incident vertex--edge pair receive different colors. If

χ^{''} (G)

is the least number of colors in such a coloring, then

χ^{''} (G) \leq Δ (G) + 2.

Here

Δ (G)

is the maximum vertex degree of

G

GRAPH-007

List Edge-Coloring Conjecture

MajorConjecturec. 1975

For every finite loopless multigraph

G

χ_{ℓ}^{'} (G) = χ^{'} (G),

where

χ^{'} (G)

is its edge-chromatic number and

χ_{ℓ}^{'} (G)

is the least

k

such that, whenever every edge

e

is assigned a list

L (e)

of at least

k

colors, a proper edge coloring

c (e) \in L (e)

exists.

GRAPH-008

Graceful Tree Conjecture

MajorConjecture1963–1967

Every tree

T

with

m

edges admits a bijection

ℓ : V (T) \to {0, 1, \dots, m}

such that

{∣ ℓ (u) - ℓ (v) ∣ : uv \in E (T)} = {1, 2, \dots, m} .

GRAPH-015

Erdős–Gyárfás Power-of-Two Cycle Conjecture

MajorConjecture1995

Every finite simple graph of minimum degree at least

3

contains a cycle whose length is a power of

2

GRAPH-016

Tuza's Triangle Packing–Covering Conjecture

MajorConjecture1981

For a finite simple graph

G

, let

ν_{3} (G)

be the maximum number of pairwise edge-disjoint triangles and let

τ_{3} (G)

be the minimum number of edges meeting every triangle. Then

τ_{3} (G) \leq 2 ν_{3} (G) .

GRAPH-017

Reed's $\Delta$ – $\omega$ Chromatic Conjecture

MajorConjecture1998

Every finite simple graph

G

satisfies

χ (G) \leq ⌈ \frac{Δ ( G ) + 1 + ω ( G )}{2} ⌉,

where

Δ (G)

is the maximum degree and

ω (G)

the clique number.

GRAPH-018

Linear Arboricity Conjecture

MajorConjecture1980–1981

Let

la (G)

be the least number of linear forests (forests whose components are paths, including isolated edges) whose edge sets partition

E (G)

. Every finite simple graph

G

with maximum degree

Δ (G)

satisfies

la (G) \leq ⌈ \frac{Δ ( G ) + 1}{2} ⌉ .

GRAPH-019

Exact Ramsey Number $R(5,5)$

MajorExact constant problemUnknown

Determine the least integer

N = R (5, 5)

such that every red--blue coloring of the edges of

K_{N}

contains a monochromatic

K_{5}

GRAPH-020

Seymour's Second Neighborhood Conjecture

MajorConjecturec. 1990

Let

D

be a finite oriented graph (no loops and no pair of oppositely directed edges). For

v \in V (D)

, let

N^{+} (v)

be its out-neighborhood and let

N^{++} (v)

be the set of vertices whose directed distance from

v

is exactly

2

. Then some vertex

v

satisfies

∣ N^{++} (v) ∣ \geq ∣ N^{+} (v) ∣.

GRAPH-022

Chvátal's Toughness Conjecture

MajorConjecture1973

There exists a real constant

t_{0} > 0

such that every finite simple

t_{0}

-tough graph on at least three vertices is Hamiltonian. Here

G

t

-tough if, for every vertex set

S

with

c (G - S) > 1

∣ S ∣ \geq t c (G - S),

where

G - S

is the graph obtained by deleting

S

and

c (\cdot)

denotes the number of connected components.

GRAPH-023

Erdős–Faber–Lovász Conjecture

MajorConjecture1972

Let

H

be a finite linear hypergraph on

n

vertices, meaning that any two distinct hyperedges meet in at most one vertex. Its hyperedges can be colored with at most

n

colors so that intersecting hyperedges receive different colors.

GRAPH-024

Perfect One-Factorization Conjecture

MajorConjecture1964

For every integer

n \geq 2

, the edge set of the complete graph

K_{2 n}

can be partitioned into perfect matchings

M_{1}, \dots, M_{2 n - 1}

such that

M_{i} \cup M_{j}

is a Hamiltonian cycle whenever

i \neq = j

. A perfect matching is a set of pairwise disjoint edges meeting every vertex exactly once, and a Hamiltonian cycle is a cycle containing every vertex.

GRAPH-028

Erd\u0151s–Simonovits Compactness Conjecture

MajorConjecture1982

For every finite nonempty family

F

of graphs, each containing a cycle, there are

F \in F

and

C > 0

such that

ex (n, F) \leq C ex (n, F)

for all sufficiently large

n

, where

ex (n, F)

is the largest number of edges in an

n

-vertex graph containing no member of

F

GRAPH-029

Erd\u0151s Degeneracy Conjecture for Extremal Numbers

MajorConjecture1967

For every integer

r \geq 2

and every fixed bipartite

r

-degenerate graph

H

ex (n, H) = O_{H} (n^{2 - 1/ r}) .

A graph is

r

-degenerate if every nonempty subgraph has a vertex of degree at most

r

GRAPH-030

Zarankiewicz Problem for $K_{4,4}$

MajorOpen problem1951

Determine the asymptotic order of

ex (n, K_{4, 4}),

the largest number of edges in an

n

-vertex graph containing no copy of the complete bipartite graph

K_{4, 4}

DG-002

Erdős Distinct-Distances Conjecture

LandmarkConjecture1946

Let

g (n) = P \subset R^{2} ∣ P ∣ = n min {∥ x - y ∥_{2} : x, y \in P, x \neq = y} .

There is an absolute constant

c > 0

such that, for all

n \geq 2

g (n) \geq c \frac{n}{lo g n} .

DG-009

Danzer's Problem

LandmarkOpen problemc. 1965

Does there exist a locally finite set

S \subset R^{2}

and a constant

C > 0

such that every convex set of area

1

meets

S

, while

∣ S \cap [- R, R]^{2} ∣ \leq C R^{2} for every R \geq 1 ?

DG-003

Exact Growth of the Planar Unit-Distance Function

MajorOpen problem1946

For

n \geq 2

, set

u (n) = P \subset R^{2} ∣ P ∣ = n max {{x, y} \subset P : ∥ x - y ∥_{2} = 1}

and

α_{U} = n \to \infty lim sup \frac{lo g u ( n )}{lo g n} .

Determine the exact value of

α_{U}

(and, more finely, the asymptotic order of

u (n)

PROB-001

Two-dimensional self-avoiding-walk critical exponents

LandmarkConjecture1972–1982

For

n \geq 0

, let

S_{n} = {ω = (ω_{0}, \dots, ω_{n}) \in (Z^{2})^{n + 1} : ω_{0} = 0, ∥ ω_{j + 1} - ω_{j} ∥_{1} = 1 (0 \leq j < n), ω_{i} \neq = ω_{j} (0 \leq i < j \leq n)}

and put

c_{n} = ∣ S_{n} ∣

. Let

μ = lim_{n \to \infty} c_{n}^{1/ n}

, whose existence is known, and let

P_{n}

and

E_{n}

denote the uniform probability law on

S_{n}

and expectation with respect to that law. There exist constants

A, D \in (0, \infty)

such that, as

n \to \infty

c_{n} \sim A μ^{n} n^{11/32} and E_{n} [∥ ω_{n} ∥_{2}^{2}] \sim D n^{3/2} .

Thus the counting and metric critical exponents are respectively

γ = 43/32

and

ν = 3/4

TCS-016

Aanderaa–Karp–Rosenberg Evasiveness Conjecture

MajorConjecturec. 1973

Fix

n

, and let

P

be a nontrivial property of simple labeled

n

-vertex graphs that is invariant under vertex permutations and monotone under adding edges, where nontrivial means that

P

is neither empty nor the set of all such graphs. Every deterministic algorithm that decides whether an unknown graph has

P

by adaptively querying edge presence has worst-case query complexity

(2 n) .

INFO-004

Main Conjecture for MDS Codes

LandmarkConjecture1955

Let

q

be a prime power and

2 \leq k \leq q - 1

. If

C \subseteq F_{q}^{n}

is a

k

-dimensional linear code whose minimum Hamming distance is

n - k + 1

, then

n \leq q + 1,

except that, when

q

is even and

k \in {3, q - 1}

, the asserted bound is

n \leq q + 2

. The Hamming distance between two words is the number of coordinates in which they differ; a code meeting the general bound

n - k + 1

is called maximum-distance separable (MDS).

INFO-003

Binary asymptotic rate–distance improvement problem

MajorOpen problem1952–1957

For

0 < δ < 1/2

, let

A_{2} (n, d)

be the largest cardinality of a set

C \subseteq {0, 1}^{n}

whose distinct words have Hamming distance at least

d

, and define

R_{2} (δ) = n \to \infty lim sup \frac{1}{n} lo g_{2} A_{2} (n, ⌈ δ n ⌉) .

Decide whether there exists

δ \in (0, 1/2)

for which

R_{2} (δ) > 1 - H_{2} (δ), H_{2} (t) = - t lo g_{2} t - (1 - t) lo g_{2} (1 - t) .