چكيده انگليسي :
The Ramsey Number Of Dense Graph Hamid Jamali Bejoo h jamali@math iut ac ir 2013 Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 Iran Supervisor Dr Gholam Reza Omidi romidi@cc iut ac ir Advisor Dr Behnaz Omoomi bomoomi@cc iut ac ir 2013 MSC 05C15 05C55 Keywords Ramsey number AbstractA graph G is a triple consisting of a vertex set V G an edge set E G and a relation that associateswith each edge two vertices called its endpoints A complete graph is a simple graph whose verticesare pairwise adjacent the complete graph with n vertices is denoted Kn Graphs with a number of G edge roughly quadratic in their number of vertices are usually called dense The number G 2proportion of its potential edge that G actually has is the edge density of G In 1928 the English mathematician Frank Plumpton Ramsey published his paper on a problem offormal logic in which he proved what would become known as Ramsey s Theorem The paper has ledto a large area of combinatorics now known as Ramsey Theory To understand Ramsey numbers and Ramsey s Theorem we must rst understand what is meantby a coloured graph A 2 coloured graph is a graph whose edges have been coloured with 2 di erentcolours The Ramsey number of a simple graph G is the least integer n such that every 2 edge colouring ofKn yields a monochromatic copy of G This number is denoted by R G G or R G That these numbers exist was rst proven by Ramsey and rediscovered independently by Erd s andSzekeres Determining or estimating Ramsey numbers is one of the central problems in combinatorics The most famous question in this eld is that of estimating the Ramsey number R t of thecomplete graph Kt on t vertices Despite some small improvements the standard estimates that 2 t R t 4t have remained largely unchanged for over sixty years A similar question to that wehave been looking at suggested by Erd s is to determine the Ramsey number of a graph G with a
