Studies On Turan Type Problems

The Turán type problems are the central of extremal graph theory,which study the maximum possible number of edges under given conditions(without a specific subgraph).One of the most fundamental and earliest researched subgraphs is the 4-cycle.The study of 4-cycle has an important enlightening effect on the development of Turán type problems,especially the degenerate cases.This thesis mainly focuses on the extremal problems of 4-cycles,especially two famous conjectures:a conjecture of Erd(?)s from 1970s which asserts that ex(n,C4)=1/2n3/2+1/4n+o(n);a longstanding conjecture of Erd(?)s and Simonovits on the number of C4 which states that every n-vertex graph with ex(n,C4)+1 edges contains at least(1+o(1))(?)copies of C4,and this is one of the favourite problems of Erdos.We will solve them as follows.In Chapter 1,we introduce the notion commonly used in the study of graph theory and finite geometry.Then we talk about the background of 4-cycles and present our main results.In Chapter 2,we obtain some new upper bounds on ex(n,C4).This leads to an asymptotically optimal bound on ex(n,C4)for a board range of integers n as well as a disproof of a conjecture of Erd(?)s on ex(n,C4).In Chapter 3,we present two extremal results on 4-cycles.Let q be a large even integer.First we prove that every(q2+q+1)-vertex C4-free graph with more than 1/2q(q+1)2-0.2q edges must be a spanning subgraph of a unique polarity graph.This implies a stability refinement of a special case of the seminal work of Furedi on the extremal number of C4.Second we prove that every(q2+q+1)-vertex graph with 1/2q(q+1)2 +1 edges contains at least q-1 copies of C4,where we also characterize the extremal graphs.This confirms infinitely many cases of a longstanding conjecture of Erd(?)s and Simonovits on the number of C4.In Chapter 4,more extremal results on 4-cycles will be given.First we obtain that an extremal C4-free graph is an induced subgraph of an orthogonal polarity graph when the size of them are close.Second for a large integer q=4k,we determine the value of ex(q2+q+2,C4)and get many different extremal graphs.This leads to infinitely many(q2+q+2)-vertex and(ex(q2+q+2,C4)+1)-edge graphs with only one copy of C4,which disproves a conjecture of Erd(?)s and Simonovits.In Chapter 5,we give some results on ex(n,{C3,C4}).And in Chapter 6,we present some of our research on other problems.I will discuss the plan in the near future to conclude this thesis.