مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

video

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

sound

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Persian Version

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

View:

235
مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Download:

93
مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Cites:

Information Journal Paper

Title

SIZE RAMSEY NUMBER OF BIPARTITE GRAPHS AND BIPARTITE RAMANUJAN GRAPHS

Pages

  45-51

Abstract

 Given a graph G, a graph F is said to be Ramsey for G if in every edge coloring of F with two colors, there exists a monochromatic copy of G. The minimum number of edges of a graph F which is Ramsey for G is called the size-Ramsey number of G and is denoted by ^r(G). In 1983, Beck gave a linear upper bound (in terms of n) for ^r(Pn), where Pn is a path on n vertices, giving a positive answer to a question of Erd}os. After that, different approaches were attempted by several authors to reduce the upper bound for ^r(Pn) for sufficiently large n and most of these approaches are based on the classic models of random graphs. Also, Haxell and Kohayakama in 1994 proved that the size Ramsey number of the cycle Cn is linear in terms n, however the Szemeredi's regularity lemma is used in their proof and so no speci c constant coefficient is provided. Here, we provide a method to obtain an upper bound for the size Ramsey number of a graph using good expander graphs such as Ramanujan graphs. In particular, we give an alternative proof for the linearity of the size Ramsey number of paths and cycles. Our method has two privileges in compare to the previous ones. Firstly, it proves the upper bound for every positive integer n in comparison to the random graph methods which needs n to be sufficiently large. Also, due to the recent explicit constructions for bipartite Ramanujan graphs by Marcus, Spielman and Srivastava, we can constructively nd the graphs with small sizes which are Ramsey for a given graph. We also obtain some results about the bipartite Ramsey numbers.

Multimedia

  • No record.

    • Cites

  • No record.

    • References

  • No record.

    • Cite

    APA: Copy

    JAVADI, R., & KHOEINI, F.. (2019). SIZE RAMSEY NUMBER OF BIPARTITE GRAPHS AND BIPARTITE RAMANUJAN GRAPHS. TRANSACTIONS ON COMBINATORICS, 8(2), 45-51. SID. https://sid.ir/paper/724413/en

    Vancouver: Copy

    JAVADI R., KHOEINI F.. SIZE RAMSEY NUMBER OF BIPARTITE GRAPHS AND BIPARTITE RAMANUJAN GRAPHS. TRANSACTIONS ON COMBINATORICS[Internet]. 2019;8(2):45-51. Available from: https://sid.ir/paper/724413/en

    IEEE: Copy

    R. JAVADI, and F. KHOEINI, “SIZE RAMSEY NUMBER OF BIPARTITE GRAPHS AND BIPARTITE RAMANUJAN GRAPHS,” TRANSACTIONS ON COMBINATORICS, vol. 8, no. 2, pp. 45–51, 2019, [Online]. Available: https://sid.ir/paper/724413/en

    Related Journal Papers

  • No record.

    • Related Seminar Papers

  • No record.

    • Related Plans

  • No record.

    • Recommended Workshops






    Move to top
    email sharing button
    telegram sharing button
    whatsapp sharing button
    linkedin sharing button
    twitter sharing button
    email sharing button
    email sharing button
    sharethis sharing button