FormalConjectures/ErdosProblems/1080.lean

GitHub source file

2 declarations, 1 contain sorry, 0 declared as axioms

1. def Erdos1080.IsBipartition IsBipartition G X Y means that X and Y form a bipartition of the vertices of G line 41 source

   Source documentation

   IsBipartition G X Y means that X and Y form a bipartition of the vertices of G.

   standard axioms: Classical.choice, Quot.sound, propext what this means

   Statement uses: SimpleGraph, Set

   Proof uses: And, Disjoint, Eq, Union.union, Set.univ, SimpleGraph.Adj, Iff, Membership.mem

   8 instances, coercions and auxiliary constants left out.

   def IsBipartition {V : Type*} (G : SimpleGraph V) (X Y : Set V) : Prop :=
   …

2. theorem Erdos1080.erdos_1080 Let $G$ be a bipartite graph on $n$ vertices such that one part has $\lfloor n^{2/3}\rfloor$ vertices sorry line 60 source

   Source documentation

   Let $G$ be a bipartite graph on $n$ vertices such that one part has $\lfloor n^{2/3}\rfloor$ vertices. Is there a constant $c>0$ such that if $G$ has at least $cn$ edges then $G$ must contain a $C_6$?

   The answer is no, as shown by De Caen and Székely [DeSz92], who in fact show a stronger result. Let $f(n,m)$ be the maximum number of edges of a bipartite graph between $n$ and $m$ vertices which does not contain either a $C_4$ or $C_6$. A positive answer to this question would then imply $f(n,\lfloor n^{2/3}\rfloor)\ll n$. De Caen and Székely prove $n^{10/9}\gg f(n,\lfloor n^{2/3}\rfloor) \gg n^{58/57+o(1)}$ for $m\sim n^{2/3}$. They also prove more generally that, for $n^{1/2}\leq m\leq n$, $f(n,m) \ll (nm)^{2/3},$ which was also proved by Faudree and Simonovits.

   This was formalized in Lean by Alexeev using Aristotle.

   depends on sorry what this means

   Statement uses: Iff, False, Exists, Real, And, GT.gt, OfNat.ofNat, Fintype, Nonempty, SimpleGraph, Set, Erdos1080.IsBipartition, Eq, Nat, Set.ncard, Nat.floor, HPow.hPow, Fintype.card, HDiv.hDiv, GE.ge and 6 more

   Proof uses: sorryAx, Lean.Name, Bool.false, Lean.Name.num, Lean.Name.str, Lean.Name.anonymous

   46 instances, coercions and auxiliary constants left out.

   Tactic trace: 1 steps

   Open to load the checked before-and-after goal states.

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

   Mentions: c, Erdos1080.IsBipartition