Vela Mathematics Program: problems

Narrowed tograph theory ×Clear all

Problem ledger

275 problems · 6/6Number SourcesGraph view

declared solved (Lean) · formalizederdos:1028

(fun n => ↑(Erdos1028.H n)) =Θ[Filter.atTop] fun n => ↑n ^ (3 / 2)

graph theorydiscrepancypossible5 sources

declared open · $100erdos:1029

Erdős problem 1029

graph theoryramsey theoryA059442

declared openerdos:1030

Erdős problem 1030

graph theoryramsey theoryA000791 · A059442

declared provederdos:1031

Erdős problem 1031

graph theorypossible

declared openerdos:1032

Do arbitrarily large 4-chromatic edge-critical graphs exist with minimum degree bounded below by a positive constant times the number of vertices?

graph theorychromatic numberpossible3 sources

declared openerdos:1033

Erdős problem 1033

graph theorypossible2 sources

declared disproved (Lean) · formalizederdos:1034

False ↔ ∀ (ε : ℝ), 0 < ε → ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (G : SimpleGraph (Fin n)), ↑n ^ 2 / 4 < ↑G.edgeSet.ncard → ∃ T, G.IsNClique 3 T ∧ ∃ Y, Erdos1034.JoinedToTwo G T Y ∧ (1 / 2 - ε) * ↑n < ↑Y.card

graph theorypossible5 sources

declared openerdos:1035

Erdős problem 1035

graph theorypossible

declared proved (Lean) · formalizederdos:1036

True ↔ ∀ (c : ℝ), 0 < c → ∃ δ, 0 < δ ∧ ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (G : SimpleGraph (Fin n)), ↑G.cliqueNum ≤ c * Real.log ↑n → ↑G.indepNum ≤ c * Real.log ↑n → Erdos1036.HasManyNonIsomorphicInducedSubgraphs G (2 ^ (δ * ↑n))

graph theorypossible5 sources

declared disproved (Lean) · formalizederdos:1037

False ↔ ∀ (ε : ℝ), 0 < ε → ∀ (C : ℝ), ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (G : SimpleGraph (Fin n)), (∀ (d : ℕ), {v | (G.neighborSet v).ncard = d}.ncard ≤ 2) → (1 / 2 + ε) * ↑n < ↑(Set.range fun v => (G.neighborSet v).ncard).ncard → ∃ s, Erdos1037.IsTrivialSet G s ∧ C * Real.log ↑n < ↑s.ncard

graph theoryN/A5 sources

declared openerdos:1066

Erdős problem 1066

graph theoryplanar graphspossible

declared disproved (Lean) · formalizederdos:1067

False ↔ ∀ (V : Type) (G : SimpleGraph V), G.chromaticCardinal = Cardinal.aleph 1 → ∃ H, H.coe.chromaticCardinal = Cardinal.aleph 1 ∧ H.coe.InfinitelyConnected

graph theoryset theoryN/A5 sources

declared open · formalizederdos:1068

True ↔ ∀ (V : Type) (G : SimpleGraph V), G.chromaticCardinal = Cardinal.aleph 1 → ∃ s, s.Countable ∧ (SimpleGraph.induce s G).InfinitelyConnected

graph theoryset theorychromatic numberN/A2 sources

declared disproved · formalizederdos:1077

False ↔ ∀ ε > 0, ε < 1 → ∀ α > 0, α < 1 → ∀ᶠ (D : ℝ) in Filter.atTop, ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (G : SimpleGraph (Fin n)), ↑G.edgeSet.ncard > ↑n ^ (1 + α) → ∃ H, H.coe.IsBalanced D ∧ ↑H.verts.ncard > ↑n ^ (1 - α) ∧ ↑H.edgeSet.ncard > ε * ↑H.verts.ncard ^ (1 + α)

graph theoryN/A2 sources

declared provederdos:1078

Erdős problem 1078

graph theoryN/A

declared solvederdos:1079

Erdős problem 1079

graph theoryturan numberN/A

declared disproved (Lean) · formalizederdos:1080

False ↔ ∃ c > 0, ∀ (V : Type) [inst : Fintype V] [Nonempty V] (G : SimpleGraph V) (X Y : Set V), Erdos1080.IsBipartition G X Y → X.ncard = ⌊↑(Fintype.card V) ^ (2 / 3)⌋₊ → ↑G.edgeSet.ncard ≥ c * ↑(Fintype.card V) → ∃ v walk, walk.IsCycle ∧ walk.length = 6

graph theorypossible5 sources

declared open · formalizederdos:1104

∃ c₁, 0 < c₁ ∧ c₁ ≤ 1 ∧ ∀ᶠ (n : ℕ) in Filter.atTop, c₁ * √↑n / √(Real.log ↑n) ≤ ↑(Erdos1104.triangleFreeMaxChromatic n)

graph theorychromatic numberA2925282 sources

declared proved · formalizederdos:1105

True ↔ ∀ (k : ℕ), 3 ≤ k → (fun n => ↑((SimpleGraph.cycleGraph k).antiRamseyNum n) - ((↑k - 2) / 2 + 1 / (↑k - 1)) * ↑n) =O[Filter.atTop] fun x => 1

graph theoryramsey theorypossible3 sources

declared openerdos:1111

Erdős problem 1111

graph theorypossible

declared openerdos:1155

Erdős problem 1155

graph theoryN/A

declared openerdos:1156

Erdős problem 1156

graph theorychromatic numberN/A

declared openerdos:1178

Erdős problem 1178

graph theoryhypergraphsN/A

declared openerdos:1182

Erdős problem 1182

graph theoryramsey theorypossible

declared disprovederdos:1216

Erdős problem 1216

graph theoryramsey theorypossible

Problems · Vela Mathematics Program

Problem ledger

Search problems.science