tailieunhanh - Báo cáo tin học: "On the Resilience of Long Cycles in Random Graphshan"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On the Resilience of Long Cycles in Random Graphshan. | On the Resilience of Long Cycles in Random Graphs Domingos Dellamonica Jr Department of Mathematics and Computer Science Emory University 400 Dowman Dr. Atlanta GA 30322 USA ddellam@ Yoshiharu Kohayakaway Instituto de Matemática e Estatistica Universidade de Sao Paulo Rua do Matão 1010 05508-090 Sao Paulo Brazil yoshi@ Martin Marciniszyn Angelika Steger Institute of Theoretical Computer Science ETH Zurich 8092 Zurich Switzerland mmarcini steger @ Submitted Jun 13 2007 Accepted Feb 5 2008 Published Feb 11 2008 Mathematics Subject Classification 05C35 05C38 05C80 Abstract In this paper we determine the local and global resilience of random graphs Gn p p n-1 with respect to the property of containing a cycle of length at least 1 a n. Roughly speaking given a 0 we determine the smallest rg G a with the property that almost surely every subgraph of G Gnp having more than rg G a E G edges contains a cycle of length at least 1 a n global resilience . We also obtain for a 1 2 the smallest rI G a such that any H c G having degH v larger than rl G a degG v for all v 2 V G contains a cycle of length at least 1 a n local resilience . The results above are in fact proved in the more general setting of pseudorandom graphs. Supported by a CAPES-Fulbright scholarship. yPartially supported by FAPESP and CNPq through a Temático-ProNEx project Proc. FApEsP 2003 09925-5 and by CNPq Proc. 306334 2004-6 and 479882 2004-5 . THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R32 1 1 Introduction Problems in extremal graph theory 1 2 usually come in the following form let P be a graph property and ụ a graph parameter determine the least m with the property that any graph G with ụ G m has P and describe the so called extremal graphs that is those G with ụ G m without P. For instance in the case of Turan s theorem P is the property of containing a clique Kt for some given t and ụ G is the number of edges e G in G. As is well known Turan s classical result .