Erdős Problems

1,217 source-owned questions · 604 with a formal statement · searchable by statement, number, topic and source status.

Add a contribution Collection details

Collection coverage

Source status, exact formal material, and reviewed Results are separate signals.

Open per source608
Resolved per source556
Other source status53

Exact formal statement available604 / 1,217

With Repository-reviewed evidence2 / 1,217

1,217 Problems · 2 with reviewed evidence

13/26

Number	Question	Source says	Formal	Result here
#577	No statement retained — open to read what the source holdsprovedNo formal declaration	proved	No formal statement	No Result decision
#578	No statement retained — open to read what the source holdsprovedNo formal declaration	proved	No formal statement	No Result decision
#579	Let $\delta > 0$ . If $n$ is sufficiently large and $G$ is a graph on $n$ vertices with no $K_{2,2,2}$ (the octahedron) and at least $\delta n^2$ edges, must $G$ contain an independent set of size $\gg_\delta n$ ?openFormalized	open	In Lean	No Result decision
#580	No statement retained — open to read what the source holdsdecidableNo formal declaration	decidable	No formal statement	No Result decision
#581	No statement retained — open to read what the source holdssolvedNo formal declaration	solved	No formal statement	No Result decision
#582	Does there exist a graph $G$ which contains no $K_4$ , and yet any $2$ -colouring of the edges produces a monochromatic $K_3$ ?proved (Lean)Formalized	proved (Lean)	In Lean	No Result decision
#583	No statement retained — open to read what the source holdsfalsifiableNo formal declaration	falsifiable	No formal statement	No Result decision
#584	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#585	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#586	No statement retained — open to read what the source holdsdisprovedNo formal declaration	disproved	No formal statement	No Result decision
#587	Nguyen and Vu proved that $\|A\| \ll N^{1/3} (\log N)^{O(1)}$ .solvedFormalized	solved	In Lean	No Result decision
#588	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#589	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#590	Let $α$ be the infinite ordinal $\omega^{\omega}$ . It was proved by Chang [Ch72] that any red/blue colouring of the edges of $K_α$ there is either a red $K_α$ or a blue $K_3$ .provedFormalized	proved	In Lean	No Result decision
#591	Let $α$ be the infinite ordinal $\omega^{\omega^2}$ . Is it true that any red/blue colouring of the edges of $K_α$ there is either a red $K_α$ or a blue $K_3$ ?provedFormalized	proved	In Lean	No Result decision
#592	Determine which countable ordinals $β$ have the property that, if $α = \omega^β$ , then in any red/blue colouring of the edges of $K_α$ there is either a red $K_α$ or a blue $K_3$ .openFormalized	open	In Lean	No Result decision
#593	Erdős Problem 593 (500): Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number $> \aleph_0$ .openFormalized	open	In Lean	No Result decision
#594	Erdős Problem 594 (Erdős–Hajnal [ErHa66], [Er69b]):provedFormalized	proved	In Lean	No Result decision
#595	Erdős Problem 595 (250): Is there an infinite graph G which contains no $K_4$ and is not the union of countably many triangle-free graphs?openFormalized	open	In Lean	No Result decision
#596	Erdős Problem 596 (Erdős–Hajnal, [Er87]). For which graph pairs $(G_1, G_2)$ is it true thatopenFormalized	open	In Lean	No Result decision
#597	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#598	Erdős Problem 598: Let $m$ be an infinite cardinal and $\kappa$ be the successor cardinal of $2^{\aleph_0}$ . Can one colour the countable subsets of $m$ using $\kappa$ many colours so that every $X \subseteq m$ with $\|X\| = \kappa$ contains subsets of all possible colours?openFormalized	open	In Lean	No Result decision
#599	Erdős Problem 599 (the Erdős–Menger conjecture).provedFormalized	proved	In Lean	No Result decision
#600	Let $r \geq 2$ . Is it true that $e(n,r+1) - e(n,r) \to \infty$ as $n \to \infty$ ?openFormalized	open	In Lean	No Result decision
#601	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#602	Does every almost-disjoint family of countably infinite sets whose pairwise intersections all have size ≠ 1 have Property B?openFormalized	open	In Lean	No Result decision
#603	No statement retained — open to read what the source holdssolvedNo formal declaration	solved	No formal statement	No Result decision
#604	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#605	No statement retained — open to read what the source holdsprovedNo formal declaration	proved	No formal statement	No Result decision
#606	No statement retained — open to read what the source holdssolvedNo formal declaration	solved	No formal statement	No Result decision
#607	No statement retained — open to read what the source holdsprovedNo formal declaration	proved	No formal statement	No Result decision
#608	No statement retained — open to read what the source holdsdisproved (Lean)No formal declaration	disproved (Lean)	No formal statement	No Result decision
#609	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#610	No statement retained — open to read what the source holdsproved (Lean)No formal declaration	proved (Lean)	No formal statement	No Result decision
#611	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#612	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#613	Erdős Problem 613: Let $n \geq 3$ and $G$ be a graph with $\binom{2n+1}{2} - \binom{n}{2} - 1$ edges. Must $G$ be the union of a bipartite graph and a graph with maximum degree less than $n$ ?disproved (Lean)Formalized	disproved (Lean)	In Lean	No Result decision
#614	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#615	Does there exist some constant $c > 0$ such that for all sufficiently large $n$ , if $G$ is a graph with $n$ vertices and at least $(1/8 - c)n^2$ edges then $G$ must contain either a $K_4$ or an independent set on at least $n/\log n$ vertices?disprovedFormalized	disproved	In Lean	No Result decision
#616	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#617	Let $r\geq 3$ . If the edges of $K_{r^2+1}$ are $r$ -coloured then there exist $r+1$ vertices with at least one colour missing on the edges of the induced $K_{r+1}$ .falsifiableFormalized	falsifiable	In Lean	No Result decision
#618	For a triangle-free graph $G$ let $h_2(G)$ be the smallest number of edges that need to be added to $G$ so that it has diameter $2$ and is still triangle-free. Is it true that if $G$ has maximum degree $o(n^{1/2})$ then $h(G)=o(n^2)$ ?proved (Lean)Formalized	proved (Lean)	In Lean	No Result decision
#619	Erdős Problem 619 [EGR98, Er99]: For a triangle-free graph $G$ let $h_r(G)$ be the smallest number of edges that need to be added to $G$ so that it has diameter $r$ (while preserving the property of being triangle-free). Is it true that there exists a constant $c>0$ such that if $G$ is a connected graph on $n$ vertices then $h_4(G)<(1-c)n$ ?solved (Lean)Formalized	solved (Lean)	In Lean	No Result decision
#620	No statement retained — open to read what the source holdsopenNo formal declaration	open	No formal statement	No Result decision
#621	Let $G$ be a graph on $n$ vertices, $\alpha_1(G)$ be the maximum number of edges that contain at most one edge from every triangle, and $\tau_1(G)$ be the minimum number of edges that contain at least one edge from every triangle.proved (Lean)Formalized	proved (Lean)	In Lean	No Result decision
#622	No statement retained — open to read what the source holdsprovedNo formal declaration	proved	No formal statement	No Result decision
#623	Let $X$ be a set of cardinality $\aleph_\omega$ and $f$ be a function from the finite subsets of $X$ to $X$ such that $f(A)\not\in A$ for all $A$ . Must there exist an infinite $Y\subseteq X$ that is independent - that is, for all finite $B\subset Y$ we have $f(B)\not\in Y$ ?openFormalized	open	In Lean	No Result decision
#624	Let $X$ be a finite set of size $n$ and $H(n)$ be such that there is a function $f:\{A : A\subseteq X\}\to X$ so that for every $Y\subseteq X$ with $\lvert Y\rvert \geq H(n)$ we have $\left\{ f(A) : A\subseteq Y\right\}=X$ . Prove that $H(n)-\log_2 n \to \infty$ .openFormalized	open	In Lean	No Result decision

Problems

Search problems.science