EDP Sciences Journals List
Home Document
Subscriber Authentication Point
Issue RAIRO-Theor. Inf. Appl.
Volume 39, Number 1, January-March 2005
Imre Simon, the tropical computer scientist
Page(s) 191 - 206
DOI 10.1051/ita:2005019

Theoret. Informatics Appl. 39, 191-206 (2005)
DOI: 10.1051/ita:2005019

A note on the Size-Ramsey number of long subdivisions of graphs

Jair Donadelli1, Penny E. Haxell2 and Yoshiharu Kohayakawa3

1  Departamento de Informática, Universidade Federal do Paraná, Centro Politécnico Caixa Postal 19081, 81531-980 Curitiba PR, Brasil;
    e-mail: jair@inf.ufpr.br
2  Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada;
    e-mail: pehaxell@math.uwaterloo.ca
3  Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-090 São Paulo SP, Brasil;
    e-mail: yoshi@ime.usp.br


Abstract
Let  TsH be the graph obtained from a given graph  H by subdividing each edge  s times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321-328], we prove that, for any graph  H, there exist graphs  G with  O(s) edges that are Ramsey with respect to  TsH.


Mathematics Subject Classification. 05C55, 05D40

Key words: The Size-Ramsey number -- Ramsey theory -- expanders -- Ramanujan graphs -- explicit constructions.


© EDP Sciences 2005


What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.