Small dense subgraphs of a graph

DOI10.1137/15M1007598MaRDI QIDQ2957688zbMATH OpenOpenAlexFDO

Authors Tao Jiang, Andrew Newman

Publication date 27 January 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cubeextremal functionTurán exponentTurán number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: Given a family $calF$ of graphs, and a positive integer $n$, the Tur'an number $ex(n,calF)$ of $calF$ is the maximum number of edges in an $n$-vertex graph that does not contain any member of $calF$ as a subgraph. The order of a graph is the number of vertices in it. In this paper, we study the Tur'an number of the family of graphs with bounded order and high average degree. For every real $dgeq2$ and positive integer $mgeq2$, let ${calF}_{d,m}$ denote the family of graphs on at most $m$ vertices that have average degree at least $d$. It follows from the ErdH{o}s-R'enyi bound that $ex(n,{calF}_{d,m})=Omega(n^{2-frac2d+fraccdm})$, for some positive constant $c$. Verstra"ete asked if it is true that for each fixed $d$ there exists a function $epsilo{n}_d(m)$ that tends to $0$ as $moinfty$ such that $ex(n,{calF}_{d,m})=O(n^{2-frac2d+epsilo{n}_d(m)})$. We answer Verstra"ete's question in the affirmative whenever $d$ is an integer. We also prove an extension of the cube theorem on the Tur'an number of the cube $Q_3$, which partially answers a question of Pinchasi and Sharir.

Recommendations

• Extremal graphs with bounded densities of small subgraphs
• On Turán densities of small triple graphs
• scientific article; zbMATH DE number 1990667
• Generalized Turán densities in the hypercube
• On two Turán Numbers

Cites work

• An approximate version of Sidorenko's conjecture
• Dense graphs without 3-regular subgraphs
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3333193 (Why is no real title available?)
• On graphs that do not contain the cube and related problems
• On the combinatorial problems which I would most like to see solved
• Parity check matrices and product representations of squares
• Rainbow Turán problem for even cycles
• Regular subgraphs of dense graphs
• Set families with a forbidden induced subposet
• Set families with a forbidden subposet
• The history of degenerate (bipartite) extremal graph problems
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(11)

• Some small sized spanning subgraphs of a hypercube
• The Turán number of blow-ups of trees
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles
• Detecting and Characterizing Small Dense Bipartite-Like Subgraphs by the Bipartiteness Ratio Measure
• Small dense subgraphs of polarity graphs and the extremal number for the 4-cycle
• Extremal graphs with bounded densities of small subgraphs
• On Turán exponents of bipartite graphs
• Tree-Degenerate Graphs and Nested Dependent Random Choice
• Extremal graphs for the odd prism
• Spectral extremal problem for the odd prism

This page was built for publication: Small dense subgraphs of a graph

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