Vela Mathematics Program: problems

Narrowed toopen ×source:erdos-problems ×Clear all

Problem ledger

604 problems · 6/13Number SourcesGraph view

declared open · formalizederdos:521

analysispolynomialsprobabilityN/A4 sources

declared open · formalizederdos:522

P_n(z) = \sum_{k=0}^n \varepsilon_k z^k

with independent uniform signs, does the number

R_n

of roots in

|z| \le 1

satisfy

R_n/(n/2) \to 1

almost surely? The manuscript proves the strong law with

R_n = n/2 + O_\omega(n^{149/150})

analysispolynomialsprobabilityN/A4 sources

declared openerdos:524

Erdős problem 524

analysisprobabilitypolynomialsN/A3 sources

declared openerdos:528

Erdős problem 528

geometryA387897 · A156816

declared openerdos:529

Erdős problem 529

geometryprobabilityN/A

declared openerdos:530

Erdős problem 530

number theorysidon setsA143824 · possible

declared openerdos:531

Erdős problem 531

number theoryramsey theorypossible

declared open · formalizederdos:535

∀ r ≥ 3, ∃ c > 0, ∀ᶠ (N : ℕ) in Filter.atTop, ↑(Erdos535.f r N) ≤ ↑N ^ (c / Real.log (Real.log ↑N))

number theorypossible3 sources

declared open · formalizederdos:536

True ↔ ∀ ε > 0, ∀ᶠ (N : ℕ) in Filter.atTop, ∀ A ⊆ Finset.Icc 1 N, ε * ↑N ≤ ↑A.card → ∃ a ∈ A, ∃ b ∈ A, ∃ c ∈ A, {a, b, c}.card = 3 ∧ a.lcm b = b.lcm c ∧ b.lcm c = a.lcm c

number theorypossible3 sources

declared open · formalizederdos:538

If each integer has at most

r

representations

m = pa

with

p

prime and

a \in A \subseteq [1, N]

, what is the best upper bound for

\sum_{a \in A} 1/a

? The candidate proof gives the matching order

\Theta_r(\log N / \log\log N)

number theoryN/A5 sources

declared open · formalizederdos:539

For

|A| = n

, how small can the cofactor set

Q(A) = \{a / \gcd(a,b) : a, b \in A\}

be? The answer is

h(n) = n^{1/2 + o(1)}

: a new upper bound

h(n) \le n^{1/2} \exp(O(\sqrt{\log n}))

matches the classical lower bound.

number theorypossible5 sources

declared openerdos:544

Erdős problem 544

graph theoryramsey theoryA000791

declared openerdos:545

Erdős problem 545

graph theoryramsey theoryA059442 · possible

declared openerdos:550

Let

m_1\leq\cdots\leq m_k

and

n

be sufficiently large. If

T

is a tree on

n

vertices and

G

is the complete multipartite graph with vertex class sizes

m_1,\ldots,m_k

, prove that

R(T,G)\leq (\chi(G)-1)(R(T,K_{m_1,m_2})-1)+m_1

graph theoryramsey theoryN/A4 sources

declared openerdos:552

Erdős problem 552

graph theoryramsey theoryA006672

declared openerdos:554

Erdős problem 554

graph theoryramsey theorypossible

declared openerdos:555

Erdős problem 555

graph theoryramsey theoryA389313 · possible

declared openerdos:557

Erdős problem 557

graph theoryramsey theoryN/A

declared openerdos:558

Erdős problem 558

graph theoryramsey theorypossible

declared openerdos:560

Erdős problem 560

graph theoryramsey theorypossible

declared openerdos:561

Erdős problem 561

graph theoryramsey theoryN/A

declared open · formalizederdos:562

True ↔ ∀ r ≥ 3, (fun n => Real.log^[r - 1] ↑(Combinatorics.hypergraphRamsey r n)) =Θ[Filter.atTop] fun n => ↑n

graph theoryramsey theoryhypergraphspossible2 sources

declared openerdos:563

Erdős problem 563

graph theoryramsey theoryhypergraphsN/A

declared open · formalized · $500erdos:564

True ↔ ∃ c > 0, ∀ᶠ (n : ℕ) in Filter.atTop, 2 ^ 2 ^ (c * n) ≤ ↑(Combinatorics.hypergraphRamsey 3 n)

graph theoryramsey theoryhypergraphspossible2 sources

declared open · formalizederdos:566

True ↔ ∀ (p : ℕ) (G : SimpleGraph (Fin p)), (∀ (S : Finset (Fin p)), 2 ≤ S.card → (SimpleGraph.induce (↑S) G).edgeSet.ncard ≤ 2 * S.card - 3) → ∃ c > 0, ∀ (n : ℕ) (H : SimpleGraph (Fin n)) [inst : DecidableRel H.Adj], (∀ (v : Fin n), 0 < H.degree v) → ↑(G.sizeRamsey H) ≤ c * ↑H.edgeSet.ncard

graph theoryramsey theoryN/A2 sources

declared open · formalizederdos:567

True ↔ Erdos567.Q3.IsRamseySizeLinear

graph theoryramsey theoryN/A2 sources

declared openerdos:568

Erdős problem 568

graph theoryramsey theoryN/A

declared openerdos:569

Erdős problem 569

graph theoryramsey theoryN/A

declared openerdos:571

Erdős problem 571

graph theoryturan numberN/A

declared openerdos:572

Erdős problem 572

graph theoryturan numberpossible

declared openerdos:573

Erdős problem 573

graph theoryturan numberA006856

declared openerdos:575

Erdős problem 575

graph theoryturan numberN/A

declared openerdos:576

Erdős problem 576

graph theoryturan numberpossible

declared open · formalizederdos:579

True ↔ ∀ (δ : ℝ), 0 < δ → ∃ c, 0 < c ∧ ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (G : SimpleGraph (Fin n)), Erdos579.octahedron.Free G → δ * ↑n ^ 2 ≤ ↑G.edgeFinset.card → c * ↑n ≤ ↑G.indepNum

graph theoryturan numberN/A2 sources

declared openerdos:584

Must every graph with

n

vertices and

\delta n^2

edges contain large subgraphs in which every two edges lie on specified short cycles? A dense high-girth construction refutes the statement when

\delta

may shrink with

n

graph theorycyclesN/A2 sources

declared openerdos:585

Erdős problem 585

graph theorycyclespossible

declared open · $100erdos:588

Erdős problem 588

geometryA006065 · A008997

declared openerdos:589

Erdős problem 589

geometrypossible

declared open · formalized · $1000erdos:592

∀ (β : Ordinal.{u}), β.card ≤ Cardinal.aleph0 → OrdinalCardinalRamsey (Ordinal.omega0 ^ β) (Ordinal.omega0 ^ β) 3 ↔ sorry β

set theoryramsey theoryN/A2 sources

declared open · formalized · $500erdos:593

Which finite triple systems occur in every triple system of uncountable chromatic number? The claimed characterization: exactly those that, after removing isolated vertices, are linear, have every hyperedge-node of their Levi graph meeting a bridge, and have every Berge cycle even.

set theorygraph theoryhypergraphsN/A4 sources

declared open · formalized · $250erdos:595

True ↔ ∃ V, ∃ (_ : Infinite V), ∃ G, G.CliqueFree 4 ∧ ¬Erdos595.IsCountableUnionOfTriangleFree G

graph theoryset theoryN/A2 sources

declared open · formalizederdos:596

∀ {U₁ U₂ : Type} (G₁ : SimpleGraph U₁) (G₂ : SimpleGraph U₂), G₁.IsErdosHajnalExceptional G₂ ↔ (fun {U₁ U₂} => sorry) G₁ G₂

graph theoryramsey theoryset theoryN/A2 sources

declared openerdos:597

Erdős problem 597

graph theoryramsey theoryset theoryN/A

declared open · formalizederdos:598

∀ (m : Type u_1) [Infinite m], True ↔ ∃ c, ∀ (X : Set m), Cardinal.mk ↑X = Erdos598.κ → c '' {s | ↑s ⊆ X} = Set.univ

set theoryramsey theoryN/A3 sources

declared open · formalizederdos:600

True ↔ ∀ (r : ℕ), 2 ≤ r → Filter.Tendsto (fun n => ↑(Erdos600.eFunction n (r + 1)) - ↑(Erdos600.eFunction n r)) Filter.atTop Filter.atTop

graph theorypossible2 sources

declared open · $500erdos:601

Erdős problem 601

graph theoryset theoryN/A

declared open · formalizederdos:602

¬Erdos602.disjoint_without_infinite_claim

combinatoricsset theoryN/A3 sources

declared open · $500erdos:604

Erdős problem 604

geometrydistancespossible

declared openerdos:609

Erdős problem 609

graph theoryramsey theorypossible

declared openerdos:611

Erdős problem 611

graph theoryN/A

Problems · Vela Mathematics Program

Problem ledger

Search problems.science