Search

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]

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]

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]

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]