Cycle lengths in graphs of large chromatic number

DefinitionErdős Problem 751#✓fully proved

The statement that both of the following hold: (i) for every natural number \(k\) there is a simple graph \(G\) with chromatic number \(4\) in which any two distinct cycle lengths of \(G\) differ by at least \(k\); (ii) for all natural numbers \(k\) and \(g\) there is a simple graph \(G\) with chromatic number \(4\) and girth at least \(g\) in which any two distinct cycle lengths of \(G\) differ by at least \(k\).

def conjecture : Prop :=
  (∀ k : ℕ, ∃ (V : Type) (G : SimpleGraph V), G.chromaticNumber = 4 ∧
    ∀ m ∈ G.cycleLengths, ∀ m' ∈ G.cycleLengths, m < m' → m + k ≤ m') ∧
  (∀ k g : ℕ, ∃ (V : Type) (G : SimpleGraph V), G.chromaticNumber = 4 ∧
    g ≤ G.girth ∧
    ∀ m ∈ G.cycleLengths, ∀ m' ∈ G.cycleLengths, m < m' → m + k ≤ m')
Uses 1 · Used by 1
Statement usesCycle lengths
Used byErdős Problem 751 is false

TheoremErdős Problem 751 is false#●ready to prove

It is not the case that both of the following hold: (i) for every natural number \(k\) there is a simple graph \(G\) with chromatic number \(4\) in which any two distinct cycle lengths of \(G\) differ by at least \(k\); (ii) for all natural numbers \(k\) and \(g\) there is a simple graph \(G\) with chromatic number \(4\) and girth at least \(g\) in which any two distinct cycle lengths of \(G\) differ by at least \(k\).

public theorem_wanted conjecture_refuted : ¬ conjecture
Sources
  • J. A. Bondy and A. Vince, Cycles in a graph whose lengths differ by one or two, Journal of Graph Theory 27 (1998), 11-15, https://doi.org/10.1002/(SICI)1097-0118(199801)27:1%3C11::AID-JGT3%3E3.0.CO;2-J; Jun Gao, Qingyi Huo, Chun-Hung Liu, and Jie Ma, A unified proof of conjectures on cycle lengths in graphs, arXiv:1904.08126v3, https://arxiv.org/abs/1904.08126v3.
Uses 1
Statement usesErdős Problem 751

DefinitionOdd cycle lengths and infinite chromatic number (Erdős Problem 57)#✓fully proved

Let \(G\) be a graph on an arbitrary vertex set that has no proper colouring with finitely many colours. Then the family \((1/\ell)\), indexed by the odd cycle lengths \(\ell\) of \(G\) (the odd numbers \(\ell\) such that \(G\) contains a cycle of length \(\ell\)), is not summable; that is, \(\sum_\ell 1/\ell = \infty\).

def conjecture : Prop :=
  ∀ {V : Type*} (G : SimpleGraph V), G.chromaticNumber = ⊤ →
    ¬ Summable (fun (a : G.oddCycleLengths) ↦ 1 / (a : ℝ))
Uses 1 · Used by 1
Statement usesOdd cycle lengths
Used byResolution of the Erdős–Hajnal odd cycle problem (Liu–Montgomery)

TheoremResolution of the Erdős–Hajnal odd cycle problem (Liu–Montgomery)#●ready to prove

Let \(G\) be a graph on an arbitrary vertex set that has no proper colouring with finitely many colours. Then the family \((1/\ell)\), indexed by the odd cycle lengths \(\ell\) of \(G\) (the odd numbers \(\ell\) such that \(G\) contains a cycle of length \(\ell\)), is not summable; that is, \(\sum_\ell 1/\ell = \infty\).

public theorem_wanted conjecture_holds : conjecture
Sources
  • Hong Liu and Richard Montgomery, A solution to Erdős and Hajnal's odd cycle problem, arXiv:2010.15802 (J. Amer. Math. Soc., doi:10.1090/jams/1018), https://arxiv.org/abs/2010.15802.
Uses 1
Statement usesOdd cycle lengths and infinite chromatic number (Erdős Problem 57)

DefinitionStatement of Erdős Problem 63#✓fully proved

The proposition that every simple graph \(G\) with infinite chromatic number has cycles of length \(2^n\) for infinitely many \(n\): for every natural number \(N\) there is some \(n \ge N\) such that \(G\) contains a cycle of length \(2^n\).

def conjecture : Prop :=
  ∀ {V : Type*} (G : SimpleGraph V), G.chromaticNumber = ⊤ →
    ∀ N : ℕ, ∃ n ≥ N, 2 ^ n ∈ G.cycleLengths
Uses 1 · Used by 1
Statement usesCycle lengths
Used byErdős Problem 63 (Liu–Montgomery)

TheoremErdős Problem 63 (Liu–Montgomery)#●ready to prove

Every simple graph \(G\) with infinite chromatic number has cycles of length \(2^n\) for infinitely many \(n\): for every natural number \(N\) there is some \(n \ge N\) such that \(G\) contains a cycle of length \(2^n\).

public theorem_wanted conjecture_holds : conjecture
Sources
  • Liu–Montgomery [LiMo20], per erdosproblems.com/63, https://www.erdosproblems.com/63.
Uses 1
Statement usesStatement of Erdős Problem 63
3 fully proved3 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.