Search

Abstract Let θ 3 , 4 denote the graph consisting of three internally disjoint paths of four edges with the same pair of endpoints. In this paper, we give a lower bound of order n 5 / 4 on the greatest number of edges of any n -vertex θ 3 , 4 -free graph, matching an earlier upper bound by Faudree and Simonovits up to an absolute constant factor. The construction is algebraic in nature, arising from equations over finite fields, and is perhaps some evidence that the Turán Number for the octagon is also of order n 5 / 4. [ABSTRACT FROM AUTHOR]

Abstract: We prove that the maximum number of edges in a k-uniform hypergraph on n vertices containing no 2-regular subhypergraph is if is even and n is sufficiently large. Equality holds only if all edges contain a specific vertex v. For odd k we conjecture that this maximum is , with equality only for the hypergraph described above plus a maximum matching omitting v. [Copyright &y& Elsevier]

Abstract: A cycle in a hypergraph is an alternating cyclic sequence of distinct edges and vertices such that for all i modulo k. In this paper, we determine the maximum number of edges in hypergraphs on n vertices containing no even cycles. [Copyright &y& Elsevier]

Corradi and Hajnal proved that a graph of order at least 3k and minimum degree at least 2k contains k vertex-disjoint cycles. Ha¨ggkvist subsequently conjectured that a sufficiently large graph of minimum degree at least four contains two vertex-disjoint cycles of the same length. We prove that this conjecture is correct. In doing so, we give a short proof of the known result that if k>2, there is an integer nk such that any graph of order at least nk and minimum degree at least 2k contains k vertex-disjoint cycles of the same length. [Copyright &y& Elsevier]

The expansion G + of a graph G is the 3-uniform hypergraph obtained from G by enlarging each edge of G with a vertex disjoint from V ( G ) such that distinct edges are enlarged by distinct vertices. Let ex r ( n , F ) denote the maximum number of edges in an r -uniform hypergraph with n vertices not containing any copy of F . The authors [10] recently determined ex 3 ( n , G + ) when G is a path or cycle, thus settling conjectures of Füredi–Jiang [8] (for cycles) and Füredi–Jiang–Seiver [9] (for paths). Here we continue this project by determining the asymptotics for ex 3 ( n , G + ) when G is any fixed forest. This settles a conjecture of Füredi [7] . Using our methods, we also show that for any graph G , either ex 3 ( n , G + ) ≤ ( 1 2 + o ( 1 ) ) n 2 or ex 3 ( n , G + ) ≥ ( 1 + o ( 1 ) ) n 2 , thereby exhibiting a jump for the Turán number of expansions. [ABSTRACT FROM AUTHOR]

The Erdős–Gallai Theorem states that for k ≥ 2 , every graph of average degree more than k − 2 contains a k -vertex path. This result is a consequence of a stronger result of Kopylov: if k is odd, k = 2 t + 1 ≥ 5 , n ≥ ( 5 t − 3 ) / 2 , and G is an n -vertex 2-connected graph with at least h ( n , k , t ) : = ( k − t 2 ) + t ( n − k + t ) edges, then G contains a cycle of length at least k unless G = H n , k , t : = K n − E ( K n − t ) . In this paper we prove a stability version of the Erdős–Gallai Theorem: we show that for all n ≥ 3 t > 3 , and k ∈ { 2 t + 1 , 2 t + 2 } , every n -vertex 2-connected graph G with e ( G ) > h ( n , k , t − 1 ) either contains a cycle of length at least k or contains a set of t vertices whose removal gives a star forest. In particular, if k = 2 t + 1 ≠ 7 , we show G ⊆ H n , k , t . The lower bound e ( G ) > h ( n , k , t − 1 ) in these results is tight and is smaller than Kopylov's bound h ( n , k , t ) by a term of n − t − O ( 1 ) . [ABSTRACT FROM AUTHOR]

A convex geometric hypergraph or cgh consists of a family of subsets of a strictly convex set of points in the plane. There are eight pairwise nonisomorphic cgh's consisting of two distinct triangles. These were studied at length by Braß [6] (2004) and by Aronov, Dujmović, Morin, Ooms, and da Silveira [2] (2019). We determine the extremal functions exactly for seven of the eight configurations. The above results are about cyclically ordered hypergraphs. We extend some of them for triangle systems with vertices from a non-convex set. We also solve problems posed by P. Frankl, Holmsen and Kupavskii [15] (2020), in particular, we determine the exact maximum size of an intersecting family of triangles whose vertices come from a set of n points in the plane. [ABSTRACT FROM AUTHOR]

Abstract: For an odd integer k, let denote the family of all odd cycles of length at most k and let denote the family of all odd cycles. Erdős and Simonovits [10] conjectured that for every family of bipartite graphs, there exists k such that as . This conjecture was proved by Erdős and Simonovits when , and for certain families of even cycles in [14]. In this paper, we give a general approach to the conjecture using Scott's sparse regularity lemma. Our approach proves the conjecture for complete bipartite graphs and : we obtain more strongly that for any odd , and we show further that the extremal graphs can be made bipartite by deleting very few edges. In contrast, this formula does not extend to triangles – the case – and we give an algebraic construction for odd of -free -free graphs with substantially more edges than an extremal -free bipartite graph on n vertices. Our general approach to the Erdős–Simonovits conjecture is effective based on some reasonable assumptions on the maximum number of edges in an m by n bipartite -free graph. [Copyright &y& Elsevier]