Search

We consider the minimum degree stability of graphs forbidding odd cycles: What is the tight bound on the minimum degree to guarantee that the structure of a C2k+1 ${C}_{2k+1}$‐free graph inherits from the extremal graph (a balanced complete bipartite graph)? Andrásfai, Erdős, and Sós showed that if a {C3,C5,...,C2k+1} $\{{C}_{3},{C}_{5},\ldots ,{C}_{2k+1}\}$‐free graph on n $n$ vertices has minimum degree greater than 22k+3n $\frac{2}{2k+3}n$, then it is bipartite. Häggkvist showed that for k∈{1,2,3,4} $k\in \{1,2,3,4\}$, if a C2k+1 ${C}_{2k+1}$‐free graph on n $n$ vertices has minimum degree greater than 22k+3n $\frac{2}{2k+3}n$, then it is bipartite. Häggkvist also pointed out that this result cannot be extended to k≥5 $k\ge 5$. In this paper, we give a complete answer for any k≥5 $k\ge 5$. We show that if k≥5 $k\ge 5$ and G $G$ is an n $n$‐vertex C2k+1 ${C}_{2k+1}$‐free graph with δ(G)≥n6+1 $\delta (G)\ge \frac{n}{6}+1$, then G $G$ is bipartite, and the bound n6+1 $\frac{n}{6}+1$ is tight. [ABSTRACT FROM AUTHOR]

Hypergraph Lagrangian function has been a helpful tool in several celebrated results in extremal combinatorics. Let G be an r-uniform graph on [n] and let x = (x 1 , ... , x n) ∈ [ 0 , ∞) n. The graph Lagrangian function is defined to be λ (G , x) = ∑ e ∈ E (G) ∏ i ∈ e x i. The graph Lagrangian is defined as λ (G) = max { λ (G , x) : x ∈ Δ } , where Δ = { x = (x 1 , x 2 , ... , x n) ∈ [ 0 , 1 ] n : x 1 + x 2 + ⋯ + x n = 1 }. The Lagrangian density π λ (F) of an r-graph F is defined to be π λ (F) = sup { r ! λ (G) : G does not contain F }. Sidorenko (Combinatorica 9:207–215, 1989) showed that the Lagrangian density of an r-uniform hypergraph F is the same as the Turán density of the extension of F. Therefore, determining the Lagrangian density of a hypergraph will add a result to the very few known results on Turán densities of hypergraphs. For an r-uniform graph H with t vertices, π λ (H) ≥ r ! λ (K t - 1 r) since K t - 1 r (the complete r-uniform graph with t - 1 vertices) does not contain a copy of H. We say that an r-uniform hypergraph H with t vertices is λ -perfect if the equality π λ (H) = r ! λ (K t - 1 r) holds. A fundamental theorem of Motzkin and Straus implies that all 2-uniform graphs are λ -perfect. It is interesting to understand the λ -perfect property for r ≥ 3. Our first result is to show that the disjoint union of a λ -perfect 3-graph and S 2 , t = { 123 , 124 , 125 , 126 , ... , 12 (t + 2) } is λ -perfect, this result implies several previous results: Taking H to be the 3-graph spanned by one edge and t = 1 , we obtain the result by Hefetz and Keevash (J Comb Theory Ser A 120:2020–2038, 2013) that a 3-uniform matching of size 2 is λ -perfect. Doing it repeatedly, we obtain the result in Jiang et al. (Eur J Comb 73:20–36, 2018) that any 3-uniform matching is λ -perfect. Taking H to be the 3-uniform linear path of length 2 or 3 and t = 1 repeatedly, we obtain the results in Hu et al. (J Comb Des 28:207–223, 2020). Earlier results indicate that K 4 3 - = { 123 , 124 , 134 } and F 5 = { 123 , 124 , 345 } are not λ -perfect, we show that the disjoint union of K 4 3 - (or F 5 ) and S 2 , t are λ -perfect. Furthermore, we show the disjoint union of a 3-uniform hypergraph H and S 2 , t is λ -perfect if t is large. We also give an irrational Lagrangian density of a family of four 3-uniform hypergraphs. [ABSTRACT FROM AUTHOR]

A graph G is k-edge-Hamiltonian if any collection of vertex-disjoint paths with at most k edges altogether belong to a Hamiltonian cycle in G. A graph G is k-Hamiltonian if for all S ⊆ V (G) with | S | ≤ k , the subgraph induced by V (G) ∖ S has a Hamiltonian cycle. These two concepts are classical extensions of the usual Hamiltonian graphs. In this paper, we present some spectral sufficient conditions for a graph to be k-edge-Hamiltonian and k-Hamiltonian in terms of the adjacency spectral radius as well as the signless Laplacian spectral radius. Our results could be viewed as slight extensions of the recent theorems proved by Li and Ning [Linear Multilinear Algebra. 2016;64:2252–2269], Nikiforov [Czechoslovak Math J. 2016;66:925–940] and Li et al. [Linear Multilinear Algebra. 2018;66:2011–2023]. Moreover, we shall prove a stability result for graphs being k-Hamiltonian, which could be regarded as a complement of two recent results of Füredi et al. [Discrete Math. 2017;340:2688–2690] and [Discrete Math. 2019;342:1919–1923]. [ABSTRACT FROM AUTHOR]

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 K N in red or blue yields a red G or a blue H. Let χ (G) be the chromatic number of G, and 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. A connected graph G is called H-good if R (G , H) = (v (G) - 1) (χ (H) - 1) + s (H) . Chvátal (J. Graph Theory 1:93, 1977) showed that any tree is K m -good for m ≥ 2 , where K m denotes a complete graph with m vertices. Let tH denote the union of t disjoint copies of graph H. Sudarsana et al. (Comput. Sci. 6196, Springer, Berlin, 2010) proved that the n-vertex path P n is 2 K m -good for n ≥ 3 and m ≥ 2 , and conjectured that any n-vertex tree T n is 2 K m -good. In this paper, we confirm this conjecture and prove that T n is 2 K m -good for n ≥ 3 and m ≥ 2 . We also prove a conclusion which yields that T n is (K m ∪ K l) -good, where K m ∪ K l is the disjoint union of K m and K l , m > l ≥ 2 . Furthermore, we extend the Ramsey goodness of connected graphs to disconnected graphs and study the relation between the Ramsey number of the components of a disconnected graph F versus a graph H. We show that if each component of a graph F is H-good, then F is H-good. Our result implies the exact value of R (F , K m ∪ K l) , where F is a forest and m , l ≥ 2 . [ABSTRACT FROM AUTHOR]

We present an Oppenheim type determinantal inequality for positive definite block matrices. Recently, Lin [Linear Algebra Appl. 2014;452:1–6] proved a remarkable extension of Oppenheim type inequality for block matrices, which solved a conjecture of Günther and Klotz. There is a requirement that two matrices commute in Lin's result. The motivation of this paper is to obtain another natural and general extension of Oppenheim type inequality for block matrices to get rid of the requirement that two matrices commute. [ABSTRACT FROM AUTHOR]

We say that a graph F $F$ can be embedded into a graph G $G$ if G $G$ contains an isomorphic copy of F $F$ as a subgraph. Guo and Volkmann conjectured that if G $G$ is a connected graph with at least n $n$ vertices and minimum degree at least n−3 $n-3$, then any tree with n $n$ vertices and maximum degree at most n−4 $n-4$ can be embedded into G $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 $n$ vertices and maximum degree at most n−3 $n-3$ can be embedded into a connected graph G with at least n $n$ vertices and minimum degree at least n−3 $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. [ABSTRACT FROM AUTHOR]

Let H 1 , ..., H k be bipartite graphs. The bipartite Ramsey number b r (H 1 , ... , H k) is the minimum integer N such that any k -edge-coloring of the complete bipartite graph K N , N contains a monochromatic H i in color i for some i ∈ { 1 , 2 , ... , k }. The study of bipartite Ramsey number was initiated in the early 70s by Faudree and Schelp (1975), and they showed that b r (P 2 n , P 2 m) = n + m − 1 , where P n denotes a path with n vertices. Combining their result and the regularity lemma, one can obtain asymptotic value b r (C 2 ⌊ α 1 n ⌋ , C 2 ⌊ α 2 n ⌋ ) = (α 1 + α 2 + o (1)) n for α 1 , α 2 > 0 , where C n denotes a cycle with n vertices. The study of bipartite Ramsey numbers of cycles has also attracted lots of attention recently. For example, Bucić, Letzter and Sudakov (2019) showed that b r (C 2 n , C 2 n , C 2 n) = (3 + o (1)) n and they remarked that it is interesting to determine the exact value of b r (C 2 n , C 2 m). Zhang and Sun (2011), Zhang, Sun, and Wu (2013), and Gholami and Rowshan (2021) determined b r (C 4 , C 2 n) , b r (C 6 , C 2 n) , and b r (C 8 , C 2 n) respectively. In this paper, we determine b r (C 2 n , C 2 m) for all the remaining cases and show that b r (C 2 n , C 2 m) = n + m − 1 for all n > m ≥ 5 and b r (C 2 n , C 2 n) = 2 n if n ≥ 5. It is somehow interesting that b r (C 2 n , C 2 m) is the same as b r (P 2 n , P 2 m) if n ≠ m , and b r (C 2 n , C 2 n) is one more than b r (P 2 n , P 2 n). [ABSTRACT FROM AUTHOR]

For a fixed positive integer n and an r-uniform hypergraph H, the Turán number ex(n, H) is the maximum number of edges in an H-free r-uniform hypergraph on n vertices, and the Lagrangian density of H is defined as π λ (H) = sup { r ! λ (G) : G is an H -free r -uniform hypergraph } , where λ (G) = max { ∑ e ∈ G ∏ i ∈ e x i : x i ≥ 0 and ∑ i ∈ V (G) x i = 1 } is the Lagrangian of G. For an r-uniform hypergraph H on t vertices, it is clear that π λ (H) ≥ r ! λ (K t - 1 r) . Let us say that an r-uniform hypergraph H on t vertices is λ -perfect if π λ (H) = r ! λ (K t - 1 r) . A result of Motzkin and Straus implies that all graphs are λ -perfect. It is interesting to explore what kind of hypergraphs are λ -perfect. A conjecture in [22] proposes that every sufficiently large r-uniform linear hypergraph is λ -perfect. In this paper, we investigate whether the conjecture holds for linear 3-uniform paths. Let P t = { e 1 , e 2 , ⋯ , e t } be the linear 3-uniform path of length t, that is, | e i | = 3 , | e i ∩ e i + 1 | = 1 and e i ∩ e j = ∅ if | i - j | ≥ 2 . We show that P 3 and P 4 are λ -perfect. Applying the results on Lagrangian densities, we determine the Turán numbers of their extensions. [ABSTRACT FROM AUTHOR]

The celebrated Erdős–Ko–Rado theorem (Erdős et al., 1961) states that a maximum intersecting k -uniform family on [ n ] must be a full star if n ≥ 2 k + 1. Furthermore, Hilton and Milner (1967) showed that if an intersecting k -uniform family on [ n ] is not a subfamily of a full star, then its maximum size is achieved only by a family isomorphic to H M (n , k) ≔ { G ∈ [ n ] k : 1 ∈ G , G ∩ [ 2 , k + 1 ] ≠ 0̸ } ∪ { [ 2 , k + 1 ] } if n ≥ 2 k + 1 and k ≥ 4 , and there is one more possibility if k = 3. Han and Kohayakawa (2017) determined a maximum intersecting k -uniform family on [ n ] which is neither a subfamily of a full star nor a subfamily of the extremal families in Hilton-Milner theorem, and they asked what the next maximum intersecting k -uniform families on [ n ] are. Kostochka and Mubayi (2017) answered the question 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 (2017), and answer the question of Han and Kohayakawa (2017) for all n ≥ 2 k + 1. [ABSTRACT FROM AUTHOR]

Guaranteed by Szemerédi's Regularity Lemma, a technique originated by Łuczak is to reduce the problem of showing the existence of a monochromatic cycle to show the existence of a monochromatic matching in a component. So determining the Ramsey number of connected matchings is crucial in determining the Ramsey number of cycles. Let k,l,m be integers and r(k,l,m) be the minimum integer N such that for any red‐blue‐green coloring of KN,N, there is a red matching of size at least k in a component, or a blue matching of size at least l in a component, or a green matching of size at least m in a component. Bucić, Letzter, and Sudakov determined the exact value of r(k,l,l) and led to the asymptotic value of 3‐colored bipartite Ramsey number of cycles (symmetric case). In this paper, we determine the exact value of r(k,l,m) completely. This answers a question of Bucić, Letzter, and Sudakov. The crucial part of the proof is the construction we give in Section 4. Applying the technique of Łuczak, we obtain the asymptotic value of 3‐colored bipartite Ramsey number of cycles for all asymmetric cases. [ABSTRACT FROM AUTHOR]

The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Recently, Lagrangian densities of hypergraphs and Turán numbers of their extensions have been studied actively. However, determining the Lagrangian density of a hypergraph is not an easy task even for a "simple" hypergraph. For example, to determine the Lagrangian density of K43 is equivalent to determine the Turán density of K43 (a long standing conjecture of Turán). Hefetz and Keevash studied the Lagrangian density of the 3‐uniform matching of size 2. Pikhurko determined the Lagrangian density of a 4‐uniform tight path of length 2 and this led to confirm the conjecture of Frankl and Füredi on the Turán number of the r‐uniform generalized triangle for the case r=4. It is natural and interesting to consider Lagrangian densities of other "basic" hypergraphs. In this paper, we determine the Lagrangian densities for a class of 3‐uniform linear forests. For positive integers s and t, let Ps,t be the disjoint union of a 3‐uniform linear path of length s and t pairwise disjoint edges. In this paper, we determine the Lagrangian densities of Ps,t for any t and s=2 or 3. Applying a modified version of Pikhurko's transference argument used by Brandt, Irwin, and Jiang, we obtain the Turán numbers of their extensions. [ABSTRACT FROM AUTHOR]

Given two graphs G and H , the Ramsey number r (G , H) is the minimum integer N such that any red-blue coloring of the edges of K N contains either a red copy of G or a blue copy of H. Let v (G) denote the number of vertices of G , and χ (G) denote 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 [3] 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). Chvátal [7] showed that any tree is K m -good for m ≥ 2 , where K m denotes a complete graph with m vertices. Let t K m denote t vertex disjoint copies of K m. Recently, Hu and Peng [13] proved that any tree T n is 2 K m -good for n ≥ 3 and m ≥ 2 , they [14] also showed that any large tree is t K 2 -good for t ≥ 3. In this paper, we show that any large tree is t K m -good for t ≥ 3 and m ≥ 3. [ABSTRACT FROM AUTHOR]

The Lagrangian density of an r -uniform hypergraph F is r ! multiplying the supremum of the Lagrangians of all F -free r -uniform hypergraphs. For an r -graph H with t vertices, it is clear that π λ (H) ≥ r ! λ (K t − 1 r). We say that an r -uniform hypergraph H with t vertices is λ -perfect if π λ (H) = r ! λ (K t − 1 r). A theorem of Motzkin–Straus implies that all 2-uniform graphs are λ -perfect. It is interesting to explore what kind of hypergraphs are λ -perfect. A hypergraph is linear if any 2 edges have at most 1 vertex in common. We propose the following conjecture: (1) For r ≥ 3 , there exists n such that a linear r -uniform hypergraph with at least n vertices is λ -perfect. (2) For r ≥ 3 , there exists n such that if G , H are λ -perfect r -graphs with at least n vertices, then G ⨆ H is λ -perfect. Regarding this conjecture, we obtain a partial result: Let S 2 , t = { 123 , 124 , 125 , 126 , ... , 12 (t + 2) }. (An earlier result of Sidorenko states that S 2 , t is λ -perfect (Sidorenko, 1989).) Let H be a λ -perfect 3-graph with s vertices. Then F = S 2 , t ⨆ H is λ -perfect if s ≥ 3 and t ≥ 3. There was no known result on Lagrangian densities of hypergraph cycles and there were 3 unsolved cases for 3-uniform graphs spanned by 3 edges: a linear cycle of length 3: C 3 3 = { 123 , 345 , 561 } , the generalized triangle: F 5 = { 123 , 124 , 345 } and K 4 3 − = { 123 , 124 , 134 }. In this paper, we obtain the Lagrangian density of F 5 which is an example of non- λ -perfect 3-uniform graph. We show that C 3 3 is λ -perfect, and among all C 3 3 -free 3-graphs G , only those hypergraphs containing K 5 3 achieve the Lagrangian λ (K 5 3). The Turán densities of extensions of the above hypergraphs can be obtained by applying a transference technique of Pikhurko. [ABSTRACT FROM AUTHOR]

The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. The Lagrangian density of an r -uniform graph F is π λ ( F ) = sup { r ! λ ( G ) : G i s F - f r e e } , where λ ( G ) is the Lagrangian of an r -uniform graph G . Recently, Lagrangian densities of hypergraphs and Turán numbers of their extensions have been studied actively. In particular, Hefetz and Keevash (2013) studied the Lagrangian density of the 3-uniform matching of size 2 and the Turán number of its extension. We obtain the Lagrangian densities of a 3-uniform matching of size t , a 3-uniform linear star of size t , and a 4-uniform linear star of size t . Using a stability argument of Pikhurko and a transference technique between the Lagrangian density of an r -uniform graph F and the Turán number of its extension, we can also determine the Turán numbers of their extensions. [ABSTRACT FROM AUTHOR]

A real number α∈[0,1) is a jump for an integer r≥2 if there exists a constant c>0 such that any number in (α,α+c] cannot be the Turán density of a family of r-uniform graphs. Erdős and Stone showed that every number in [0,1) is a jump for r=2. Erdős asked whether the same is true for r≥3. Frankl and Rödl gave a negative answer by showing the existence of non-jumps for r≥3. Recently, Baber and Talbot showed that every number in [0.2299,0.2316)⋃[0.2871,827) is a jump for r=3 using Razborov’s flag algebra method. Pikhurko showed that the set of non-jumps for every r≥3 has cardinality of the continuum. But, there are still a lot of unknowns regarding jumps for hypergraphs. In this paper, we show that 1+r-1lr-1-rlr-2 is a non-jump for r≥4 and l≥3 which generalizes some earlier results. We do not know whether the same result holds for r=3. In fact, when r=3 and l=3, 1+r-1lr-1-rlr-2=29, and determining whether 29 is a jump or not for r=3 is perhaps the most important unknown question regarding this subject. Erdős offered $500 for answering this question. [ABSTRACT FROM AUTHOR]

We study the Hessian matrix of the Lagrange function of a dense 3-uniform hypergraph and show that the Lagrange function of a dense 3-uniform hypergraph has a unique optimal weight. We also give a characterization to the optimal weight of a dense 3-uniform hypergraph by the Hessian matrix of the Lagrange function and a simple application on the regular 3-uniform hypergraphs. [ABSTRACT FROM AUTHOR]

In 1965, Motzkin–Straus established the connection between the maximum cliques and the Lagrangian of a graph, the maximum value of a quadratic function determined by a graph in the standard simplex. This connection gave a proof of the Turán’s classical result on Turán densities of complete graphs. In 1980’s, Sidorenko and Frankl–Füredi further developed this method for hypergraph Turán problems. However, the connection between the Lagrangian and the maximum cliques of a graph cannot be extended to hypergraphs. In 2009, S. Rota Bulò and M. Pelillo defined a homogeneous polynomial function of degree r determined by an r -uniform hypergraph and gave the connection between the minimum value of this polynomial function and the maximum cliques of an r -uniform hypergraph. In this paper, we provide a connection between the local (global) minimizers of non-homogeneous polynomial functions to the maximal (maximum) cliques of hypergraphs whose edges containing r − 1 and r vertices. This connection can be applied to obtain an upper bound on the Turán densities of complete { r − 1 , r } -type hypergraphs. [ABSTRACT FROM AUTHOR]

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ős and Stone [8] implies that every number in [ 0 , 1) is a jump for r = 2. Erdős [6] also showed that every number in [ 0 , r ! / r r) is a jump for r ≥ 3 and asked whether every number in [ 0 , 1) is a jump for r ≥ 3. Frankl and Rödl [9] gave a negative answer by showing a sequence of non-jumps for every r ≥ 3. After this, Erdős modified the question to be whether r ! r r is a jump for r ≥ 3 ? What's the smallest non-jump? Frankl, Peng, Rödl and Talbot [10] showed that 5 r ! 2 r r is a non-jump for r ≥ 3. However, Baber and Talbot [1] showed that there are more jumps by proving that every α ∈ [ 0.2299 , 0.2316) ∪ [ 0.2871 , 8 27) is a jump for r = 3. However, whether r ! r r is a jump for r ≥ 3 remains open, and 5 r ! 2 r r has remained the known smallest non-jump for r ≥ 3. In this paper, we give a smaller non-jump by showing that 54 r ! 25 r r is a non-jump for r ≥ 3. Furthermore, we give infinitely many irrational non-jumps for every r ≥ 3. [ABSTRACT FROM AUTHOR]

Let H s , t 1 , ... , t k be the graph with s triangles and k odd cycles of lengths t 1 , ... , t k ≥ 5 intersecting in exactly one common vertex. Recently, Hou et al. (2018) [27] , and Yuan (2018) [42] determined independently the maximum number of edges in an n -vertex graph that does not contain H s , t 1 , ... , t k as a subgraph. In this paper, we determine the graphs of order n that attain the maximum spectral radius among all graphs containing no H s , t 1 , ... , t k for n large enough. [ABSTRACT FROM AUTHOR]

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 has been motivated by extremal poset problems and suggested by Johnston and Lu. 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 the Motzkin–Straus theorem to non-uniform hypergraphs whose edges contain 1 or 2 vertices. Applying it, we give an extension of the Erdős–Stone–Simonovits theorem to non-uniform hypergraphs whose edges contain 1 or 2 vertices. Our approach follows from the approach in Keevash’s paper Keevash (2011). [ABSTRACT FROM AUTHOR]

Let G and H be simple graphs. The Ramsey number r (G , H) is the minimum integer N such that any red-blue-coloring of edges of K N contains either a red copy of G or a blue copy of H. Let m K 1 , t denote m vertex-disjoint copies of K 1 , t. A lower bound is that r (m K 1 , t , n K 1 , s) ≥ m (t + 1) + n − 1. Burr, Erdős and Spencer proved that this bound is indeed the Ramsey number r (m K 1 , t , n K 1 , s) for t = s = 3 , m ≥ 2 and m ≥ n. In this paper, we show that this bound is the Ramsey number r (m K 1 , t , n K 1 , s) for t ≥ s = 3 , m ≥ 2 and m ≥ n. We also show that this bound is the Ramsey number r (m K 1 , t , n K 1 , s) for s ≥ 4 , t > s (s − 1) 2 and m > n. [ABSTRACT FROM AUTHOR]

Motzkin and Straus established a remarkable connection between the maximum clique and the Graph-Lagrangian of a graph in (Can. J. Math. 17:533-540, ). 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 Graph-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 Peng and Zhao (Graphs Comb. 29:681-694, ) and extend a result of Talbot (Comb. Probab. Comput. 11:199-216, ). [ABSTRACT FROM AUTHOR]

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 Füredi conjectured that the -graph with edges formed by taking the first sets in the colex ordering of has the largest Lagrangian of all -graphs with edges. Talbot in Talbot (2002) provided some evidences for Frankl and Füredi’s conjecture. In this paper, we prove that the -graph with edges formed by taking the first sets in the colex ordering of has the largest Lagrangian of all -uniform graphs on vertices with edges when where under some conditions. As an implication, we also derive that Frankl and Füredi’s conjecture holds for 3-uniform graphs with edges where . [ABSTRACT FROM AUTHOR]

Motzkin and Straus established a remarkable connection between the maximum clique and the Lagrangian of a graph in []. They showed that if G is a 2-graph in which a largest clique has order l then $${\lambda(G)=\lambda(K^{(2)}_l),}$$ where λ( G) denotes the Lagrangian of G. It is interesting to study a generalization of the Motzkin-Straus Theorem to hypergraphs. In this note, we give a Motzkin-Straus type result. We show that if m and l are positive integers satisfying $${{l-1 \choose 3} \le m \le {l-1 \choose 3} + {l-2 \choose 2}}$$ and G is a 3-uniform graph with m edges and G contains a $${K_{l-1}^{(3)}}$$, a clique of order l−1, then $${\lambda(G) = \lambda(K_{l-1}^{(3)})}$$. Furthermore, the upper bound $${{l-1 \choose 3} + {l-2 \choose 2}}$$ is the best possible. [ABSTRACT FROM AUTHOR]

Let G = ( V, E) be a graph and $${R\subseteq E}$$ . A matching M in G is called R-feasible if the subgraph induced by the M-saturated vertices does not have an edge of R. We show that the general problem of finding a maximum size R-feasible matching in G is NP-hard and identify several natural applications of this new concept. In particular, we use R-feasible matchings to give a necessary and sufficient condition for the existence of a systems of disjoint representatives in a family of hypergraphs. This provides another Hall-type theorem for hypergraphs. We also introduce the concept of R-feasible (vertex) cover and combine it with the concept of R-feasible matching to provide a new formulation and approach to Ryser's conjecture. [ABSTRACT FROM AUTHOR]

Abstract: Text: A positive integer n is perfect if the sum of the proper positive divisors of n equals n. Generalizing this we call n a Zumkeller number if the set of its positive divisors can be partitioned into two disjoint subsets of equal sum. Similarly we call n a half-Zumkeller number if the set of its proper positive divisors can be so partitioned. A study of Zumkeller numbers, half-Zumkeller numbers and their relation to practical numbers is undertaken in this paper. Clark et al. (2008) [1] announced some results about Zumkeller numbers and half-Zumkeller numbers, and suggested two conjectures. In the present paper we shall settle one of the conjectures, prove the second conjecture in some special cases, and prove several results related to the second conjecture. We shall also show that if there is an even Zumkeller number that is not half-Zumkeller it is bigger than . Video: For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=z85qyvIorBE. [Copyright &y& Elsevier]

A number $${\alpha\in [0, 1)}$$ is a jump for an integer r ≥ 2 if there exists a constant c > 0 such that for any family $${{\mathcal F}}$$ of r-uniform graphs, if the Turán density of $${{\mathcal F}}$$ is greater than α, then the Turán density of $${{\mathcal F}}$$ is at least α + c. A fundamental result in extremal graph theory due to Erdős and Stone implies that every number in [0, 1) is a jump for r = 2. Erdős also showed that every number in [0, r!/ r r) is a jump for r ≥ 3. However, not every number in [0, 1) is a jump for r ≥ 3. In fact, Frankl and Rödl showed the existence of non-jumps for r ≥ 3. By a similar approach, more non-jumps were found for some r ≥ 3 recently. But there are still a lot of unknowns regarding jumps for hypergraphs. In this note, we show that if $${c\cdot{\frac{r!}{r^r}}}$$ is a non-jump for r ≥ 3, then for every p ≥ r, $${c\cdot{\frac{p!}{p^p}}}$$ is a non-jump for p. [ABSTRACT FROM AUTHOR]

Abstract: Estimating Turán densities of hypergraphs is believed to be one of the most challenging problems in extremal set theory. The concept of ‘jump’ concerns the distribution of Turán densities. A number is a jump for -uniform graphs if there exists a constant such that for any family of -uniform graphs, if the Turán density of is greater than , then the Turán density of is at least . A fundamental result in extremal graph theory due to Erdős and Stone implies that every number in is a jump for graphs. Erdős also showed that every number in is a jump for -uniform hypergraphs. Furthermore, Frankl and Rödl showed the existence of non-jumps for hypergraphs. Recently, more non-jumps were found in for -uniform hypergraphs. But there are still a lot of unknowns regarding jumps for hypergraphs. In this paper, we propose a new but related concept–strong-jump and describe several sequences of non-strong-jumps. It might help us to understand the distribution of Turán densities for hypergraphs better by finding more non-strong-jumps. [Copyright &y& Elsevier]

Abstract: Let be an integer. A real number is a jump for r if there is a constant such that for any and any integer m where , there exists an integer such that any r-uniform graph with vertices and density contains a subgraph with m vertices and density . It follows from a fundamental theorem of Erdős and Stone that every is a jump for . Erdős asked whether the same is true for . Frankl and Rödl gave a negative answer by showing some non-jumping numbers for every . In this paper, we provide a recursive formula to generate more non-jumping numbers for every based on the current known non-jumping numbers. [Copyright &y& Elsevier]

Abstract: Let be an integer. A real number is a jump for if for any and any integer , any -uniform graph with vertices and density at least contains a subgraph with vertices and density at least , where does not depend on and . A result of Erdős, Stone and Simonovits implies that every is a jump for . Erdős asked whether the same is true for . Frankl and Rödl gave a negative answer by showing an infinite sequence of non-jumping numbers for every . However, there are a lot of unknowns on determining whether or not a number is a jump for . In this paper, we find two infinite sequences of non-jumping numbers for , and extend one of the results to every . Our approach is still based on the approach developed by Frankl and Rödl. [Copyright &y& Elsevier]

Abstract: We characterize -free graphs. We also characterize graphs which are both -free and -free. [Copyright &y& Elsevier]

Abstract: Let be an integer. The real number is a jump for r if there exists such that for every positive ϵ and every integer , every r-uniform graph with vertices and at least edges contains a subgraph with m vertices and at least edges. A result of Erdős, Stone and Simonovits implies that every is a jump for . For , Erdős asked whether the same is true and showed that every is a jump. Frankl and Rödl gave a negative answer by showing that is not a jump for r if and . Another well-known question of Erdős is whether is a jump for and what is the smallest non-jumping number. In this paper we prove that is not a jump for . We also describe an infinite sequence of non-jumping numbers for . [Copyright &y& Elsevier]

A classical result of Erdős and Rademacher (1955) indicates a supersaturation phenomenon. It says that if G is a graph on n vertices with at least ⌊ n 2 / 4 ⌋ + 1 edges, then G contains at least ⌊ n / 2 ⌋ triangles. We prove a spectral version of Erdős–Rademacher's theorem. Moreover, Mubayi (2010) [28] extends the result of Erdős and Rademacher from a triangle to any color-critical graph. It is interesting to study the extension of Mubayi from a spectral perspective. However, it is not apparent to measure the increment on the spectral radius of a graph comparing to the traditional edge version (Mubayi's result). In this paper, we provide a way to measure the increment on the spectral radius of a graph and propose a spectral version on the counting problems for color-critical graphs. [ABSTRACT FROM AUTHOR]

Determining the Turán density of a hypergraph is a central and challenging question in extremal combinatorics. We know very few about the Turán densities of hypergraphs. Even the conjecture given by Turán on the Turán density of K 4 3 , the smallest complete hypergraph remains open. It turns out that the hypergraph Lagrangian method, a continuous optimization method has been helpful in hypergraph extremal problems. In this paper, we intend to explore this method further, and try to understand the Turán densities of hypergraphs via Lagrangian densities. Given an integer n and an r -uniform graph H , the Turán number of H , denoted by ex (n, H), is the maximum number of edges in an n -vertex r -uniform graph without containing a copy of H. The Turán density of H , denoted by π (H), is the limit of the function e x (n , H) (n r) as n → ∞. The Lagrangian density of H is π λ (H) = sup { r ! λ (F) : H i s n o t c o n t a i n e d i n F } , where λ (F) is the Lagrangian of F. For any r -uniform graph H , Sidorenko showed that π λ (H) equals the Turán density of the extension of H. So researching on Lagrangian densities of hypergraphs is helpful to better understand the behavior of the Turán densities of hypergraphs. For a t -vertex r -uniform graph H , π λ (H) ≥ r ! λ (K t − 1 r) since K t − 1 r doesn't contain H , where K t − 1 r is the (t − 1) -vertex complete r -uniform graph. We say that H is λ -perfect if the equality holds, i.e., π λ (H) = r ! λ (K t − 1 r). A result given by Motzkin and Straus shows that every graph is λ -perfect. It is natural and fundamental to explore which hypergraphs are λ -perfect. Sidorenko (1989) showed that the (r − 2) -fold enlargement of a tree satisfying the Erdős-Sós conjecture with order at least A r is λ -perfect, where A r is the last maximum of the function g r (x) = (r + x − 3) − r ∏ i = 1 r − 1 (i + x − 2) as x ≥ 2. By using the so-called generalised Lagrangian of hypergraphs, Jenssen (2017) showed that the (r − 2) -fold enlargement of M 2 2 for r = 5 , 6 or 7 is λ -perfect, where M s r is the r -uniform matching of size s. The result given by Sidorenko (1989) implies that the (r − 2) -fold enlargement of M t 2 for r = 5 and t ≥ 4, or r = 6 and t ≥ 6, or r = 7 and t ≥ 8 is λ -perfect. So there are still some gaps between the results of Jenssen and Sidorenko. In this paper we fill the gaps for r = 5 or 6. We also determine the Lagrangian densities for the (r − 3) -fold enlargement of M t 3 for r = 5 or 6. [ABSTRACT FROM AUTHOR]

Let F k be the (friendship) 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 [Electron. J. Combin. 27 (4) (2020)], and later uniquely determined by Zhai, Liu and Xue [Electron. J. Combin. 29 (3) (2022)] under the condition that n is sufficiently large. In this paper, we get rid of the condition on n being sufficiently large if k = 2. The graph F 2 is also known as the bowtie. We show that the unique n -vertex F 2 -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. Our result is a spectral generalization of a theorem of Erdős, Füredi, Gould and Gunderson [J. Combin. Theory Ser. B 64 (1995)], which states that ex (n , F 2) = ⌊ n 2 / 4 ⌋ + 1. Moreover, we study the spectral extremal problem for F k -free graphs with given number of edges. In particular, we show that the unique m -edge F 2 -free spectral extremal graph is the join of K 2 with an independent set of m − 1 2 vertices if m ≥ 8 , and the condition m ≥ 8 is tight. [ABSTRACT FROM AUTHOR]

The Lagrangian of a hypergraph is a function that has featured notably in hypergraph Turán densities. Motzkin and Straus established the relationship between Lagrangian and the maximum clique in a graph. As a generalization of Motzkin-Straus Theorem, Frankl and Füredi put forward a well-known conjecture, which states 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. The conjecture was settled when r = 3 for sufficiently large m , and is false outside the principal range for r ≥ 4 , proved by Gruslys, Letzter and Morrison. Until now, it is still open to characterize the maximisers of the hypergraph Lagrangian outside the principal range for r ≥ 4. In this paper, we study the conjecture outside the principal range. We determine the smallest number of edges for which the conjecture is false, and also partially characterize the maximisers of the Lagrangian. [ABSTRACT FROM AUTHOR]

The Graph-Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. In most applications, we need an upper bound for the Graph-Lagrangian of a hypergraph. Frankl and Füredi conjectured that the $${r}$$ -graph with $$m$$ edges formed by taking the first $$\textit{m}$$ sets in the colex ordering of the collection of all subsets of $${\mathbb N}$$ of size $${r}$$ has the largest Graph-Lagrangian of all $$r$$ -graphs with $$m$$ edges. In this paper, we show that the largest Graph-Lagrangian of a class of left-compressed $$3$$ -graphs with $$m$$ edges is at most the Graph-Lagrangian of the $$\mathrm 3 $$ -graph with $$m$$ edges formed by taking the first $$m$$ sets in the colex ordering of the collection of all subsets of $${\mathbb N}$$ of size $${3}$$ . [ABSTRACT FROM AUTHOR]