BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
The families A and B are cross intersecting if A∩B=∅ for any A∈A and B∈B. Let t≥2 and k1≥k2≥⋯≥kt. We say that (F1,…,Ft) is an (n,k1,…,kt)-cross intersecting system if F1⊆(k1[n]),…,Ft⊆(kt[n]) are non-empty pairwise cross intersecting families. Let M(n,k1,…,kt) denote the maximum sum of sizes of families of an (n,k1,…,kt)-cross intersecting system. The case t=2 was studied by Frankl--Tokushige. Solving a problem of Shi-Frankl-Qian, Huang-Peng-Wang and Zhang-Feng independently determined M(n,k1,…,kt) for all n≥k1+k2.
Both the Simonovits stability theorem and the Nikiforov spectral stability theorem are powerful tools for solving exact values of Turán numbers in extremal graph theory. Recently, Füredi [J. Combin. Theory Ser. B 115 (2015)] provided a concise and contemporary proof of the Simonovits stability theorem. In this note, we present a unified treatment for some extremal graph problems, including short proofs of Nikiforov's spectral stability theorem and the clique stability theorem proved recently by Ma and Qiu [European J. Combin. 84 (2020)]. Moreover, some spectral extremal problems related to the p-spectral radius and signless Laplacian radius are also included.
The celebrated Erdős-Ko-Rado theorem \cite{EKR1961} states that the maximum intersecting k-uniform family on [n] is a full star if n≥2k+1. Furthermore, Hilton-Milner \cite{HM1967} showed that if an intersecting k-uniform family on [n] is not a subfamily of a full star, then its maximum size achieves only on a family isomorphic to HM(n,k):={G∈(k[n]):1∈G,G∩[2,k+1]=∅}∪{[2,k+1]} if n>2k and k≥4, and there is one more possibility in the case of k=3. Han and Kohayakawa \cite{HK2017} determined the maximum intersecting k-uniform family on [n] which is neither a subfamily of a full star nor a subfamily of the extremal family in Hilton-Milner theorm, and they asked what is the next maximum intersecting k-uniform family on [n]. Kostochka and Mubayi \cite{KM2016} gave the answer for large enough n. In this paper, we are going to get rid of the requirement that n is large enough in the result by Kostochka and Mubayi \cite{KM2016} and answer the question of Han and Kohayakawa \cite{HK2017}.
Given two graphs G and H, the Ramsey number R(G,H) is the minimum integer N such that any coloring of the edges of KN in red or blue yields a red G or a blue H. Let v(G) be the number of vertices of G and χ(G) be the chromatic number of G. Let s(G) denote the chromatic surplus of G, the cardinality of a minimum color class taken over all proper colorings of G with χ(G) colors. Burr showed that for a connected graph G and a graph H with v(G)≥s(H), R(G,H)≥(v(G)−1)(χ(H)−1)+s(H). A connected graph G is called H-good if R(G,H)=(v(G)−1)(χ(H)−1)+s(H). In this paper, we mainly confirm the Ramsey number for any tree Tn versus Km∪Kl. Our result yields that Tn is Km∪Kl-good.
Let Hs,t1,…,tk be the graph with s triangles and k odd cycles of lengths t1,…,tk≥5 intersecting in exactly one common vertex. Recently, Hou, Qiu and Liu [Discrete Math. 341 (2018) 126--137], and Yuan [J. Graph Theory 89 (1) (2018) 26--39] determined independently the maximum number of edges in an n-vertex graph that does not contain Hs,t1,…,tk as a subgraph. In this paper, we determine the graphs of order n that attain the maximum spectral radius among all graphs containing no Hs,t1,…,tk for n large enough.
The {\em Turán number} of an r-uniform graph F, denoted by ex(n,F), is the maximum number of edges in an F-free r-uniform graph on n vertices. The {\em Turán density} of F is defined as π(F)=n→∞lim(rn)ex(n,F). For graphs, Erdős-Stone-Simonovits (\cite{ESi}, \cite{ES}) showed that Π∞(2)=Πfin(2)=Π1(2)={0,21,32,…,ll−1,...}. We know quite few about the Turán density of an r-uniform graph for r≥3. Baber and Talbot \cite{BT}, and Pikhurko \cite{Pikhurko2} showed that there is an irrational number in Π3(3) and Πfin(3) respectively, disproving a conjecture of Chung and Graham \cite{FG}. Baber and Talbot \cite{BT} asked whether Π1(r) contains an irrational number. In this paper, we show that the Lagrangian density of F={123,124,134,234,567} (the disjoint union of K43 and an edge) is 33, consequently, the Turán density of the extension of F is an irrational number, answering the question of Baber and Talbot.
A real number α∈[0,1) is a jump for an integer r≥2 if there exists c>0 such that no number in (α,α+c) can be the Turán density of a family of r-uniform graphs. A classical result of Erd\H os and Stone \cite{ES} implies that that every number in [0,1) is a jump for r=2. Erd\H os \cite{E64} also showed that every number in [0,r!/rr) is a jump for r≥3 and asked whether every number in [0,1) is a jump for r≥3. Frankl and Rödl \cite{FR84} gave a negative answer by showing a sequence of non-jumps for every r≥3. After this, Erd\H os modified the question to be whether rrr! is a jump for r≥3? What's the smallest non-jump? Frankl, Peng, Rödl and Talbot \cite{FPRT} showed that 2rr5r! is a non-jump for r≥3. Baber and Talbot \cite{BT0} showed that every α∈[0.2299,0.2316)∪[0.2871,278) is a jump for r=3. Pikhurko \cite{Pikhurko2} showed that the set of all possible Turán densities of r-uniform graphs has cardinality of the continuum for r≥3. However, whether rrr! is a jump for r≥3 remains open, and 2rr5r! has remained the known smallest non-jump for r≥3. In this paper, we give a smaller non-jump by showing that 25rr54r! is a non-jump for r≥3. Furthermore, we give infinitely many irrational non-jumps for every r≥3.
We say that a graph F can be embedded into a graph G if G contains an isomorphic copy of F as a subgraph. Guo and Volkmann \cite{GV} conjectured that if G is a connected graph with at least n vertices and minimum degree at least n−3, then any tree with n vertices and maximum degree at most n−4 can be embedded into G. In this paper, we give a result slightly stronger than this conjecture and obtain a sufficient and necessary condition that a tree with n vertices and maximum degree at most n−3 can be embedded into a connected graph G with at least n vertices and minimum degree at least n−3. Our result implies that the conjecture of Guo and Volkmann is true with one exception. We also give an application to the Ramsey number of a tree versus a star.
Given a positive integer n and an r-uniform hypergraph (or r-graph for short) F, the Turan number ex(n,F) of F is the maximum number of edges in an r-graph on n vertices that does not contain F as a subgraph. The extension HF of F is obtained as follows: For each pair of vertices vi,vj in F not contained in an edge of F, we add a set Bij of r−2 new vertices and the edge {vi,vj}∪Bij, where the Bij 's are pairwise disjoint over all such pairs {i,j}. Let Kpr denote the complete r-graph on p vertices. For all sufficiently large n, we determine the Turan numbers of the extensions of a 3-uniform t-matching, a 3-uniform linear star of size t, and a 4-uniform linear star of size t, respectively. We also show that the unique extremal hypergraphs are balanced blowups of K3t−13,K2t3, and K3t4, respectively. Our results generalize the recent result of Hefetz and Keevash [7].
There is a remarkable connection between the maximum clique number and the Lagrangian of a graph given by T. S. Motzkin and E.G. Straus in 1965. This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It is useful in practice if similar results hold for hypergraphs. In this paper, we explore evidences that the Lagrangian of a 3-uniform hypergraph is related to the order of its maximum cliques when the number of edges of the hypergraph is in certain range. In particular, we present some results about a conjecture introduced by Y. Peng and C. Zhao (2012) and describe a combinatorial algorithm that can be used to check the validity of the conjecture.
The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. In most applications, we need an upper bound for the Lagrangian of a hypergraph. Frankl and Furedi in \cite{FF} conjectured that the r-graph with m edges formed by taking the first m sets in the colex ordering of N(r) has the largest Lagrangian of all r-graphs with m edges. In this paper, we give some partial results for this conjecture.
A remarkable connection between the order of a maximum clique and the Graph-Lagrangian of a graph was established by Motzkin and Straus in 1965. This connection and its extension were useful in both combinatorics and optimization. Since then, Graph-Lagrangian has been a useful tool in extremal combinatorics. In this paper, we give a parametrized Graph-Lagrangian for non-uniform hypergraphs and provide several Motzkin-Straus type results for nonuniform hypergraphs which generalize results from [1] and [2]. Another part of the paper concerns a long-standing conjecture of Frankl-Füredi on Graph-Lagrangians of hypergraphs. We show the connection between the Graph-Lagrangian of {1,r1,r2,⋯,rl}-hypergraphs and {r1,r2,⋯,rl}-hypergraphs. Some of our results provide solutions to the maximum value of a class of polynomial functions over the standard simplex of the Euclidean space.
In 1965, Motzkin and Straus established a remarkable connection between the order of a maximum clique and the Lagrangian of a graph and provided a new proof of Turán's theorem using the connection. The connection of Lagrangians and Turán densities can be also used to prove the fundamental theorem of Erdös-Stone-Simonovits on Turán densities of graphs. Very recently, the study of Turán densities of non-uniform hypergraphs have been motivated by extremal poset problems. In this paper, we attempt to explore the applications of Lagrangian method in determining Turán densities of non-uniform hypergraphs. We first give a definition of the Lagrangian of a non-uniform hypergraph, then give an extension of Motzkin-Straus theorem to non-uniform hypergraphs whose edges contain 1 or 2 vertices. Applying it, we give an extension of Erdös-Stone-Simonovits theorem to non-uniform hypergraphs whose edges contain 1 or 2 vertices.
There is a remarkable connection between the clique number and the Lagrangian of a 2-graph proved by Motzkin and Straus in 1965. It is useful in practice if similar results hold for hypergraphs. However the obvious generalization of Motzkin and Straus' result to hypergraphs is false. Frankl and Füredi conjectured that the r-uniform hypergraph with m edges formed by taking the first m sets in the colex ordering of N(r) has the largest Lagrangian of all r-uniform hypergraphs with m edges. For r=2, Motzkin and Straus' theorem confirms this conjecture. For r=3, it is shown by Talbot that this conjecture is true when m is in certain ranges. In this paper, we explore the connection between the clique number and Lagrangians for 3-uniform hypergraphs. As an application of this connection, we confirm that Frankl and Füredi's conjecture holds for bigger ranges of m when r=3. We also obtain two weaker versions of Turán type theorem for left-compressed 3-uniform hypergraphs.
Motzkin and Straus established a close connection between the maximum clique problem and a solution (namely graph-Lagrangians) to the maximum value of a class of homogeneous quadratic multilinear functions over the standard simplex of the Euclidean space in 1965. This connection provides a new proof of Turán's theorem. Recently, an extension of Motzkin-Straus theorem was proved for non-uniform hypergraphs whose edges contain 1 or 2 vertices in \cite{PPTZ}. It is interesting if similar results hold for other non-uniform hypergraphs. In this paper, we give some connection between polynomial programming and the clique of non-uniform hypergraphs whose edges contain 1, or 2, and more vertices. Specifically, we obtain some Motzkin-Straus type results in terms of the graph-Lagrangian of non-uniform hypergraphs whose edges contain 1, or 2, and more vertices.
Motzkin and Straus established a remarkable connection between the maximum clique and the Lagrangian of a graph in 1965. This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It is useful in practice if similar results hold for hypergraphs. In this paper, we provide upper bounds on the Lagrangian of a hypergraph containing dense subgraphs when the number of edges of the hypergraph is in certain ranges. These results support a pair of conjectures introduced by Y. Peng and C. Zhao (2012) and extend a result of J. Talbot (2002). \keywords{Cliques of hypergraphs \and Colex ordering \and Lagrangians of hypergraphs \and Polynomial optimization}
A remarkable connection between the order of a maximum clique and the Lagrangian of a graph was established by Motzkin and Straus in 1965. This connection and its extensions were applied in Turán problems of graphs and uniform hypergraphs. Very recently, the study of Turán densities of non-uniform hypergraphs has been motivated by extremal poset problems. In this paper, we give some Motzkin-Straus type results for non-uniform hypergraphs.
A remarkable connection between the order of a maximum clique and the Lagrangian of a graph was established by Motzkin and Straus in [7]. This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It has been also applied in spectral graph theory. Estimating the Lagrangians of hypergraphs has been successfully applied in the course of studying the Turan densities of several hypergraphs as well. It is useful in practice if Motzkin-Straus type results hold for hypergraphs. However, the obvious generalization of Motzkin and Straus' result to hypergraphs is false. We attempt to explore the relationship between the Lagrangian of a hypergraph and the order of its maximum cliques for hypergraphs when the number of edges is in certain range. In this paper, we give some Motzkin-Straus type results for r-uniform hypergraphs. These results generalize and refine a result of Talbot in [19] and a result in [11].
In 1965, Motzkin and Straus [5] provided a new proof of Turan's theorem based on a continuous characterization of the clique number of a graph using the Lagrangian of a graph. This new proof aroused interests in the study of Lagrangians of r-uniform graphs. The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Sidorenko and Frankl-Furedi applied Lagrangians of hypergraphs in finding Turan densities of hypergraphs. Frankl and Rodl applied it in disproving Erdos' jumping constant conjecture. In most applications, we need an upper bound for the Lagrangian of a hypergraph. Frankl and Furedi conjectured that the r-uniform graph with m edges formed by taking the first m sets in the colex ordering of N(r) has the largest Lagrangian of all r-uniform graphs with m edges. Talbot in [14] provided some evidences for Frankl and Furedi's conjecture. In this paper, we prove that the r-uniform graph with m edges formed by taking the first m sets in the colex ordering of N(r) has the largest Lagrangian of all r-uniform graphs on t vertices with m edges when tchooser−3 or tchooser−4. As an implication, we also prove that Frankl and Furedi's conjecture holds for 3-uniform graphs with tchoose3−3 or tchoose3−4 edges.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.