Some Extremal Problems In Extremal Combinatorics

Combinatorial mathematics focuses on the existence,counting and construction of configurations(or arrangements)that satisfy certain conditions.It includes algebraic combinatorics,extremal combinatorics,enumerative combinatorics,graph theory,combinatorial design,combinatorial optimization and other fields.As an important branch of combinatorics,extremal combinatorics has important applica-tions in many fields,such as computer science,cryptography,coding theory and experimental design,etc.The extremal problem in extremal combinatorics has always been a hot research field.Especially with the rapid development of computers,the application of machine proof makes the problems of extremal combinatorics developing rapidly.In recent years,the research results about the extremal combinatorics emerge in an endless stream,which greatly enriches the combinatorial theory.The methods commonly used to solve the problems of extremal combinatorics include contradiction,recursive construction,equivalence transformation,inductive conjecture,algebraic methods(including cyclic groups,permutation groups,isomorphisms,homomorphisms),and so on.In this paper,we mainly research three types of extremal problems in extremal combinatorics.Firstly,we mainly study the problem of distance set in Euclidean space.Secondly,we mainly study the construction of the largest points set without forming right angles about square lattice points in the plane.Third,we mainly study the problem of the construction and enumeration of extremal 1-Sperner hypergraph achieving the upper bound.The full thesis is divided into five chapters.In the first chapter,we first introduce the research background,the research overview and the basic concepts in this article,and give some important results known in extremal combinatorics.In the second chapter,we first introduce the basic concepts of distance sets,and give a new proof of 1-distance sets by using the method of algebraic constraints.Meanwhile,we prove the s-distance sets by employing some conclusions of the generator function in combinatorics.In the third chapter,we first discuss the source of the problem and the research ideas about the construction of the largest points set without forming right angles about square lattice points in the plane.Secondly,we give the construction and enumeration of the maximum points set without forming right angles in the m ×n square lattice points.Finally,we study the construction and enumeration of the maximum points set connecting the origin and without forming right angle about n × n and m × n square lattice points in the plane.In the fourth chapter,we first introduce some important conclusions about 1-Sperner hypergraph.Then,we research the problem of the construction and enumeration of extremal 1-Sperner hypergraph achieving the upper bound.Finally,we give the construction and enumeration of extremal 1-Sperner hypergraph achieving the lower bound in the case of fewer vertices.In the fifth chapter,we first summarize the research contents of this article,then give some further research prospects.