Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
1,221 problems
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Determines how many edges a graph on n vertices can have without containing the k-dimensional hypercube graph; for the cube the order lies between n to the three halves and n to the eight fifths, refuting Erdős's first guess.
Asks whether every graph on four k vertices with minimum degree at least two k contains k vertex-disjoint four-cycles; the Erdős-Faudree conjecture, proved by Wang in 2010 as Theorem B of a refereed paper.
Asks whether a random graph on two to the d vertices with each edge included with probability one half almost surely contains a d-dimensional hypercube; proved by Riordan for every fixed edge probability above one quarter.
Asks whether a large dense graph on n vertices with no complete tripartite subgraph having two vertices per class must have a linear independent set; false at edge density 3/2048 by a Lean construction Conjectures.io certified.
Asks whether every graph on n vertices in which at least half the vertices have degree at least n over two contains every tree on at most n over two vertices; proved by Zhao for large n, with finitely many orders unchecked.
Determines the largest number of edges of a bipartite subgraph that every triangle-free graph with m edges must contain; known to the order m/2 + Theta(m^{4/5}) by Alon, the exponent sharp and the exact value open.
Asks whether there is a graph with no complete subgraph on four vertices in which every two-coloring of the edges produces a monochromatic triangle.
Asks whether every connected graph on n vertices can be split into at most n over two rounded up edge-disjoint paths; Gallai's path decomposition conjecture, proved for several classes and open in general.
Asks whether every graph on n vertices with edge density delta, allowed to shrink as a power of n, contains dense subgraphs in which any two edges lie together on a short cycle.
Asks for the most edges a graph on n vertices can have without two edge-disjoint cycles on exactly the same vertex set; known to lie between n log log n and n times a power of log n.
Asks whether there is a system of congruences covering all integers in which no modulus divides another.
Determines the largest set of integers up to N in which no non-empty subset has a square sum.
Asks whether, for k at least four, n points in the plane with no k plus one collinear have only a negligible fraction of n squared lines through k points.
Estimates the largest subset with no three points on a line that can always be found inside n points in the plane having no four points on a line.
Asks whether every red-blue coloring of the pairs from the ordinal omega to the omega yields a red complete subgraph of that order type or a blue triangle.
Asks whether every red-blue coloring of pairs from the ordinal omega to the omega squared gives a red complete subgraph of that order type or a blue triangle.
Determines which countable ordinals force every red-blue coloring of pairs from omega to that ordinal to give a red clique of that type or a blue triangle.
Characterizes the finite three-uniform hypergraphs that must appear in every three-uniform hypergraph with uncountable chromatic number.
Asks whether every graph with chromatic number at least the first uncountable cardinal contains all sufficiently large odd cycles.
Asks whether there is an infinite graph with no complete subgraph on four vertices that is not a union of countably many triangle-free graphs.
Characterizes pairs of graphs for which finite colorings of a host avoiding the first force a monochromatic second, while countably many colors do not; Erdős and Hajnal first guessed that no pair exists, which C_4 and C_6 refute.
Asks whether a partition relation holds for graphs on at most aleph_1 vertices with no K_4 and no K_{aleph_0,aleph_0}; Erdős first asked it for every K_4-free graph, which a relation of Baumgartner refutes.
Asks whether the countable subsets of an infinite cardinal can be colored with successor-of-continuum many colors so every set of that size gets all colors.
Asks whether every graph with two disjoint independent sets has a family of disjoint paths between them plus a blocking set meeting each path once.
Asks whether the least edge count forcing an edge in r triangles, when every edge lies in a triangle, has differences going to infinity and ratios going to one.