14601

1382 دكتري

دكتري

رياضي

اصفهان : دانشگاه صنعتي اصفهان

1398

ده، [79]، 4ص.

غلامرضا اميدي، رامين جوادي

بهناز عمومي

واژه نامه

بهروز طايفه رضايي، عليرضا عبدالهي، صفيه محمودي

1398/02/17

كتابنامه

رياضي

رياضي

1398/02/18

2531682

The Size Ramsey Numbers of sparse graphs Farideh Khoeini Doctor of Philosophy Thesis Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 Iran Supervisor Dr Gholamreza OmidiDr Ramin Javadi Advisor Dr Behnaz Omoomi Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 IranAbstractFor given graphs G1 G2 the Ramsey number r G1 G2 is the smallest positive integer n suchthat if the edges of the complete graph Kn are partitioned into two disjoint color classes givingtwo subgraphs H1 H2 then at least one Hi has a subgraph isomorphic to Gi Size Ramseynumber r G1 G2 is the smallest positive integer m such that if the edges of the graph H with m edges are partitioned into two disjoint color classes giving two graphs H1 H2 thenat least one Hi has a subgraph isomorphic to Gi for 1 i 2 This thesis deals with Ramsey numbers and size Ramsey numbers of sparse graphs Toprovide suitable upper bounds for size Ramsey numbers random graphs random regulargraphs and random bipartite graphs play important roles By nding appropriate randomgraphs and random regular graphs we can nd some linear upper bounds for size Ramseynumbers of sparse graphs especially paths and cycles In this thesis we rst focus on the size Ramsey numbers of F and H where F C cn is the family of cycles of length at most cn and H Pn Using similar techniques we alsostudy r Cn Pn which was investigated previously only by using the regularity method In particular we express various linear upper bounds for the size Ramsey numbers of cycles Dudek et al 4 proved that for su ciently large n r Pn 137n Their proof uses a simple probabilistic technique In fact they used random graphs to show that there exist graphswith linear number of edges and good Ramsey type properties Then in 2017 Dudek et al 5 gave another proof for size Ramsey number of paths and proved that for su ciently large n r Pn 74n They used random regular graphs instead of random graphs for their recent proof These proofs are probabilistic but they did not use the regularity lemma Computing size Ramsey numbers for cycles is important as well The standard techniquesfor proving a linear bound for paths without use of the regularity lemma would not havesu ced to prove a linear bound for cycles The linearity of the size Ramsey number of cycles has already been proved by Haxell Ko hayakawa and Luczak 8 actually they proved that the induced size Ramsey number of Cnis linear in n by using of the regularity lemma In this thesis we show that the r color size Ramsey number of a cycle of order n is linear 1

غلامرضا اميدي، رامين جوادي

بهناز عمومي

بهروز طايفه رضايي، عليرضا عبدالهي، صفيه محمودي