Vela Mathematics Program: problems

Narrowed toopen ×chromatic number ×Clear all

Problem ledger

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 · 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 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 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 · $1000erdos:625

Erdős problem 625

graph theorychromatic numberN/A

declared openerdos:626

Erdős problem 626

graph theorychromatic numbercyclespossible

declared openerdos:627

Erdős problem 627

graph theorychromatic numberpossible

declared openerdos:629

Erdős problem 629

graph theorychromatic numberpossible2 sources

declared openerdos:640

Erdős problem 640

graph theorychromatic numberN/A

declared openerdos:704

Erdős problem 704

graph theorygeometrychromatic numberN/A

declared openerdos:706

Erdős problem 706

graph theorychromatic numberpossible

declared openerdos:738

Erdős problem 738

graph theorychromatic numberN/A

declared open · formalizederdos:740

True ↔ ∀ (V : Type u_1) (G : SimpleGraph V), Cardinal.aleph0 ≤ G.chromaticCardinal → ∀ (r : ℕ), ∃ H, H.coe.chromaticCardinal = G.chromaticCardinal ∧ Erdos740.NoShortOddCycle H.coe r

graph theorychromatic numberN/A2 sources

declared openerdos:761

Erdős problem 761

graph theorychromatic numberN/A

declared openerdos:836

Erdős problem 836

graph theoryhypergraphschromatic numberN/A2 sources

declared openerdos:917

Erdős problem 917

graph theorychromatic numberN/A

declared open · formalizederdos:918

True ↔ ∃ V G, Cardinal.mk V = Cardinal.aleph 2 ∧ G.chromaticCardinal = Cardinal.aleph 2 ∧ ∀ (W : Set V), Cardinal.mk ↑W = Cardinal.aleph 1 → (SimpleGraph.induce W G).chromaticCardinal ≤ Cardinal.aleph0

graph theorychromatic numberN/A2 sources

declared openerdos:919

Erdős problem 919

graph theorychromatic numberN/A

declared open · formalizederdos:944

True ↔ ∀ k ≥ 4, ∀ r ≥ 1, ∃ V G, Erdos944.SimpleGraph.IsErdos944 G k r

graph theorychromatic numberN/A2 sources

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 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 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 openerdos:1156

Erdős problem 1156

graph theorychromatic numberN/A

declared open · formalizederdos:1175

True ↔ ∀ (κ : Cardinal.{u_1}), Cardinal.aleph0 < κ → ∃ μ, ∀ (V : Type u_1) (G : SimpleGraph V), G.chromaticCardinal = μ → ∃ H, H.coe.CliqueFree 3 ∧ H.coe.chromaticCardinal = κ

set theorychromatic numberN/A2 sources

declared openerdos:1177

For a finite forbidden triple system

G

, what exact uncountable chromatic cardinalities occur among

G

-free triple systems, and how do those spectra interact? The revised manuscript answers the three exact-cardinal questions and claims a complete spectrum dichotomy.

set theorychromatic numberhypergraphsN/A3 sources

Problems · Vela Mathematics Program

Problem ledger

Search problems.science