Vela Mathematics Program: problems

graph theoryA120414 · A390256 · A390257 · A390919 · A392636 · A394400 · A394462 · A394539 · A394563 · A394564 · A394573 · A394574 · A394930 · A3949332 sources

declared openerdos:84

Erdős problem 84

graph theorycyclespossible

declared open · formalizederdos:85

True ↔ ∀ᶠ (n : ℕ) in Filter.atTop, Erdos85.f n ≤ Erdos85.f (n + 1)

graph theoryA006672 · possible2 sources

declared open · $100erdos:86

Erdős problem 86

graph theoryA245762

declared openerdos:87

Erdős problem 87

graph theoryramsey theoryA059442 · possible

declared proved · $100erdos:88

Erdős problem 88

graph theoryramsey theoryN/A

declared open · formalizederdos:108

True ↔ ∀ r ≥ 4, ∀ k ≥ 2, ∃ f, ∀ (V : Type u) (G : SimpleGraph V), Nonempty V → ↑f ≤ G.chromaticNumber → ∃ H, H.coe.girth ≥ r ∧ H.coe.chromaticNumber ≥ ↑k

graph theorychromatic numbercyclespossible2 sources

declared disprovederdos:110

Erdős problem 110

graph theorychromatic numbercyclesN/A

declared openerdos:111

Erdős problem 111

graph theorychromatic numberset theoryN/A

declared openerdos:112

Erdős problem 112

graph theoryramsey theorypossible

declared disproved · $500erdos:113

Erdős problem 113

graph theoryturan numberN/A

declared provederdos:127

Erdős problem 127

graph theorypossible

declared falsifiable · formalized · $250erdos:128

True ↔ ∀ (V : Type) [inst : Fintype V] (G : SimpleGraph V), (∀ (V' : Set V), 2 * V'.ncard + 1 ≥ Fintype.card V → 50 * (SimpleGraph.induce V' G).edgeSet.ncard > Fintype.card V ^ 2) → ¬G.CliqueFree 3

graph theoryN/A2 sources

declared openerdos:129

Erdős problem 129

graph theoryramsey theorypossible

declared open · formalizederdos:130

For an infinite planar set in strong general position, how large can the chromatic and clique numbers of its positive-integer-distance graph be - in particular, can the chromatic number be infinite? Yes: there is such a set, no three collinear and no four concyclic, with infinite chromatic number.

graph theorychromatic numberN/A4 sources

declared disprovederdos:133

Erdős problem 133

graph theorypossible

declared proved (Lean) · formalizederdos:134

True ↔ ∀ (ε δ : ℝ), 0 < ε → 0 < δ → ∃ N, ∀ n ≥ N, ∀ (G : SimpleGraph (Fin n)), G.CliqueFree 3 → (∀ (v : Fin n), ↑(G.degree v) < (↑n).rpow (1 / 2 - ε)) → ∃ H, G ≤ H ∧ H.CliqueFree 3 ∧ (∀ (x y : Fin n), x ≠ y → H.Adj x y ∨ ∃ z, H.Adj x z ∧ H.Adj z y) ∧ ↑(H.edgeFinset \ G.edgeFinset).card ≤ δ * ↑n ^ 2

graph theoryN/A5 sources

declared solvederdos:136

Erdős problem 136

graph theorypossible

declared open (Lean) · formalized · $500erdos:146

H

is bipartite and

r

-degenerate, is

\mathrm{ex}(n;H) \ll n^{2-1/r}

(a $500 Erdős-Simonovits prize conjecture)? A counterexample refutes the degeneracy conjecture.

graph theoryturan numberN/A3 sources

declared disproved · $500erdos:147

Erdős problem 147

graph theoryturan numberN/A

declared openerdos:149

Erdős problem 149

graph theoryN/A

declared proved (Lean) · formalizederdos:150

True ↔ ∃ α < 2, Filter.Tendsto (fun n => ↑(Erdos150.maxMinimalCuts n) ^ (1 / ↑n)) Filter.atTop (nhds α)

graph theorypossible5 sources

declared openerdos:151

Erdős problem 151

graph theorypossible

declared openerdos:159

Erdős problem 159

graph theoryramsey theorypossible

declared provederdos:163

Erdős problem 163

graph theoryramsey theoryN/A

Problems · Vela Mathematics Program

Problem ledger

Search problems.science