Problems
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Loading problems…
0552
Problem 552
OpenDetermines the Ramsey number of a four-cycle against the star with n edges.
- Graph theory
- Ramsey theory
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.
Determines the Ramsey number of a four-cycle against the star with n edges.
Asks for a proof that the k-color Ramsey number of an odd cycle on two n plus one vertices is negligible against that of the triangle, for n at least two.
Determines the k-color Ramsey number of the even cycle on two n vertices.
Asks whether every 3-coloring of the edges of the complete graph on 4n - 3 vertices has a monochromatic cycle of length n, for every n > 3; the site's wording also includes the triangle, where it fails, and the bound is known for all large n.
Determines the k-color Ramsey number of the complete bipartite graph with s vertices in one class and t in the other.
Asks for the size Ramsey number of the balanced complete bipartite graph with n vertices on each side; known between orders n squared times two to the n and n cubed times two to the n.
Asks to prove the 1978 formula for the size Ramsey number of two star forests as a sum over diagonals of the largest star-size sums minus one; proved in special cases only.
Estimates the Ramsey number for r-uniform hypergraphs, the fewest vertices forcing a monochromatic complete r-uniform subhypergraph on n vertices.
Determines the least size m such that some two-coloring of the complete graph on n vertices leaves every vertex set of size at least m rich in both colors.
Estimates the Ramsey number for three-uniform hypergraphs, the fewest vertices forcing a monochromatic complete three-uniform subhypergraph on n vertices.
Asks whether a graph whose subgraphs on k at least 2 vertices have at most 2k-3 edges is Ramsey size linear; corrected from the site's wording, which no graph meets since one vertex exceeds the bound; open.
Asks whether the three-cube, the complete bipartite graph with three vertices per side, or the complete graph on four vertices with one edge subdivided is Ramsey size linear; open, with partial results.
Asks whether a graph with linear Ramsey numbers against trees and quadratic against complete graphs has Ramsey number linear in the edge count of every graph without isolated vertices.
Asks whether, for every k at least three, some graph on n vertices with no cycle of length two k has at least a constant times n to the power one plus one over k edges; known for k equal to 3 and 5, open for every other k.
Asks whether the most edges a graph on n vertices can have with no triangle and no four-cycle is asymptotic to n over two to the power three halves; the ratio is known only to lie between one and the square root of two.
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 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.
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, 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.
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.
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.