Many Cliques in Bounded-Degree Hypergraphs

DOI10.1137/22M1507565zbMATH Open1519.05123arXiv2207.02336OpenAlexW4384154330MaRDI QIDQ6170441FDOQ6170441

Authors: Rachel Kirsch, Jamie Radcliffe 

Publication date: 10 August 2023

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• On a packing and covering problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Families of finite sets with minimum shadows
• Title not available (Why is that?)
• The maximum number of complete subgraphs in a graph with given maximum degree
• Maximizing the number of independent sets of a fixed size
• Title not available (Why is that?)
• A Kruskal-Katona type theorem for graphs
• On the maximum number of cliques in a graph
• Face vectors of flag complexes
• Many \(T\) copies in \(H\)-free graphs
• The maximum number of complete subgraphs of fixed size in a graph with given maximum degree
• Extremal problems for finite sets
• Many cliques with few edges
• The maximum number of triangles in a graph of given maximum degree
• 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
• Many cliques with few edges and bounded maximum degree
• Many triangles with few edges
• A simple proof of the Gan-Loh-Sudakov conjecture

Cited In (8)

• Shadow ratio of hypergraphs with bounded degree
• Many cliques with few edges
• Title not available (Why is that?)
• 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)