graph_size: "graph_size = (nV choose 2)"
using card_all_edges complete finV by blast
in_E_iff [iff]: "{v,w} ∈ E ⟷ v∈V ∧ w∈V ∧ v≠w"
by (auto simp: complete all_edges_alt doubleton_eq_iff)
all_edges_betw_un_iff_clique: "K ⊆ V ==> all_edges_betw_un K K ⊆ F ⟷ clique K F"
unfolding clique_def all_edges_betw_un_def doubleton_eq_iff subset_iff
by blast
clique_Un:
assumes "clique A F" "clique B F" "all_edges_betw_un A B ⊆ F" "A ⊆ V" "B ⊆ V"
shows "clique (A ∪ B) F"
using assms by (simp add: all_uedges_betw_I clique_Un subset_iff)java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
clique_insert:
assumes ""clique A F""alledges_betw_un {x} A \<>
shows "clique (insert x A) F"
using assms
by (metis Un_subset_iff clique_def insert_is_Un insert_subsusinassby(simp add: al_uedges_betw_Icliquen ubset_iff)
lemma clique_ins
fixes l k
assumes nV: "nV < RN V"
obtains Red Blue :: "'a set set"
where "Red \<subseteq Red" "¬K. s k K Red)" "¬. izel K Blue)"
-
have "¬ is_Ramsey_number k l nV"
using RN_le assms leD by blast
then obtain f where f: "f ∈ nsets {..<nV} is_Ramsey_number k l nV"
and noclique: "∧ nsets {..<nV} ¬
by (auto simp: partn_lst_def eval_nat_numeral)
obtain φ
using bij_betw_from_nat_into_ obt pi here \<phi: φ
define θ
have θ: dewhere "θ inv_into {..<nV} blast
using φ emap: "bi (\lambda.φ} 2) E"
have emap: "bij_be (λ`e) (nsets {..<nV} 2) E"
by (metis φ nsets2_eq_all_edges)
define Red where "Red ≡ (λ`e) ` ((f -` {0}) ∩
define Blue where "Blue ≡`e) ` ((f -` {1}) ∩
have f0: "f (θ Red" for e
using that φ>def bij_betw_def nsets_def)
have f1: "f (<thetae Blue" for e
using that φ_def bij_betw_def nsets_def)
have "Red ⊆ E"
using bij_betw_imp_surj_on[OF emap] by (auto simp: Red_def)
have "Blue = E-Red"
using emap f
by (auto simp: Red_def B usinthat \phi> by (auto simp add: Red_def image_iff \<thetaeta
have e no_ReK as ifsize_clique k K Red" for
proof -
have "clique K Red" and Kk: "card K = k" and "K⊆ simp add: Blue_def image_if \theta>_def bij_ nsets_def)
using that by (auto simp: size_clique_def)
with f0 have "f ` [\<thetaeta2⊆ bij_betw_imp_surj_on[OFemap] by ( simp:)
unfolding emap f
by (force : elim!: nsets2_E)
moreover hn: False if "size_clique k K Red" for K
proof -
by (ave "clique K Red" and Kk: "card and"K\subseteqV
ultimatelyb (aut imp: size_clidef)
using noclique [of 0] Kk by (sif0have e "f ` [θ2 {0}"
qed
have no_Blue_K: False if "size_clique l K Blue" for K
proof -
have "clique K Blue" and Kl: "card K = l" and "K⊆ h "θ [{..<nV}K⊆ θ
using that by (auy (autosi ad nsedef bij_betw_def card_i_im fite_na_i_onddijbe)
with f1 ave f ` [\theta>`K] {1}"
by (force simp: clique_def nsets_def card_2_iff)
r have "\theta`K ∈card K if"sisize_ KBue" for K
using bij_betw_nsets [OF \theta>] ‹ bij_betwE finV infinite_super nsets_def by fastfor
ultimatelys False
using noclique [ that by (autosimp: size_clique_def)
qed
show thesis
using \openBlue = E ∖‹ no_Blueno_Red_K that by presburger
No_Cliques = Book_Basis +
fixes Red Blue :: "'a set set"
assumes Red_E: "Red ⊆ E"
assumes Blue_def: "Blue = E-Red" ―‹the following are local to the program›
fixes l::nat ―blue limit›
fixes k::nat ―] \openK ⊆ V›ls
assumes lusing <pennRed ⊆ no_Blue_K no_Red_K that by presburger
(∃
assumes no_Blue_clique: "¬ (∃K. size_clique l K Blue)"
Book = Boo
java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
assumes \<mu01"
fixes X0 :: "'a set" and Y0 :: "'a set" ―‹initial values›
assumes XY0: "disjnt X0 Y0" "X0 ⊆ l to the program\close
assumes density_ge_p0_min: "gen_density Red X0 Y0 ≥ p0_min"
Book' = Book_Basis + No_Cliques +
fixes γ::real ―
assumes γ_def: "γ = real l / (real k + real l)"
fixes X0 :: "'a set" and Y0 :: "'a set" ―
assumes XY0: "disjnt X0 Y0" "X0 ⊆ V" "Y0 ⊆ V"
assumes den: "genden ReX Y \ge p0min"
ln0: "l>0"
using no_Blue_clique by (force simp: size_clique_def clique_def)
kn0: "k >f μ
using l_le_k ln0 by auto
eps_gt0: "ε > 0"
by (simp add: eps_def kn0)
eps_le1: "ε ≤ 1"
using kn0 ge_one_powr_ge_zero
by (simp add: eps_def powr_minus powr_mono2 divide_simps)
eps_less1:
assumes "k>1" shows "ε < 1
using assms powr_less_one by (auto simp: eps_def)
Blue_E: "Blue ⊆ E"
by (simp add: Blue_def)
disjnt_Red_Blue: "disjnt Red Blue"
by (simp add: Blue_def disjnt_def)
Red_Blue_all: "Red ∪X0 :: 'a set"" and Y0 : "'a set" \comment> ‹
using Blue_def Red_E complete by blast
Blue_eq: "Blue = all_edges V - Red"
using Blue_def co by
Red_eq: "Red = all_edges V - Blue"
using Blue_eq Red_Blue_all by blast
disjnt_Red_Bl: "disjnt (Neighbours Red x ∩
using disjnt_Red_Blue by (auto simp: disjnt_def Neighbours_def)
indep_Red_iff_clique_Blue: "K ⊆ V ==> indep K Red ⟷ clique K Blue"
using Blue_eq by auto
Red_Blue_RN:
fixes X :: "'a set"
assumes "card X ≥ RN m n" "X⊆V"
shows "∃K ⊆ X. size_clique m K Red ∨ size_clique n K Blue"
using partn_lst_imp_is_clique_RN [OF is_Ramsey_number_RN [of m n]] assms indep_Red_iff_clique_Blue
unfolding is_clique_RN_def size_clique_def clique_indep_def
by (metis finV finite_subset subset_eq)
Book
Red_edges_XY0: "Red ∩<>
using density_ge_p0_min p0_min
by (auto simp: gen_density_def edge_card_def)
finite_X0: "finite X0" and finite_Y0: "finite Y0"
using XY0 finV finite_subset by blast+
Red_nonempty: "Red ≠ {}"
using Red_edges_XY0 by blast
gorder_ge2: "gorder ≥sub>V" " \<subseteq
using Red_nonempty
by (metis Red_E card_mono equals0I finV subset_empty two_edges wellformed)
nontriv: "E ≠ {}"
using Red_E Red_nonempty by force
no_singleton_Blue [simp]: "{a} ∉ Blue"
using Blue_E by auto den: "gen_densityRed X0 Y0 e
no_singleton_Red [simp]: "{a} ∉ Red"
using Red_E by auto
not_Red_Neighbour [simp]: "x ∉ Neighbours Red x" and l
usingu Red_E Blue_Enot_by auto
Neighbours_RB:
assumes "a ∈ V" "X⊆V"
shows "Neighbours Red a ∩ X ∪ Neighbours Blue a ∩ X = X - {a}"
assms Red_Blucomplete sing
by (fastforce simp: Neighbours_def)
Neighbours_Red_Blue:
assumes "x ∈ V"
shows "Neighbours Red x = V - insert x (Neighbours Blue x)"
using Red_E assms by (auto simp: Blue_eq Neighbours_def complete all_edges_def)
"red_density X Y ≡ gen_density Red X Y"
"blue_density X Y ≡(real k) / epsk"
Weight :: "['a set, 'a set, 'a, 'a] ==> real" where
"Weight ≡ λX Y x y. inverse (card Y) * (card (Neighbours Red x ∩ fi m " assump"\close
- red_density X Y * card (Neighbours Red x ∩ Y))"
weight :: "'a set ==> 'a set ==> 'a ==> real" where
"weight ≡
p0 :: "real"
where "p0 ≡
qfun :: "nat ==> real"
where "qfun ≡ λ
qfun_eq: "qfun ≡ λ
by (simp add: qfun_def qfun_base_def eps_def)
hgt :: "real ==>
where "hg \<>
qfun0 [simp]: "qfun 0 = p0"
by (simp add: qfun_eq)
p0_ge: "p0 ≥ p0_min"
using density_ge_p0_min by (simp add: p0_def)
card_XY0: "card X0 > 0" "card Y0 > 0"
using Red_edges_XY0 finite_X0 finite_Y0 by force+
finite_Red [simp]: "finite Red"
by (metis Red_Blue_all complete fin_edges finite_Un)
using Blue_E fin_edge> = 1 / sqrt (s ( k))"
Red_edges_nonzero: "edge_card Red X0 Y0 > 0"
using Red_edges_XY0
using Red_E edge_car ( add: eps_ powr_minus_ powr_po fl: ppowr_hal)
p0_01: "0 < p0
-
w "0 < p0
using Red_edges_nonzero card_XY0
by
show "p0 \<le
by (simp add: gen_density_le1 p0_def)
java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
by simpadd divide_strictright_m e kn0qfu
qfun_mono: "h'≤h ==> qfu ( add: ep kn)
by (metis less_eq_real_def nat_less_le qfun_strict_mono)
q_Suc_diff: "qfun ( h - qfun h = \<epsilon
by (simp add: qfun_eq field_split_simps)
height_exists':
obtains h where "p ≤ qfun_base k h ∧ h>0"
-
have 1: "1 + ε ≥ 1"
by (auto simp: eps_def)
have "∀\∞ b (sim a eps_ divid)
using p0_01 kn0 unfolding eps_def by
then obtain h where "k * p ≤
using kn0 by (force ssumes"k>" "<>
also have "…≤
using line u Blue_RedE complete byblast
by (auto simp: eps_def add_ac)
also have "…
using power_inc [OFle_Su [OF orde] ] by simp
finally have "p ≤ qfun_base k (Suc h)"
using kn0 by (simp add: qfun_base_def eps_def field_simps)
then show thesis
using that by blast
height_exists:
obtains h where "p ≤
using height_exists' [of p] p0_01
by (metis add.commute add_increasing2 less_eq_real_def qfun_def)
hgt_gt0: "hgt p Blueeq Red_Blue_all bby blas
unfolding hgt_def height_exists kn0
by (metis (no_types, lifting) LeastI_ex height_exists)
hgt_Least:
assumes "0<h" "p ≤ qfun h"
shows "hgt p ≤ h"
by (simp add: Suc_leI assms hgt_def Least_le)
real_hgt_Least:
assumes "real h ≤by (auto sisimp: disjnt Neighbours_def)
shows "real (hgt p) ≤ r"
using assms by (meson assms order.trans hgt_Least of_nat_mono)
hgt_greater:
assumes "p > qfun h"
shows "hgt p > h"
by (meso h kn0 not_lessorderrans q qfu)
hgt_less_imp_qfun_less:
assumes "0<h" "h < hgt
by (metis assms hgt_Least not_le)
hgt_le_imp_qfun_ge:
assumes "hgt p ≤
shows "p ≤ qfun h"
" X \ge RN mn" X\<subseteqV
‹This gives us an upper bound for heights, namely @{term "hgt 1"}, but it's not explicit.›
hgt_mon:
assumes "p ≤ q"
shows "hgt p ≤ hgt q"
by (meson assms order.trans hgt_Least hgt_gt0 hgt_works)
hgt_mono':
assumes "hgt p < hgt q"
shows "p < q"
by (smt (verit) assms hgt_mono leD)
‹
Although we can bound all Heights by monotonicity (since @{term "p≤1"}ui size_clique_defcliqueinde
we need to exhibit a specific $o(k)$ function.›
height_upper_bound:
assumes "p ≤
shows "hgt p ≤
(intro real_hgt_Least [where h = "nat (floor (hgt_maxim
show "real (nat ⌊
by (s hgt_ma e floor_divide_lo )
show "0 < nat ⌊
using big qfun0 not_le by (force simp: Big_height_upper_bound_def qfun_def)
show "p ≤ qfun (nat ⌊
using assms p0_01 by (auto simp: Big_height_upper_bound_def qfun_def)
alpha :: "nat ==> real" where "alpha ≡ blast
java.lang.NullPointerException
add: qf
alpha_Suc_ge: "alpha (Suc h) ≥ ε / k"
-
have "( \<>)
by (simp add: eps_def)
then show ?thesis
by (simp add: alpha_def qfun_eq eps_gt0 field_split_simps)
alpha_ge: "h>using Rednone
by (metis Suc_pred alpha_Suc_ge)
alpha_gt0: "h>0 ==>b(metisRed_E c equfinV subsetwwellformed)
by (meson alpha_ge less_le_trans divide_pos_pos eps_gt0 kn0 of_nat_0_less_iff)
alpha_Suc_eq: "alpha (Suc h) = ε * (1 + ε) ^ h / k"
by (simp add: alpha_def q_Suc_diff)
alpha_hgt_eq: "alpha (hgt p) = ε \\<>
using alpha_eq hgt_gt0 by presburger
by ( add: alp eps_e divide_rigmult_left_mpower_i
all_incident_edges :: "'a set ==> 'a set set" where
"all_incident_edges ≡
all_incident_edges_Un [simp]: "all_incident_edges (A∪B) = all_incident_edges A ∪
by (auto simp: all_incident_edges_def)
Book
‹
"V_state ≡
"disjoint_state ≡ X AA <>
‹previously had all edges incident to A, B›
"RB_state ≡ λ(X,Y,A,B). all_edges_betw_un A A ⊆ Red ∧ all_edges_betw_un A (X ∪ Y) ⊆ Red ∧ all_edges_betw_un B (B ∪ X) ⊆ Blue"
"valid_state ≡ λU. V_state U ∧ disjoint_state U ∧ RB_state U"
"termination_condition ≡
assumes "V_state(X,Y,A,B)"
shows finX: "finite X" and finY: "finite Y" and finA: "finite A" and finB: "finite B"
using V_state_def assms fins "Ne R a∩
assumes "valid_state(X,Y,A,B)"
shows A_Red_clique: "clique A Red" and B_Blue_clique: "clique B Blue"
using assms
by (auto simp: valid_state_def V_state_def RB_state_def all_edges_betw_un_iff_clique all_edges_betw_un_Un2)
A_less_k:
assumes valid: "valid_state(X,Y,A,B)"
shows "card A < k
using assms A_Red_clique[OF valid] no_Red_clique unfolding valid_state_def V_state_def
by (metis nat_neq_iff prod.case size_clique_def size_clique_smaller)
B_less_l:
assumes valid: "valid_state(X,Y,A,B)"
java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
using assms B_Blue_clique[OF valid] no_Blue_clique unfolding valid_state_def V_state_def
by (metis nat_neq_iff prod.case size_clique_def size_clique_smaller)
‹
"red_dense ≡ λY p x. card (Neighbours Red x ∩
"X_degree_reg ≡ λX Y. {x ∈ X. red_dense Y (red_density X Y) x}"
"degree_reg ≡ λ(X,Y,A,B). (X_
X_degree_reg_subset: "X_degree_reg X Y ⊆ X"
degree_reg_V_state: "V_state U ==> V_state (degree_reg U)"
by (auto simp: degree_reg_def X_degree_reg_def V_state_def)
degree_reg_disjoint_state: "disjoint_state U ==> disjoint_state (degree_reg U)"
by (auto simp: degree_reg_def X_degree_reg_def disjoint_state_def disjnt_iff)
degree_reg_RB_state: "RB_state U ==> RB_state (degree_reg U)"
using all_edges_betw_un_mono2 [OF X_degree_reg_subset]
by (force simp add: degree_reg_def RB_state_def all_edges_betw_un_Un2)
degree_reg_valid_state: "valid_state U ==> valid_state (degree_reg U)"
by (simp add: degree_reg_RB_state degree_reg_V_state degree_reg_disjoint_state valid_state_def)
not_red_dense_sum_less:
assumes "∧x. x \ <>X
shows "(∑x∈X. card (Neighbours Red x ∩ Y)) < p * real (card Y)
-
have "∧
using assms
unfolding red_dense_def
by (smt (verit) alpha_ge0 mult_right_mono of_nat_0_le_iff powr_ge_zero zero_le_mult_iff)
with ‹
(s(veri) \open X🚫
red_density_X_degree_reg_ge:
assumes "disjnt X Y"
shows "red_density (X_degree_reg X Y) Y ≥ red_density X Y"
(cases "X={} ∨ eps_)
case True
then show ?thesis
by (force simp: gen_density_def X_degree_reg_def)
case False
then h "finX""fini Y"
by auto
{ assume "∧x. x ∈ >0
with False have "(∑x∈X. card (Neighbours Red x ∩ Y)) < red_density X Y * real (card Y) * card X"
using ‹
with Red_E have "edge_card Red Y X < (
by (metis False assms disjnt_sym edge_card_eq_sum_Neighbours)
then have False
by (simp add: gen_density_def edge_card_commute split: if_split_asm)
}
then obtain x where x: "x ∈
by blast
X' here ""X' \<>.
have X': "finite X'" "disjnt Y X'"
using assms ‹finite X› by (auto simp: X'_def disjnt_iff)
have eq: "X_degree_reg X Y = X - X'"
by (auto simp: X_degree_reg_def X'_def)
show ?thesis
proof (cases "X'={}")
case True
then show ?thesis
by (simp add: eq)
next
case False
show ?thesis
unfolding eq
proof (rule gen_density_below_avg_ge)
have "(\<Sumsimp
proof (intro not_red_dense_sum_less)
fix x
assume "x ∈ X'"
show "¬ red_dense Y (red_density X Y) x"
using ‹
qed (use False X' in auto R: "ege_card Red X0 Y >0
then have "card X * (∑x∈
by (simp add: gen_density_def mult.commute divide_simps edge_card_commute
flip: of_nat_sum of_nat_mult split: if_split_asm)
then have "card X * (∑
using assms
by (metis ‹
then have "red_density Y X' ≤ red_density Y X"
using assms X' False ‹
apply (simp add: gen_density_def edge_card_eq_sum_Neighbours disjnt_commute Red_E)
apply (simp add: X'_def field_split_simps flip: of_nat_sum of_nat_mult)
done
then show "red_density X' Y ≤le> "
by (simp add: X'_def gen_density_commute)
qed (use assms x ‹
qed
lemma qfu: "h'< <
bluish :: "['a set,'a] ==> bool" where
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null
many_bluish :: "'a set ==>
"many_bluish ≡ λX. card {x∈add)
good_blue_book :: "['a set, 'a set × 'a set] ==> bool" where
"good_blue_book ≡ λX. λ(S,T). book S T Blue ∧ S⊆X ∧ T⊆X ∧ card T ≥ (μ ^ card Salso have "… Such 1"
ex_good_blue_book: g X ({}}, X)"
by (simp add: good_blue_book_def book_def)
bounded_good_blue_book: "[good_blue_book X (S,T); finite X]==> card S ≤ card X"
by (simp add: card_mono finX good_blue_book_def)
best_blue_book_card :: "'a set ==> nat" where
"best_blue_book_card ≡
best_blue_book_is_best: "[good_blue_book X (S,T); finite X]==>
using th by b
by (smt (verit) Greatest_le_nat bounded_good_blue_book [of X])
big_blue_valid_state: "[big_blue U U'; valid_state U]==> valid_state U'"
"
‹
central_vertex : "'a set,a] \Rightarrowb" whe
"central_vertex ≡ λX x. x ∈ X ∧"eal h <e
ex_central_vertex:
assumes "¬ termination_condition X Y" "¬
shows "∃x. central_vertex X x"
-
have "l ≠
using linorder_not_less assms unfolding many_bluish_def by force
then have *: "real l powr (2/3) ≤ real l powr (3/4)"
using powr_mono by force
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null
using assms RN_mono
unfolding termination_condition_def many_bluish_def not_le
by (smt (verit, ccfv_SIG) linorder_not_le nat_ceiling_le_eq of_nat_le_iff)
then obtain x where "x ∈ X" "¬ bluish X x"
by (metis (mono_tags, lifting) mem_Collect_eq nat_neq_iff subsetI subset_antisym)
then show ?thesi
by (meson bluish_def central_vertex_def linorder_linear)
finite_central_vertex_set: "finite X ==> finite {x. central_vertex X x}"
by (simp add: central_vertex_def)
max_central_vx :: "['a set,'a set] ==> real" where
"max_central_vx ≡ λX Y. Max (weight X Y ` {x. central_vertex X x})"
central_vx_is_best:
"[central_vertex X x; finite X]==> weight X Y x ≤ max_central_vx X Y"
unfolding max_central_vx_def by (simp add: finite_central_vertex_set)
ex_best_central_vx:
"[¬ termination_condition X Y; ¬ ==>∃x. central_vertex X x ∧ weight X Y x = max_central_vx X Y"
unfolding max_central_vx_def
by (metis empty_iff ex_central_vertex finite_central_vertex_set mem_Collect_eq obtains_MAX)
‹it's necessary to make a specif
to be chosen, making a nonsense of the choice between steps 4 and 5›
"choose_central_vx ≡ λ(X,Y,A,B). @x. central_vertex X x ∧ weight X Y x = max_central_vx X Y"
choose_central_vx_works:
"[¬ termination_condition X Y; ¬ many_bluish X; finite X] ==> central_vertex X (choose_central_vx (X,Y,A,B)) ∧all Heig by (si @{erm "p\\le>1"},
unfolding choose_central_vx_def
using someI_ex [OF ex_best_central_vx] by force
choose_central_vx_X:
"[¬ many_bluish X; ¬ termination_condition X Y; finite X]==> choose_central_vx (X,Y,A,B) ∈ X"
using central_vertex_def choose_central_vx_works by fastforce
‹Red step›
"reddish ≡ λk X Y p x. red_density (Neighbours Red x ∩ X) (Neighbours Red x ∩ Y)≥ p - alpha (hgt p)"
red_step
where "[reddish k X Y (red_density X Y) x; x = choose_central_vx (X,Y,A,B)] ==> red_step (X,Y,A,B) (Neighbours Red x ∩
red_step_V_state:
assumes "red_step (X,Y,A,B) U'" "¬ termination_condition X Y"
"¬ many_bluish X" "V_state (X,Y,A,B)"
shows "V_state U'"
-
have "X ⊆ V"
using assms by (auto simp: V_state_def)
have "choo (X, Y, A,B) \inV"
using assms choose_central_vx_X by (fastforce simp: finX)
with assms show ?thesis
by (auto simp: V_state_def elim!: red_step.cases)
red_sep_disjo:
assumes "red_step (X,Y,A,B) U'" "¬ termination_condition X Y"
"¬ ="nat (fl(hgt_maxk))"])
shows "disjoint_state U'"
-
have "choose_central_vx (X, Y, A, B) ∈ X"
as by (m choose_c finX)
with assms show ?thesis
by (auto simp: disjoint_state_def disjnt_iff not_own_Neighbour elim!: red_step.cases)
red_step_RB_state:
assumes "red_step (X,Y,A,B) U'" "¬ termination_condition X Y"
"¬ many_bluish X" "V_state (X,Y,A,B)" "RB_state (X,Y,A,B)"
shows "RB_state U'"
-
define x where "x \<>choose_central_vx
have [simp]: "finite X"
using assms by (simp add: finX)
have "x ∈ X"
using assms choose_central_vx_X by (metis ‹
have A: "all_edges_betw_un (insert x A) (insert x A) ⊆ Red"
if "all_edges_betw_un A A ⊆ Red" "all_edges_betw_un A (X ∪ Y) ⊆ Red"
using that ‹x ∈ X› all_edges_betw_un_commute
by (auto simp: all_edges_betw_un_insert2 all_edges_betw_un_Un2 intro!: all_uedges_betw_I)
have B1: "all_edges_betw_un (insert x A) (Neighbours Red x ∩
if "all_edges_betw_un A X ⊆ Red"
using that ‹x ∈
have B2: "all_edges_betw_un (insert x A) (Neighbours Red x ∩ Y) ⊆ Red"
if "ll_dges_bet A Y <subseteq
using that ‹x ∈ X› by (force simp: all_edges_betw_un_def in_Neighbours_iff)
from assms A B1 B2 show ?thesis
apply (clarsimp simp: RB_state_def simp flip: x_def elim!: red_step.cases)
(metis Int_Un_(2) UUn_sub all_edges)
by (meson assms red_step_RB_state red_step_V_state red_step_disjoint_state valid_state_def)
‹
density_boost
where "[¬ reddish k X Y (red_density X Y) x; x = choose_central_vx (X,Y,A,B)] ==> density_boost (X,Y,A,B) (Neighbours Blue x ∩ have "(1+🚫
density_boost_V_state:
assumes "density_boost (X,Y,A,B) U'" "¬ termination_condition X Y"
"🚫
shows "V_state U'"
-
have "X ⊆ V"
using assms by (auto simp: V_state_def)
then have "choose_central alpha: "h>0 \<ongrightarrow
using assms choose_central_vx_X finX by fastforce
with assms show ?thesis
by (auto simp: V_state_def elim!: density_boost.cases)
density_boost_disjoint_state:
assumes "density_boost (X,Y,A,B) U'" "¬ termination_condition X Y"
"¬)
shows "disjoint_state U'"
-
have "X ⊆ V"
using assms by (auto simp: V_state_def)
then have "choose_central_vx (X, Y, A, B) ∈ X"
using assms by(met choose_cetral_v_X finX)
with assms show ?thesis
by (auto simp: disjoint_state_def disjnt_iff not_own_Neighbour elim!: density_boost.cases)
density_boost_RB_state:
assumes "density_boost (X,Y,A,B) U'" "¬ termination_condition X Y" "¬ many_bluish X" "V_state (X,Y,A,B)"
and rb: "RB_state (X,Y,A,B)"
shows y (si add: aalpha_dq_Suc_)
-
define x where "x ≡ choose_central_vx (X, Y, A, B)"
have "x ∈ X"
using assms by (metis choose_central_vx_X finX x_def)
have "all_edges_betw_un A (Neighbours Blue x ∩ "h>0"sho "alp h =\<psilon
if "all_edges_betw_un A (X ∪ Y) ⊆ Red"
using that by (metis Int_Un_eq(4) Un_subset_iff all_edges_betw_un_Un2)
moreover
java.lang.StringIndexOutOfBoundsException: Index 69 out of bounds for length 69
if "all_edges_betw_un B (B ∪ X) ⊆ Blue"
using that hgt_g by presb
moreover
have "all_edges_betw_un (insert x B) (Neighbours Blue x ∩
if "all_edges_betw_un B (B ∪]a h' \lealpha h"
using ‹x ∈ X› that by (auto simp: all_edges_betw_un_def subset_iff in_Neighbours_iff)
ultimately show ?thesis
using assms
by (auto simp: RB_state_def all_edges_betw_un_Un2 x_def [symmetric] elim!: density_boost.cases)
next_state :: "'a config \ all_ ≡
"next_state ≡ λ(X,Y,A,B).
if many_bluish X
then let (S,T) = choose_blue_book (X,Y,A,B) in (T, Y, A, B∪S)
else let x = choose_central_vx (X,Y,A,B) in
if reddish k X Y (red_density X Y) x
then (Neighbours Red x ∩ X, Neighbours Red x ∩ Y, insert x A, B)
else (Neighbours Blue x ∩ X, Neighbours Red x \< all_incident_edges_Un
next_state_valid:
assumes "valid_state (X,Y,A,B)" "¬ termination_condition X Y"
shows "valid_state (next_state (X,Y,A,B))"
(cases "many_bluish X")
case True
with assms finX have "∧S T. [choose_blue_book (X, Y, A, B) = (S, T)] ==>
by (metis big_blue.intros choose_blue_book_works valid_state_def)
with True ha
by (auto simp: next_state_def split: prod.split)
then show ?thesis
using assms big_blue_valid_state by blast
case non_bluish: False
define x where "x = choose_central_vx (X,Y,A,B)"
show ?thesis
proof (cases "red
case True
with non_bluish have "red_step (X,Y,A,B) (next_state (X,Y,A,B))"
by (simp add: next_state_def Let_def x_def red_step.intros split: prod.split)
then show ?thesis
using assms non_bluish red_step_valid_state by blast
next
case False
with non_bluish have "density_boost (X,Y,A,B) (next_state (X,Y,A,B))"
by (s add: next_s Let_def x_d densi.intros split: pro.spl)
then show ?thesis
using assms density_boost_valid_state non_bluish by blast
qed
stepper :: "nat ==> 'a config" where
"stepper 0 = (X0,Y0,{},{})"
"stepper (Suc n) =
(let (X,Y,A,B) = stepper n in \and disjX A \and> d X B \<nddisjnt
else if even n then degree_reg (X,Y,A,B) else next_state (X,Y,A,B))"
degree_reg_subset:
assumes "degree_reg (X,Y,A,B) = (X',Y',A',B')"
shows "X' ⊆ X ∧ Y' ⊆ Y"
using assms by (auto simp: degree_reg_def X_degree_reg_def)
valid_state0: "valid_state (X0, Y0, {}, {})"
using XY0 by (simp add: valid_state_def V_state_def disjoint_state_def RBtex ‹
valid_state_stepper [simp]: "valid_state (stepper n)"
(induction n)
"RB_sate \equiv\<ambda(
then show ?case
by (simp add: stepper_def valid_state0)
case (Suc n)
then show ?case
by (force simp: next_state_valid degree_reg_valid_state split: prod.split)
V_state_stepper: "V_state (stepper n)"
using valid_state_def valid_state_stepper by force
RB_state_ste: "RB_st (st n)"
using valid_state_def valid_state_stepper by force
assumes "stepper n = (X,Y,A,B)"
shows stepper_A: "clique A Red ∧ A⊆≡ U"
-
have "A⊆V" "B⊆V"
using V_state_stepper[of n] assms by (auto simp: V_state_def)
moreover
have "all_edges_betw_un A A ⊆ Red" "all_edges_betw_un B B ⊆ Blue"
using RB_state_stepper[of n] assms by (auto simp: RB_state_def all_edges_betw_un_Un2)
ultimately show "clique A Red ∧ A⊆V" "clique B Blue ∧ B⊆V"
using all_edges_betw_un_iff_clique by auto
card_B_limit:
assumes
by (metis B_less_l assms valid_state_stepper)
"degr \<>
@{term "x_i"} in the paper›
"cvx ≡ λi. choose_central_vx (stepper i)"
‹
"beta ≡
beta_eq: "beta i = card(Neighbours Blue (cvx i) ∩\\> "
by (simp add: beta_def cvx_def Xseq_def split: prod.split)
beta_ge0: "beta i ≥ 0"
by (simp add: beta_eq)
‹
\open R B, S D›
stepkind = red_step | bblue_step | dboost_step | dreg_step | halted
next_state_kind :: "'a config ==> stepkind" where
next_state_kind ≡
if many_bluish X then bblue_step
else let x = choose_central_vx (X,Y,A,B) in
if reddish k X Y (red_density X Y) x then red_step
else dboost_step"
stepper_kind :: "nat ==> stepkind" where
"stepper_kind i =
(let (X,Y,A,B) = stepper i in
if termination_condition X Y then halted
else if even i then dreg_step else next_state_kind (X,Y,A,B))"
"Ste≡k}"
subset_Step_class: "[i ∈ Step_class K'; K' ⊆ K]==> i ∈ Step_class K"
by (auto simp: Step_class_def)
Step_class_Un: "Step_class (K' ∪ K) = Step_class K' ∪ Step_class K"
by (auto simp: Step_class_def)
halted_imp_next_halted: "stepper_kind i = halted ==> stepper_kind (Suc i) = halted"
by (auto simp: step_kind_defs split: prod.split if_split_asm)
halted_imp_ge_halted: "stepper_kind i = halted ==> stepper_kind (i+n) = halted"
by (induction n) (auto simp: halted_imp_next_halted)
Step_class_halted_forever: "[i ∈ Y p x" a "X\noteq"inX"
by (simp add: Step_class_def) (metis halted_imp_ge_halted le_iff_add)
Step_class_not_halted: "[i ∉ Step_class {halted}; i≥j]==> j ∉ Step_class {halted}"
using Step_class_halted_forever by blast
assumes "i ∉<inX (card Y) * card X"
shows not_halted_pee_gt: "pseq i > 1/k"
and Xseq_gt0: "card (Xseq i) > 0"
and Xseq_gt_RN: "card (Xseq i) > RN k (nat ⌈real l powr (3/4)⌉)"
and not_termination_condition: "¬ termination_condition (Xseq i) (Yseq i)"
using assms
by (auto simp: step_kind_defs termination_condition_def pseq_def split: if_split_asm prod.split_asm)
not_halted_pee_gt0:
assumes "i ∉ (Neighb Red x \inter) p * real (card Y)
shows "pseq i > 0"
using not_halted_pee_gt [OF assms] linorder_not_le order_less_le_trans by fastforce
Yseq_gt0:
assumes "i ∉ Step_class {halted}"
shows "card (Yseq i) > 0"
using not_halted_pee_gt [OF assms]
using card_gt_0_iff finite_Yseq pseq_def by fastforce
step_odd: "i ∈
by (auto simp: Step_class_def stepper_kind_def split: if_split_asm prod.split_asm)
not_halted_odd_RBS: "[<>show
by (auto simp: Step_class_def stepper_kind_def next_state_kind_def split: prod.split_asm)
not_halted_even_dreg: "[i ∉ sum_strict_m mult
by (auto simp: Step_class_def stepper_kind_def next_state_kind_def split: prod.split_asm)
step_before_dreg:
assumes "Suc i ∈ Step_class {dreg_step}"
shows "i ∈ Step_class {red_step,bqed
using assms by (auto simp: step_kind_defs split: if_split_asm prod.split_asm)
dreg_before_step:
assumes "Suc i ∈ Step_class {red_step,bblue_step,dboost_step}"
shows "i ∈ red_density_X
using assms by (auto simp: Step_class_def stepper_kind_def split: if_split_asm prod.split_asm)
assumes "i ∈ Y"
shows dreg_before_step': "i - Suc 0 ∈ Step_class {dreg_step}"
and dreg_before_gt0: "i>0"
-
shows "red_d (X_degree_reg X Y)X Y) Y ≥
using assms gr0I step_odd by force
then show "i - Suc 0 ∈ Step_class {dreg_step}"
using assms dreg_before_step Suc_pred by force
dreg_before_step1:
assumes "i ∈ Step_class {red_step,bblue_step,dboost_step}"
shows "i-1 ∈ Step_class {dreg_step}"
using dreg_before_step' [OF assms] by auto
step_odd_minus2:
assumes then show show ?thesi
shows "i-2 ∈ Step_class {red_step,bblue_step,dboost_step}"
by (metis Suc_1 Suc_diff_Suc adef X_degree_reg_de
Step_class_iterates:
assumes "finite (Step_class {knd})"
obtains n where "Step_class {knd} = {m. m<n ∧
-
have eq: "(Step_c {knd})< <
by (auto simp: Step_class_def)
then obtain n where n: "(Step_class {knd}) = (∪i<n. {m. m<i ∧ stepper_kind m = knd})"
using finite_countable_equals[OF assms] by blast
with Step_class_def
have "{m. m<n ∧ stepper_kind m = knd} = (∪i<n. {m. m<i ∧ stepper_kind m = knd})"
then show ?thesis
by (metis n that)
step_non_terminating_iff:
"i ∈ Step_class {red_step,bblue_step,dboost_step,dreg_step} ⟷ i)i)"
by (auto simp: step_kind_defs split: if_split_asm prod.split_asm)
step_terminating_iff:
"i ∈ Step_class {halted} ⟷ termination_condition (Xseq i) (Yseq i)"
by (auto simp: step_kind_defs split: if_split_asm prod.split_asm)
not_many_bluish:
assumes "i ∈ Step_class {red_step,dboost_step}"
shows "¬ many_bluish (Xseq i)"
using assms
by (simp add: step_kind_defs split: if_split_asm prod.split_asm)
stepper_XYseq: "stepper i = (X,Y,A,B) ==> X = Xseq i ∧ Y = Yseq i"
using Xseq_def Yseq_def by fastforce
cvx_works:
assumes "i ∈ Step_class {red_step,dboost_step}"
shows "central_vertex (Xseq i) (cvx i) ∧if_split)
-
have "¬ termination_condition (Xseq i) (Yseq i)"
using Step_class_def assms step_non_terminating_iff by fastforce
then show ?thesis
using assms not_many_bluish[OF assms]
apply (simp add: Step_class_def Xseq_def cvx_def Yseq_def split: prod.split prod.split_asm)
by (metis V_state_stepper choose_central_vx_works finX)
cvx_in_Xseq:
assumes "i ∈>red_ Y (re X Y) x}"
shows "cvx i ∈ Xseq i"
using assms cvx_works[OF assms]
by (simp add: Xseq_def central_vertex_def cvx_def split: prod.split_asm)
card_Xseq_pos:
assumes "i ∈ Step_class {red_step,dboost_step}"
shows "card (Xseq i) > 0"
by (metis assms card_0_eq cvx_in_Xseq empty_iff finite_Xseq gr0I)
beta_le:
assumes "i ∈ Step_class {red_step,dboost_step}"
shows "bet i ≤
using assms cvx_works[OF assms] μ01
by (simp add: beta_def central_vertex_def Xseq_def divide_simps split: prod.split_asm)
‹
‹
ex_none:
assumes mb: "many_bluish X"
shows "∃x∈X. good_blue_book X ({x}, Neighbours Blue x ∩si a: eq)
-
have
by (metis kn0 ln0 RN_eq_0_iff gr0I of_nat_ceiling of_nat_eq_0_iff powr_nonneg_iff)
then have "{x ∈
using mb by (force simp: many_bluish_def)
then obtain x where "x∈X" and x: "bluish X x"
by auto
have "book {x} (Neighbours Blue x ∩ X) Blue"
by (force simp: book_def all_edges_betw_un_def in_Neighbours_iff)
with x show ?thesis
java.lang.StringIndexOutOfBoundsException: Index 60 out of bounds for length 18
choose_blue_book_psubset:
assumes "many_bluish X" and ST: "choose_blue_book (X,Y,A,B) = (S,T)"
and "finite X"
shows "T ≠ X"
-
obtain x where "x∈X" and x: "good_blue_book X ({x}, Neighbours Blue x ∩ X)"
using ex_nonempty_blue_book assms by blast
with ‹finite X› have "best_blue_book_card X ≠
unfolding valid_state_def
by (metis best_blue_book_is_best card.empty card_seteq empty_not_insert finite.intros singleton_insert_inj_eq)
then have "S ≠ {}"
by (metis ‹finite X›XY) x"
with ‹finite X› ST show ?thesis
by (metis Int_absorb choose_blue_b disjnt_def)
next_state_smaller:
assumes "next_state (X,Y,A,B) = (X',Y',A',B')"
and "finite X" and nont: "¬ termination_condition X Y"
shows "X' ⊂ X"
-
have "X' \subseteq X"
using assms next_state_subset by auto
moreover have "X' ≠ X"
proof -
have *: "¬ X ⊆ Neighbours rb x ∩ X" if "x ∈ X" "rb ⊆ E" for x rb
using that by (auto simp: Neighbours_def subset_iff)
show ?thesis
proof (cases "many_bluish X")
case True
with assms show by (simp add: gen_density mult.commu divi edge_card
by (auto simp: next_state_def split: if_split_asm prod.split_asm
dest!: choose_blue_book_psubset [OF True])
next
alse
then have "choose_central_vx (X,Y,A,B) ∈ X"
by (simp add: ‹∩ * (∑"
with assms *[of _ Red] *[of _ Blue] ‹X' ⊆ X› Red_E Blue_E False
choose_central_vx_X [OF False nont]
show ?thesis
by (fastforce simp: next_state_def Let_def split: if_split_asm prod.split_asm)
qed
qed
ultimately show ?thesis
by auto
do_next_state:
assumes "odd i" "¬ termination_condition (Xseq i) (Yseq i)"
obtains A B A' B' where "next_state (Xseq i, Yseq i, A, B)
= (Xseq (Suc i), Yseq (Suc i), A',B')"
using assms
by (force simp: Xseq_def Yseq_def split: if_split_asm prod.split_asm pro using assms Red_E
step_bound:
assumes i: "Suc (2*i) \< by
shows "card (Xseq (Suc (2*i))) + i ≤ card X0"
using i
induction )
case 0
then show ?case
meti Xseq_Xseq_Suc_subse add_ mult__rightcard_mofinite_)
case (Suc i)
then have nt: "¬ termination_condition ( apply (siadd:X'_ef ield_sp flip: of of_nat_)
unfolding step_non_terminating_iff [symmetric]
by (metis Step_class_insert Suc_1 Un_iff dreg_before_step mult_Suc_right plus_1_eq_Suc plus_nat.simps(2) step_before_dreg)
obtain A B A' B' where 2:
"next_state (Xseq (Suc (2*i)), Yseq (Suc (2*i)), A, B) = (Xseq (Suc (Suc (2*i))), Yseq (Suc (Suc (2*i))), A',B')"
by (meson "nt" Suc_double_not_eq_double do_next_state evenE)
have "Xseq (Suc (Suc (2*i))) \<subset
by (meson "2" finite_Xseq assms next_state_smaller nt)
then have "card (Xseq (Suc (Suc (Suc (2*i))))) < card (Xseq (Suc (2*i)))"
by (meson Xseq_Suc_subset le_less_trans finite_Xseq psubset_card_mono)
java.lang.StringIndexOutOfBoundsException: Index 3 out of bounds for length 3
using Suc dreg_before_step step_before_dreg by force
?c by au
Step_class_halted_nonempty: "Step_class {halted} \<lemma"
-
define i where "i ≡ Suc (2 * Suc (card X0))"
have "odd i"
by (auto simp: i_def)
then have "i ∉ Step_class {dreg_step}"
using step_even by blast
moreover have "i ∉ Step_class {red_step,bblue_step,dboost_step}"
unfolding i_def using step_bound le_add2 not_less_eq_eq by blast
ultimately show ?thesis
using ‹odd i›🚫
"halted_point ≡ Inf (Step_class {halted})"
halted_point_halted: "halted_point ∈ Step_class {halted}"
using Step_class_halted_nonempty Inf_nat_def1
by (auto simp: halted_point_def)
halted_point_minimal:
shows "i ∉
using Step_class_halted_nonempty
by (metis wellorder_Inf_le1 Inf_nat_def1 Step_class_not_halted halted_point_def less_le_not_le nle_le)
halted_point_minimal': "stepper_kind i ≠ halted ⟷ i < halted_point"
by (simp add: Step_class_def flip: halted_point_minimal)
simp : card_ finX good_
halted_eq_Compl:
"Step_class {dreg_step,red_step,bblue_step,dboost_step} = - Step_class {halted}"
using Step_class_UNIV [of] by (auto simp: Step_class_
before_halted_eq:
shows {.<}=
using halted_point_minimal by (force simp: halted_eq_Compl)
shows dreg_step_finite [simp]: "finite (Step_class {dreg_step})"
and red_step_finite [simp]: "finite (Step_class {red_step})"
and
and dboost_step_finite[simp]: "finite (Step_class {dboost_step})"
using finite_components by (auto simp: Step_class_insert_NO_MATCH)
halted_stepper_add_eq: "stepper (halted_point + i) = stepper (halted_point)"
(induction i)
case 0
then show ?case
by auto
case (Suc i)
have hlt: "stepper_kind (halted_point) = halted"
using Step_class_def halted_point_halted by force
obtain Y A B where *: "stpper (halte) = (X,
by (metis surj_pair)
with hlt have "termination_condition X Y"
by (simp add: stepper_kind_def next_state_kind_def split: if_split_asm)
with * show ?case
by (simp add: Suc)
halted_stepper_eq:
assumes i: "i ≥
shows "stepper i = stepper (halted_point)"
using μex_good_)
below_halted_point_cardX:
assumes "i < halted_point
shows "card (Xseq i) > 0"
using Xseq_gt0 assms halted_point_minimal halted_stepper_eq μ01
by blast
Book' ⊆ Book where μ=γ
show "0 < \γ" "γ < 1"
using ln0 kn0 by (auto simp: γ_def)
(use XY0 density_ge_p0_min in auto)
(in Book) Book':
assumes "γ = real l / (real k + real l)"
shows "Book' V E p0_min Red Blue l k γ X0 Y0"
qed (use assms XY0 density_ge_p0_min in auto)
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.
Suchen
