Many Cliques in Bounded-Degree Hypergraphs

DOI10.1137/22M1507565MaRDI QIDQ6170441zbMATH OpenOpenAlexFDO

Authors Rachel Kirsch, Jamie Radcliffe

Publication date 10 August 2023

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

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

zbMATH Keywords

enumerationhypergraphdegreecliquesextremal

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30) Hypergraphs (05C65)

Abstract: Recently Chase determined the maximum possible number of cliques of size $t$ in a graph on $n$ vertices with given maximum degree. Soon afterward, Chakraborti and Chen answered the version of this question in which we ask that the graph have $m$ edges and fixed maximum degree (without imposing any constraint on the number of vertices). In this paper we address these problems on hypergraphs. For $s$-graphs with $sge3$ a number of issues arise that do not appear in the graph case. For instance, for general $s$-graphs we can assign degrees to any $i$-subset of the vertex set with $1leiles-1$. We establish bounds on the number of $t$-cliques in an $s$-graph $mathcalH$ with $i$-degree bounded by $Delta$ in three contexts: $mathcalH$ has $n$ vertices; $mathcalH$ has $m$ (hyper)edges; and (generalizing the previous case) $mathcalH$ has a fixed number $p$ of $u$-cliques for some $u$ with $sleulet$. When $Delta$ is of a special form we characterize the extremal $s$-graphs and prove that the bounds are tight. These extremal examples are the shadows of either Steiner systems or packings. On the way to proving our uniqueness results, we extend results of F"uredi and Griggs on uniqueness in Kruskal-Katona from the shadow case to the clique case.

Recommendations

• Many cliques with few edges and bounded maximum degree
• On the maximum number of edges in hypergraphs with fixed matching and clique number
• Shadow ratio of hypergraphs with bounded degree
• scientific article; zbMATH DE number 3896979
• Generalized octahedra and cliques in intersection graphs of uniform hypergraphs

Cites work

• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• A Kruskal-Katona type theorem for graphs
• A simple proof of the Gan-Loh-Sudakov conjecture
• Extremal problems for finite sets
• Face vectors of flag complexes
• Families of finite sets with minimum shadows
• Many \(T\) copies in \(H\)-free graphs
• Many cliques with few edges
• Many cliques with few edges and bounded maximum degree
• Many triangles with few edges
• Maximizing the number of independent sets of a fixed size
• On a packing and covering problem
• On the maximum number of cliques in a graph
• Shadow ratio of hypergraphs with bounded degree
• Shadows of 3-uniform hypergraphs under a minimum degree condition
• The maximum number of cliques in hypergraphs without large matchings
• The maximum number of complete subgraphs in a graph with given maximum degree
• The maximum number of complete subgraphs of fixed size in a graph with given maximum degree
• The maximum number of triangles in a graph of given maximum degree

Cited in

(8)

• Shadow ratio of hypergraphs with bounded degree
• Many cliques with few edges
• scientific article; zbMATH DE number 3896979 (Why is no real title available?)
• Many cliques with few edges and bounded maximum degree
• A localized approach to generalized Turán problems
• A tale of stars and cliques
• Maximizing the density of \(K_t\)'s in graphs of bounded degree and clique number
• Coloring hypergraphs from random lists

This page was built for publication: Many Cliques in Bounded-Degree Hypergraphs

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