The shifting method and generalized Turán number of matchings

DOI10.1016/J.EJC.2019.103057MaRDI QIDQ2297913zbMATH OpenOpenAlexFDO

Authors Jian Wang

Publication date 20 February 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.01832

zbMATH Keywords

Erdős and Gallai theorem

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Given two graphs $T$ and $F$, the maximum number of copies of $T$ in an $F$-free graph on $n$ vertices is called the generalized Tur'{a}n number, denoted by $ex(n,T,F)$. When $T=K_2$, it reduces to the classical Tur'{a}n number $ex(n,F)$. Let $M_k$ be a matching with $k$ edges and $K_{s,t}^{\ast }$ a graph obtained from $K_{s,t}$ by replacing the part of size $s$ by a clique of the same size. In this paper, we show that for any $sgeq2$ and $ngeq2k+1$, [ ex(n,K_s,M_{k+1})=maxleft{�inom{2k+1}{s}, �inom{k}{s}+(n-k)�inom{k}{s-1} ight}. ] For any $sgeq1$, $tgeq2$ and $ngeq2k+1$, [ ex(n,K_{s,t}^*,M_{k+1})=maxleft{�inom{2k+1}{s+t}�inom{s+t}{t}, �inom{k}{s}�inom{n-s}{t}+(n-k)�inom{k}{s+t-1}�inom{s+t-1}{t} ight}. ] Moreover, we also study the bipartite case of the problem. Let $e{x}_{bip}(n,T,F)$ be the maximum possible number of copies of $T$ in an $F$-free bipartite graph with each part of size $n$. We prove that for any $s,tgeq1$ and $ngeqk$, [ ex_{bip}(n,K_{s,t},M_{k+1})=left{ �egin{aligned} &�inom{k}{s}�inom{n}{t}+�inom{k}{t}�inom{n}{s}, & quad s eq t, &�inom{k}{s}�inom{n}{s},&quad s=t. end{aligned} ight. ] Our proof is mainly based on the shifting method.

Recommendations

• The generalized Turán number of spanning linear forests
• Generalized Turán problems for complete bipartite graphs
• Some sharp results on the generalized Turán numbers
• On generalized Turán number of two disjoint cliques
• Generalized Turán problems for \(K_{2,t}\)

Cites work

• A generalized Turán problem and its applications
• A method in graph theory
• Counting copies of a fixed subgraph in F-free graphs
• Generalized Turán problems for disjoint copies of graphs
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• Many \(T\) copies in \(H\)-free graphs
• On maximal paths and circuits of graphs
• On the maximum number of five-cycles in a triangle-free graph
• On the size of graphs with complete-factors
• Some sharp results on the generalized Turán numbers
• The maximum number of cliques in graphs without long cycles

Cited in

(32)

• Generalized Turán number of even linear forests
• The maximum number of stars in a graph without linear forest
• Further results on the generalized Turán number of spanning linear forests
• The generalized Turán number of spanning linear forests
• Turán numbers for hypergraph star forests
• Generalized Turán number for linear forests
• The maximum number of cliques in hypergraphs without large matchings
• The shifted Turán sieve method on tournaments. II
• The maximum number of copies of \(K_{r,s}\) in graphs without long cycles or paths
• The maximum spectral radius of graphs without spanning linear forests
• Many H-copies in graphs with a forbidden tree
• Maximum cliques in a graph without disjoint given subgraph
• Exact generalized Turán numbers for even linear forests
• Spectral radius and rainbow Hamilton paths of a graph
• A note on the stability results of the number of cliques in graphs with given matching number
• Turán numbers of general star forests in hypergraphs
• The Turán number of Berge-linear forests in hypergraphs
• A note on the generalized Turán number of star forests
• The maximum number of cliques in graphs that avoid vertex-disjoint copies of path of length two
• The maximum number of cliques in graphs with given fractional matching number and minimum degree
• A spectral generalized Erdős-Gallai theorem
• Maxima of the Q-index: forbidden rainbow Hamilton paths, matchings and linear forests
• Extremal problems for a matching and any other graph
• On the generalized Turán number of star forests
• Generalized Turán results for matchings
• Maximum number of cliques in \(\{C_{k_1}, C_{k_2}, C_{k_3}, \cdots \}\)-free graphs with \(6 = k_1 < k_2 < \cdots\) and \(k_{i+1} - k_i \leq 5\)
• The number of stars in a graph that forbids a matching and any graph
• Counting the maximum number of sunflowers in hypergraphs with given matching number
• Many cliques in graphs with bounded matching number and circumference
• Exact results for generalized Turán number of a linear forest and a clique
• Spectral radius, transversal Hamilton paths and cycles in bipartite graph families
• Generalized Turán number of matchings for connected graphs

This page was built for publication: The shifting method and generalized Turán number of matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2297913)