Skip to content

Problems · Vela Mathematics Program

Narrowed tocycles ×Clear all

Problem ledger

22 problemsGraph view
declared provederdos:57
Erdős problem 57
graph theorychromatic numbercyclesN/A
declared provederdos:58
Erdős problem 58
graph theorychromatic numbercyclesN/A
declared open · formalizederdos:60
∃ c > 0, ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (G : SimpleGraph (Fin n)) [inst : DecidableRel G.Adj], SimpleGraph.extremalNumber n (SimpleGraph.cycleGraph 4) < G.edgeFinset.card → c * √↑n ≤ ↑{H' | Nonempty (H'.coe ≃g SimpleGraph.cycleGraph 4)}.ncard
graph theorycyclesA0068552 sources
declared provederdos:63
Erdős problem 63
graph theorychromatic numbercyclesN/A
declared falsifiable · formalized · $1000erdos:64
True ↔ ∀ (V : Type u_1) (G : SimpleGraph V) [inst : Fintype V] [inst_1 : DecidableRel G.Adj], G.minDegree ≥ 3 → ∃ k v c, k ≥ 2 ∧ c.IsCycle ∧ c.length = 2 ^ k
graph theorycyclesN/A2 sources
declared openerdos:65
Erdős problem 65
graph theorycyclesN/A
declared proved (Lean) · formalizederdos:71
True ↔ ∀ (P : Set ℕ), P.IsAPOfLength ⊤ → (∃ n ∈ P, Even n) → ∃ c, ∀ (V : Type) [inst : Fintype V] [DecidableEq V] (G : SimpleGraph V) [inst_2 : DecidableRel G.Adj], c ≤ G.averageDegree → ∃ v w, w.IsCycle ∧ w.length ∈ P
graph theorycyclesN/A4 sources
declared proved · $100erdos:72
Erdős problem 72
graph theorycyclesN/A
declared open · formalized · $500erdos:74
∀ {V : Type u} {G : SimpleGraph V} (A : G.Subgraph), (Erdos74.SimpleGraph.edgeDistancesToBipartite A).Nonempty
graph theorychromatic numbercyclesN/A2 sources
declared openerdos:84
Erdős problem 84
graph theorycyclespossible
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 open · formalizederdos:184
∃ f, (f =O[Filter.atTop] fun n => ↑n) ∧ ∀ {V : Type u_1} [inst : Fintype V] [DecidableEq V] (G : SimpleGraph V), ∃ D, (∀ H ∈ D, Erdos184.IsCycleOrEdge H.coe) ∧ Erdos184.IsDecomposition G D ∧ ↑D.card ≤ f (Fintype.card V)
graph theorycyclespossible2 sources
declared openerdos:584
Must every graph with nn vertices and δn2\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 nn.
graph theorycyclesN/A2 sources
declared openerdos:585
Erdős problem 585
graph theorycyclespossible
declared openerdos:626
Erdős problem 626
graph theorychromatic numbercyclespossible
declared openerdos:642
Erdős problem 642
graph theorycyclespossible
declared provederdos:752
Erdős problem 752
graph theorycyclesN/A
declared provederdos:916
Erdős problem 916
graph theorycyclesN/A
declared provederdos:921
Erdős problem 921
graph theorychromatic numbercyclespossible
declared disprovederdos:1006
Erdős problem 1006
graph theorycyclesN/A
declared openerdos:1016
Erdős problem 1016
graph theorycyclesA105206

Search problems.science

Find a Problem, Result, source, or page