Skip to content

Problems · Vela Mathematics Program

Narrowed toopen ×graph theory ×Clear all

Problem ledger

119 problems · 1/3NumberSourcesGraph view
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 open · formalizederdos:61
sorry ↔ ∀ {α : Type u_1} [inst : Fintype α] [inst_1 : DecidableEq α] (H : SimpleGraph α), ∃ c > 0, Erdos61.IsErdosHajnalLowerBound H fun n => ↑n ^ c
graph theoryN/A2 sources
declared openerdos:62
Erdős problem 62
graph theoryN/A
declared openerdos:65
Erdős problem 65
graph theorycyclesN/A
declared open · formalizederdos:70
True ↔ ∀ (β : Ordinal.{0}) (n : ℕ), β.card ≤ Cardinal.aleph0 → 2 ≤ n → Erdos70.OrdinalCardinalRamsey3 Cardinal.continuum.ord β ↑n
graph theoryramsey theoryset theoryN/A2 sources
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 open · formalizederdos:75
True ↔ ∃ V G, G.chromaticCardinal = Cardinal.aleph 1 ∧ Cardinal.mk V = Cardinal.aleph 1 ∧ ∀ ε > 0, ∀ᶠ (n : ℕ) in Filter.atTop, ∀ (H : G.Subgraph), H.verts.ncard = n → ∃ I, ↑I ⊆ H.verts ∧ G.IsIndepSet ↑I ∧ ↑I.card > ↑n ^ (1 - ε)
graph theorychromatic numberN/A3 sources
declared open · $250erdos:77
Erdős problem 77
graph theoryramsey theoryA059442
declared open · $100erdos:78
Erdős problem 78
graph theoryramsey theoryA0594422 sources
declared openerdos:80
Erdős problem 80
graph theoryramsey theoryN/A
declared openerdos:81
Erdős problem 81
graph theorypossible2 sources
declared open · formalizederdos:82
Filter.Tendsto (fun n => ↑(Erdos82.F n) / Real.log ↑n) Filter.atTop Filter.atTop
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 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 openerdos:111
Erdős problem 111
graph theorychromatic numberset theoryN/A
declared openerdos:112
Erdős problem 112
graph theoryramsey theorypossible
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 openerdos:149
Erdős problem 149
graph theoryN/A
declared openerdos:151
Erdős problem 151
graph theorypossible
declared openerdos:159
Erdős problem 159
graph theoryramsey theorypossible
declared open · $250erdos:165
Erdős problem 165
graph theoryramsey theoryA0007912 sources
declared openerdos:181
Erdős problem 181
graph theoryramsey theorypossible
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 open · $500erdos:500
Erdős problem 500
graph theoryhypergraphsturan numberA140462
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 m1≤⋯≤mkm_1\leq\cdots\leq m_k and nn be sufficiently large. If TT is a tree on nn vertices and GG is the complete multipartite graph with vertex class sizes m1,…,mkm_1,\ldots,m_k, prove that R(T,G)≤(χ(G)−1)(R(T,Km1,m2)−1)+m1R(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

Search problems.science

Find a Problem, Result, source, or page