Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
516 of 1,221 problems match
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
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 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.
Asks for which limit ordinals every graph on that many vertices has an infinite path or an independent set whose vertices have that same order type.
Asks whether a family of countably infinite sets meeting pairwise in a finite set of size other than one can always be two-colored with no set monochromatic.
Asks whether any n distinct points in the plane must contain a point from which the number of distinct distances to the others is almost n.
Estimates the least m such that n-coloring a complete graph on two to the n plus one vertices forces a monochromatic odd cycle of length at most m.
Asks whether cliques of linear size force a sublinear clique transversal and which clique size k_c(n) forces a transversal below (1 − c)n; open, with k_c(n) ≥ n^{c'/log log n} (infinitely many n) and τ ≤ n − √(kn) from 1992.
Determines the fewest edges of a graph on n vertices in which every set of k plus two vertices induces a subgraph of maximum degree at least k.
Asks for the best bound t on the covering number of an r-uniform hypergraph, r at least three, in which every subhypergraph on at most 3r - 3 vertices has covering number at most one.
Asks whether r-coloring the edges of a complete graph on r squared plus one vertices forces r plus one vertices whose induced edges miss a color.
Asks to prove that H(n) minus the base-two logarithm of n tends to infinity, where H(n) is the least size such that some map from the subsets of an n-element set X to X sends the subsets of each set that large onto X.
Asks whether the largest girth of a graph on n vertices with chromatic number k, divided by the logarithm of n, tends to a limit, for k at least four.
Asks whether the largest ratio of chromatic to clique number on n vertices, divided by n over the squared logarithm of n, tends to a limit.
Asks whether a graph of chromatic number k with no k-vertex clique has disjoint subgraphs of chromatic number at least a and at least b when a plus b is k+1.
Asks for the least number of vertices n(k) of a bipartite graph whose list chromatic number exceeds k; open, with n(2) = 6 and n(3) = 14 known.
Determines all n for which some triangle can be cut into n congruent triangles.
Asks how large a subset of the first N integers can be if no difference of at least t between two of its elements divides the larger element.
Asks whether large enough chromatic number forces an odd cycle whose vertices span a subgraph of chromatic number at least k, for k at least three.
Asks whether a graph on n vertices in which every cycle has more vertices than chords can have at most a constant times n edges.
Estimates how many edges force a t-uniform hypergraph on n vertices to have four edges with A union B equal to C union D and A, B and C, D disjoint.
Bounds the size of a set meeting all k-element sets of a family in which every r of them share a piercing pair, asking if it is a constant times k.
Asks whether some n greater than 24 has m plus the number of divisors of m at most n plus two for every m less than n.
Estimates how many distinct distances to other points some point must have, among n points in the plane with no four of them on a circle.
Asks whether n planar points forming no isosceles triangle must determine a number of distinct distances that grows faster than a constant times n.