# Counting copies of a fixed subgraph in F-free graphs

@article{Gerbner2019CountingCO, title={Counting copies of a fixed subgraph in F-free graphs}, author={D{\'a}niel Gerbner and Cory Palmer}, journal={Eur. J. Comb.}, year={2019}, volume={82} }

Abstract Fix graphs F and H and let ex ( n , H , F ) denote the maximum possible number of copies of the graph H in an n -vertex F -free graph. The systematic study of this function was initiated by Alon and Shikhelman [J. Comb. Theory, B. 121 (2016)]. In this paper, we give new general bounds concerning this generalized Turan function. We also determine ex ( n , P k , K 2 , t ) (where P k is a path on k vertices) and ex ( n , C k , K 2 , t ) asymptotically for every k and t . For example, it… Expand

#### 53 Citations

The maximum number of cliques in graphs without large matchings

- 2018

Let F be a family of graphs. A graph G is called F-free if for any F ∈ F , there is no subgraph of G isomorphic to F . The Turán number ex(n,F) is defined to be the maximum number of edges in an… Expand

C O ] 1 S ep 2 02 0 The generalized Turán number of spanning linear forests ∗

- 2020

Let F be a family of graphs. A graph G is called F-free if for any F ∈ F , there is no subgraph of G isomorphic to F . Given a graph T and a family of graphs F , the generalized Turán number of F is… Expand

Asymptotics for the Turán number of Berge-K2, t

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 2019

The bounds improve the results of Gerbner and Palmer [18] , Furedi and Ozkahya [15] , Timmons [37] , and provide a new proof of a result of Jiang and Ma [26] . Expand

On Tur\'an-good graphs

- Mathematics
- 2020

For graphs H and F , the generalized Turán number ex(n,H,F ) is the largest number of copies of H in an F -free graph on n vertices. We say that H is F -Turán-good if ex(n,H,F ) is the number of… Expand

Generalized rainbow Turán problems

- 2019

Alon and Shikhelman [J. Comb. Theory, B. 121 (2016)] initiated the systematic study of the following generalized Turán problem: for fixed graphs H and F and an integer n, what is the maximum number… Expand

The Tur\'an number of Berge book hypergraphs

- Mathematics
- 2021

Given a graph G, a Berge copy of G is a hypergraph obtained by enlarging the edges arbitrarily. Győri in 2006 showed that for r = 3 or r = 4, an r-uniform n-vertex Berge triangle-free hypergraph has… Expand

A note on the uniformity threshold for Berge hypergraphs

- Mathematics
- 2021

A Berge copy of a graph is a hypergraph obtained by enlarging the edges arbitrarily. Grósz, Methuku and Tompkins in 2020 showed that for any graph F , there is an integer r0 = r0(F ), such that for… Expand

Some results on k-Turán-good graphs

- Computer Science, Mathematics
- Discret. Math.
- 2021

This paper constructs some new classes of k-Turán-good graphs and proves that P4 and P5 are k- Turán- good for k ≥ 4 and 4 respectively. Expand

On the number of $k$-gons in finite projective planes

- Mathematics
- 2021

Let Π be a projective plane of order n and ΓΠ be its Levi graph (the point-line incidence graph). For fixed k ≥ 3, let c2k(ΓΠ) denote the number of 2k-cycles in ΓΠ. In this paper we show that c2k(ΓΠ)… Expand

A non-aligning variant of generalized Tur\'an problems

- Mathematics
- 2021

In the so-called generalized Turán problems we study the largest number of copies of H in an n-vertex F -free graph G. Here we introduce a variant, where F is not forbidden, but we restrict how… Expand

#### References

SHOWING 1-10 OF 60 REFERENCES

Many T copies in H-free graphs

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 2016

The general function of ex ( n, T, H) is investigated, focusing on the cases of triangles, complete graphs, complete bipartite graphs and trees, and improves (slightly) an estimate of Bollobas and Győri. Expand

Asymptotics for the Turán number of Berge-K2, t

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 2019

The bounds improve the results of Gerbner and Palmer [18] , Furedi and Ozkahya [15] , Timmons [37] , and provide a new proof of a result of Jiang and Ma [26] . Expand

Turán Problems and Shadows III: Expansions of Graphs

- Mathematics, Computer Science
- SIAM J. Discret. Math.
- 2015

This paper shows that this occurs when G is any bipartite graph with Turan number o(n ϕ ) where ϕ = 1+ √ 5 2 , and in particular this shows ex3(n, G + )= O(n 2 )w henG is the three-dimensional cube graph. Expand

On the maximal number of certain subgraphs inKr-free graphs

- Mathematics, Computer Science
- Graphs Comb.
- 1991

It is shown that in the class of allKr-free graphs withn vertices the complete balanced (r − 1)-partite graphTr−1(n) has the largest number of subgraphs isomorphic toKt (t < r),C4,K2,3. Expand

On complete subgraphs of different orders

- Mathematics
- 1976

Let S be a set and let { X 1 , …, X n } = be a family of distinct subsets of S . The intersection graph Ω( ) of has vertex set { X 1 , …, X n } and X i X j ( i ≠ j ) is an edge of Ω( ) if and only if… Expand

ON SOME PROBLEMS IN GRAPH THEORY , COMBINATORIAL ANALYSIS AND COMBINATORIAL NUMBER THEORY

- 2004

1. G(n) is a graph of n vertices and G(n ; e) is a graph of n vertices and e edges. Is it true that if every induced subgraph of a G(10n) of 5n vertices has more than 2n 2 edges then our G(10n)… Expand

Many H-Copies in Graphs with a Forbidden Tree

- Mathematics, Computer Science
- SIAM J. Discret. Math.
- 2019

It is shown that if $F$ is a tree then $\operatorname{ex}(n, H, F) = \Theta(n^r)$ for some integer $r = r(H,F)$, thus answering one of their questions. Expand

Problems and Results in Graph Theory and Combinatorial Analysis

- 1977

I published several papers with similar titles. One of my latest ones [13] (also see [16] and the yearly meetings at Boca Raton or Baton Rouge) contains, in the introduction, many references to my… Expand

A note on the maximum number of triangles in a C5-free graph

- Mathematics, Computer Science
- Electron. Notes Discret. Math.
- 2017

Abstract We prove that the maximum number of triangles in a C5-free graph on n vertices is at most 1 2 2 ( 1 + o ( 1 ) ) n 3 / 2 , improving an estimate of Alon and Shikhelman [Alon, N. and C.… Expand

A note on the maximum number of triangles in a C5-free graph

- Mathematics, Computer Science
- J. Graph Theory
- 2019

We prove that the maximum number of triangles in a C5-free graph on n vertices is at most [Formula presented](1+o(1))n3/2, improving an estimate of Alon and Shikhelman [Alon, N. and C. Shikhelman,… Expand