✦ 5 frontiers

read-only vieweressays

erdős #82

← #81 · #83 → (packet.json; erdosproblems.com)

Let $F (n)$ be maximal such that every graph on $n$ vertices contains a regular induced subgraph on at least $F (n)$ vertices. Prove that $F (n) / lo g n \to \infty$ .

Worked, still open.

graph theory · open · formalized (Lean) · 0 attempts

machinery: graph-coloring,Ramsey-theory,extremal-set-system,regular-induced-subgraph,probabilistic-method,asymptotic-lower-bound

use this record

vela registry pull vfr_37aec80d874a0239

vela reproduce examples/erdos-problems

evidence

unverified AI candidates (2)

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

What you wrote is a famous **open** problem.

candidate solution ↗

llm-hunter · gpt 5.2, gpt pro 5.2 · unverified

2 LLM attack(s) recorded (gpt 5.2, gpt pro 5.2); unverified.

candidate solution ↗

formal

AMS 5 · open (literature)

theorem erdos_82 : Tendsto (fun n => F n / Real.log n) atTop atTop

formal-conjectures/82.lean ↗

oeis

A120414 — a(0)=0, a(1)=1; thereafter a(n) = ceiling((3/2)^(n-3)*n*(n-1)).0,1,2,6,18,45,102,213,426,821,1538,2820,5075,8996,15743,27247,46709,79405,133996,224640,374400,620715,1024180,1682580,27 A390256 — Minimum size of maximum clique or independent set of a graph on n vertices.0,1,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4 A390257 — Minimum size of maximum regular induced subgraph of a graph on n vertices.0,1,2,2,2,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5 A390919 — Number of graphs with n vertices that have no induced regular subgraph of order 5 or greater.1,2,4,11,31,130,728,6027,66308,818276,8336902,45933753,79888458,23814804,512906,954,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,A392636 — Number of graphs with n vertices that have no induced regular subgraph of order 6 or greater.1,2,4,11,34,148,960,10390,188560,5317230,202396620,8905369148,384098286140,13129756210164 A394400 — Number of graphs with n vertices that have no induced regular subgraph of order 4 or greater.1,2,4,7,11,10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,A394462 — Number of graphs with n vertices that have no induced regular subgraph of order 6.1,2,4,11,34,148,964,10472,191776,5524670,219302174,10333796899,493296884096,19658348081642 A394539 — Number of graphs with n vertices that have no induced regular subgraph of order 5.1,2,4,11,31,136,792,7185,94893,1714430,37216434,854671213,18369802688,328662169364,4236467418682,29440587191035,80145694 A394563 — Least integer a(n) such that every graph on a(n) vertices has an induced regular subgraph of order at least n.1,2,5,7,17 A394564 — Least integer a(n) such that every graph on a(n) vertices has an induced regular subgraph of order n.1,2,6,8,21 A394573 — Number of graphs with n vertices that have no induced regular subgraph of order 4.1,2,4,7,12,12,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,A394574 — a(n) is the greatest k such that every graph on n vertices has an induced regular subgraph of order k.0,1,2,2,2,2,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5 A394930 — Number of graphs with n vertices that have no induced regular subgraph of order 7.1,2,4,11,34,156,1038,12246,269646,11453460,907948002,127924347122,30302185606487 A394933 — Number of graphs with n vertices that have no induced regular subgraph of order 7 or greater.1,2,4,11,34,156,1038,12226,268920,11361262,885194426,119298229792,25716285392622

links

this site · link

status

open

finding.noted · reviewer:will-blair · 1 day

renders the record as of vev_d199cb2e · 1,338 events · hub