Research On Some Problems In Extremal Combinatorics

It is well-known that eigenvalues of graphs can be used to describe structural properties and parameters of graphs.The spectral extremal graph problem is an important research topic in extremal graph theory and algebraic graph theory.Letλ（G）be the spectral radius of a graph G.A famous result in extremal spectral graph theory,due to Nosal and Nikiforov,states that if G is a triangle-free graph on n vertices,thenλ（G）≤λ(K_{（?）n/2」,「n/2（?）}),equality holds if and only if G=K_{（?）n/2」,「n/2（?）}.Later,Guiduli,and Nikiforov extended this result to K_r+1-free graphs for every integer r≥2.This is known as the spectral Turán theorem.In 2021,Lin,Ning and Wu proved a refinement on this result for non-bipartite triangle-free graphs.In Chapter 2,for two non-adjacent vertices,by comparing the sums of weights of their neighbors,we provide alternative proofs for the result of Nikiforov and the result of Lin,Ning and Wu.The proof can be viewed as a spectral extension of Zykov’s symmetrization.Importantly,using local changes and switches on edges,our proof can allow us to extend the later result to non-r-partite K_r+1-free graphs.Our result refines the theorem of Nikiforov and it also can be viewed as a spectral version of a theorem of Brouwer.Recently,it is also popular to consider the corresponding spectral extremal problem for graphs with given number of edges,instead of the number of vertices.A theorem of Nosal states that if G is a triangle-free graph with m edges,thenλ（G）≤m^1/2,equality holds if and only if G is a complete bipartite graph.For non-bipartite triangle-free graphs,Lin,Ning and Wu recently proved a generalization by showing thatλ（G）≤（m-1）^1/2,equality holds if and only if m=5 and G=C₅.Moreover,Zhai and Shu presented a further improvement,which states thatλ（G）≤β（m）,whereβ（m）is the largest root of Z（x）=x³-x²-（m-2）x+m-3.In Chapter 3,we present an alternative method for proving the improvement by Zhai and Shu.Furthermore,the method can allow us to give a refinement on the result of Zhai and Shu for non-bipartite graphs without short odd cycles.Letγ（m）be the largest root of L（x）=x⁷-mx⁵+（4m-14）x³-（3m-14）x-m+5.We proved that if G is a{C₃,C₅}-free graph with m edges,and G is non-bipartite,thenλ（G）≤γ（m）,equality holds if and only if G=S₃(K_{2,（m-3）/2}).A graph F is color-critical if it contains an edge whose deletion reduces its chromatic number.A counting result of Mubayi shows that for a color-critical graph F withχ（F）=r+1,there existsδ=δ（F）>0 such that if q<δn is a positive integer and G is a graph with sufficiently large order n and e（G）≥e（T_r（n））+q,then G has at least q·c（n,F）copies of F,where c（n,F）is the minimum number of copies of F in the graph obtained from the r-partite Turán graph T_r（n）by adding exactly one edge.In 2023,Ning and Zhai studied the counting result from a spectral perspective and established a tight bound on the number of copies of triangles,namely,t（G）≥（?）n/2」-1,whenever G is a graph of order n with the spectral radiusλ（G）>λ（T₂（n））.They raised the question of finding a spectral version of Mubayi’s result.It is not apparent to measure the increment on the spectral radius of a graph comparing to the edge version（Mubayi’s result）.In Chapter 4,we attempt to measure the increment and propose the following spectral version of counting problem.Let T_r^K_1,q（n）be the n-vertex graph obtained from T_r（n）by embedding a star K_1,qwith q edges into the vertex part of size「n/r（?）.We conjecture that there existsδ=δ（F）>0 such that if n is sufficiently large,1≤q<δn,and G is an n-vertex graph withλ（G）≥λ(T_r^K_1,q（n）),then G contains at least q·c（n,F）copies of F,and the graph T_r^K_1,q（n）is the unique spectral extremal graph attaining the minimum number of copies of F.We confirm this conjecture with the fundamental case of triangles for q=1,and characterize the unique spectral extremal graph.Let F_kbe the graph obtained from k triangles by sharing a common vertex.The F_k-free graphs of order n which attain the maximal spectral radius was firstly characterized by Cioab?,Feng,Tait and Zhang,and later uniquely determined by Zhai,Liu and Xue under the condition that n is sufficiently large.In Chapter 5,we get rid of the condition n being sufficiently large if k=2.The graph F₂is also known as the bowtie.We show that the unique n-vertex F₂-free spectral extremal graph is the balanced complete bipartite graph adding an edge in the vertex part with smaller size if n≥7,and the condition n≥7 is tight.Moreover,we shall propose a spectral conjecture for F_k-free graph with given number of edges.In particular,we solve the case k=2 by showing that the unique m-edge F₂-free spectral extremal graph is the join of K₂with an independent set of（m-1）/2 vertices if m≥8,and the condition m≥8 is tight.