Search

A graph is F-saturated if it does not contain F as a subgraph but the addition of any edge creates a copy of F. We prove that for s ≥ 3 and t ≥ 2, the minimum number of copies of K1,t in a Ks-saturated graph is Î,(nt/2). More precise results are obtained in the case of K1,2, where determining the minimum number of K1,2's in a K3-saturated graph is related to the existence of Moore graphs. We prove that for s ≥ 4 and t ≥ 3, an n-vertex Ks-saturated graph must have at least Cnt/5+8/5 copies of K2,t, and we give an upper bound of O(nt/2+3/2). These results answer a question of Chakraborti and Loh on extremal Ks-saturated graphs that minimize the number of copies of a fixed graph H. General estimates on the number of Ka,b's are also obtained, but finding an asymptotic formula for the number Ka,b's in a Ks-saturated graph remains open. [ABSTRACT FROM AUTHOR]

In this paper we initiate a systematic study of the Turán problem for edge-ordered graphs. A simple graph is called edge-ordered if its edges are linearly ordered. This notion allows us to study graphs (and in particular their maximum number of edges) when a subgraph is forbidden with a specific edge-order but the same underlying graph may appear with a different edge-order. We prove an Erdős-Stone-Simonovits-type theorem for edge-ordered graphs—we identify the relevant parameter for the Turán number of an edge-ordered graph and call it the order chromatic number. We establish several important properties of this parameter. We also study Turán numbers of edge-ordered paths, star forests and the cycle of length four. We make strong connections to Davenport-Schinzel theory, the theory of forbidden submatrices, and show an application in discrete geometry. [ABSTRACT FROM AUTHOR]

A graph is F-saturated if it is F-free but the addition of any edge creates a copy of F. In this paper we study the function sat(n, H, F) which is the minimum number of copies of H that an F-saturated graph on n vertices may contain. This function is a natural saturation analogue of Alon and Shikhelman's generalized Turán problem, and letting H = K2 recovers the well-studied saturation function. We provide a first investigation into this general function focusing on the cases where the host graph is either Ks or Ck-saturated. Some representative interesting behavior is: (a) For any natural number m, there are graphs H and F such that sat(n, H, F) = Θ(nm). (b) For many pairs k and l, we show sat(n, Cl, Ck) = 0. In particular, we prove that there exists a triangle-free Ck-saturated graph on n vertices for any k > 4 and large enough n. (c) sat(n, K3, K4) = n -2, sat(n, C4, K4) ~ n²/2, and sat(n, C6, K5 ~ n³. We discuss several intriguing problems that remain unsolved. [ABSTRACT FROM AUTHOR]

Erdős and Moser raised the question of determining the maximum number of maximal cliques or, equivalently, the maximum number of maximal independent sets in a graph on n vertices. Since then there has been a lot of research along these lines. A k‐dominating independent set is an independent set D such that every vertex not contained in D has at least k neighbors in D. Let mik(n) denote the maximum number of k‐dominating independent sets in a graph on n vertices, and let ζk≔limn→∞mik(n)n. Nagy initiated the study of mik(n). In this study, we disprove a conjecture of Nagy using a graph product construction and prove that for any even k we have 1.489≈369≤ζkk. We also prove that for any k≥3 we have ζkk≤2.053(1/(1.053+1∕k))<1.98, improving the upper bound of Nagy. [ABSTRACT FROM AUTHOR]

We prove that the maximum number of triangles in a C5‐free graph on n vertices is at most 122(1+o(1))n3∕2, improving an estimate of Alon and Shikhelman. [ABSTRACT FROM AUTHOR]

In this note we asymptotically determine the maximum number of hyperedges possible in an r -uniform, connected n -vertex hypergraph without a Berge path of length k , as n and k tend to infinity. We show that, unlike in the graph case, the multiplicative constant is smaller with the assumption of connectivity. [ABSTRACT FROM AUTHOR]

Given a graph H and a set of graphs F , let e x (n , H , F) denote the maximum possible number of copies of H in an F -free graph on n vertices. We investigate the function e x (n , H , F) , when H and members of F are cycles. Let C k denote the cycle of length k and let C k = { C 3 , C 4 , ... , C k }. We highlight the main results below. (i) We show that e x (n , C 2 l , C 2 k) = Θ (n l) for any l , k ≥ 2. Moreover, in some cases we determine it asymptotically: We show that e x (n , C 4 , C 2 k) = (1 + o (1)) (k − 1) (k − 2) 4 n 2 and that the maximum possible number of C 6 's in a C 8 -free bipartite graph is n 3 + O (n 5 / 2). (ii) Erdős's Girth Conjecture states that for any positive integer k , there exist a constant c > 0 depending only on k , and a family of graphs { G n } such that | V (G n) | = n , | E (G n) | ≥ c n 1 + 1 / k with girth more than 2 k. Solymosi and Wong [37] proved that if this conjecture holds, then for any l ≥ 3 we have e x (n , C 2 l , C 2 l − 1) = Θ (n 2 l / (l − 1)). We prove that their result is sharp in the sense that forbidding any other even cycle decreases the number of C 2 l 's significantly: For any k > l , we have e x (n , C 2 l , C 2 l − 1 ∪ { C 2 k }) = Θ (n 2). More generally, we show that for any k > l and m ≥ 2 such that 2 k ≠ m l , we have e x (n , C m l , C 2 l − 1 ∪ { C 2 k }) = Θ (n m). (iii) We prove e x (n , C 2 l + 1 , C 2 l) = Θ (n 2 + 1 / l) , provided a stronger version of Erdős's Girth Conjecture holds (which is known to be true when l = 2 , 3 , 5). This result is also sharp in the sense that forbidding one more cycle decreases the number of C 2 l + 1 's significantly: More precisely, we have e x (n , C 2 l + 1 , C 2 l ∪ { C 2 k }) = O (n 2 − 1 l + 1 ) , and e x (n , C 2 l + 1 , C 2 l ∪ { C 2 k + 1 }) = O (n 2) for l > k ≥ 2. (iv) We also study the maximum number of paths of given length in a C k -free graph, and prove asymptotically sharp bounds in some cases. [ABSTRACT FROM AUTHOR]

A classical result of Bondy and Simonovits in extremal graph theory states that if a graph on n vertices contains no cycle of length 2 k then it has at most O ( n 1 + 1 ∕ k ) edges. However, matching lower bounds are only known for k = 2 , 3 , 5 . In this paper we study ordered variants of this problem and prove some tight estimates for a certain class of ordered cycles that we call bordered cycles . In particular, we show that the maximum number of edges in an ordered graph avoiding bordered cycles of length at most 2 k is Θ ( n 1 + 1 ∕ k ) . Strengthening the result of Bondy and Simonovits in the case of 6-cycles, we also show that it is enough to forbid these bordered orderings of the 6-cycle to guarantee an upper bound of O ( n 4 ∕ 3 ) on the number of edges. [ABSTRACT FROM AUTHOR]

A well-known theorem of Erdős and Gallai (1959) [ 1 ] asserts that a graph with no path of length k contains at most 1 2 ( k − 1 ) n edges. Recently Győri et al. (2016) gave an extension of this result to hypergraphs by determining the maximum number of hyperedges in an r -uniform hypergraph containing no Berge path of length k for all values of r and k except for k = r + 1 . We settle the remaining case by proving that an r -uniform hypergraph with more than n edges must contain a Berge path of length r + 1 . [ABSTRACT FROM AUTHOR]