Skip to content

Erdős Problems

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

Add a contributionCollection details
Collection coverage

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
More filters

Coverage is source-observation coverage, not Problem completeness. Inspect coverage

Problems

275 Problems

6/6

NumberQuestionOpen
#1013No statement retained — open to read what the source holdsopenNo formal declaration
#1014Let R(k,l)R(k,l) be the Ramsey number, so the minimal nn such that every graph on at least nn vertices contains either a KkK_k or an independent set on ll vertices.proved (Lean)Formalized
#1015No statement retained — open to read what the source holdssolvedNo formal declaration
#1016No statement retained — open to read what the source holdsopenNo formal declaration
#1017No statement retained — open to read what the source holdsopenNo formal declaration
#1018No statement retained — open to read what the source holdssolvedNo formal declaration
#1019No statement retained — open to read what the source holdsprovedNo formal declaration
#1020No statement retained — open to read what the source holdsfalsifiableNo formal declaration
#1021No statement retained — open to read what the source holdsprovedNo formal declaration
#1024No statement retained — open to read what the source holdssolvedNo formal declaration
#1028Let H(n)=min⁡fmax⁡X⊆{1,…,n}∣∑x<y∈Xf(x,y)∣,H(n)=\min_f \max_{X\subseteq \{1,\ldots,n\}} \left\lvert \sum_{x<y\in X} f(x,y)\right\rvert, where ff ranges over all functions f:{1,…,n}2→{−1,1}f:\{1,\ldots,n\}^2\to \{-1,1\}. Estimate H(n)H(n).solved (Lean)Formalized
#1029No statement retained — open to read what the source holdsopenNo formal declaration
#1030No statement retained — open to read what the source holdsopenNo formal declaration
#1031No statement retained — open to read what the source holdsprovedNo formal declaration
#1032No statement retained — open to read what the source holdsopenNo formal declaration
#1033No statement retained — open to read what the source holdsopenNo formal declaration
#1034Let GG be a graph on nn vertices with >n2/4>n^2/4 many edges. Must there be a triangle TT in GG and vertices y1,…,yty_1,\ldots,y_t, where t>(12−o(1))nt>(\frac{1}{2}-o(1))n, such that every yiy_i is joined to at least two vertices of TT?disproved (Lean)Formalized
#1035No statement retained — open to read what the source holdsopenNo formal declaration
#1036Let GG be a graph on nn vertices which does not contain a trivial (empty or complete) graph on more than clog⁡nc\log n vertices. Must GG contain at least 2Ωc(n)2^{\Omega_c(n)} many induced subgraphs which are not pairwise isomorphic?proved (Lean)Formalized
#1037Let GG be a graph on nn vertices in which every degree occurs at most twice, and the number of distinct degrees is >(12+ϵ)n>(\frac{1}{2}+\epsilon)n. Must GG contain a trivial (empty or complete) subgraph of size 'much larger' than log⁡n\log n?disproved (Lean)Formalized
#1066No statement retained — open to read what the source holdsopenNo formal declaration
#1067Does every graph with chromatic number ℵ1\aleph_1 contain an infinitely connected subgraph with chromatic number ℵ1\aleph_1?disproved (Lean)Formalized
#1068Does every graph with chromatic number ℵ1\aleph_1 contain a countable subgraph which is infinitely connected?openFormalized
#1077We call a graph DD-balanced (or DD-almost-regular) if the maximum degree is at most DD times the minimum degree.disprovedFormalized
#1078No statement retained — open to read what the source holdsprovedNo formal declaration
#1079No statement retained — open to read what the source holdssolvedNo formal declaration
#1080Let GG be a bipartite graph on nn vertices such that one part has ⌊n2/3⌋\lfloor n^{2/3}\rfloor vertices. Is there a constant c>0c>0 such that if GG has at least cncn edges then GG must contain a C6C_6?disproved (Lean)Formalized
#1104Lower bound (Hefty–Horn–King–Pfender 2025). There exists a constant c1∈(0,1]c_1 \in (0,1] such that, for sufficiently large nn, c1nlog⁡n≤f(n), c_1 \sqrt{\frac{n}{\log n}} \le f(n), where f(n)f(n) denotes the maximum chromatic number of a triangle-free graph on nn vertices, formalized as triangleFreeMaxChromatic n.openFormalized
#1105The anti-Ramsey number AR(n,G)\mathrm{AR}(n,G) is the maximum possible number of colours in which the edges of KnK_n can be coloured without creating a rainbow copy of GG (i.e. one in which all edges have different colours).provedFormalized
#1111No statement retained — open to read what the source holdsopenNo formal declaration
#1155No statement retained — open to read what the source holdsopenNo formal declaration
#1156No statement retained — open to read what the source holdsopenNo formal declaration
#1178No statement retained — open to read what the source holdsopenNo formal declaration
#1182No statement retained — open to read what the source holdsopenNo formal declaration
#1216No statement retained — open to read what the source holdsdisprovedNo formal declaration

Search problems.science

Find a Problem, Result, source, or page