PreprintarXiv licencearXiv
On the distinct maximal-clique sizes in k-uniform hypergraphs
Abstract
Let g(n,k) be the maximum number of distinct sizes of maximal cliques in an n-vertex k-uniform hypergraph, and let f(n,k)=n−g(n,k). We determine the asymptotic order of f(n,k) for every fixed integer k≥ 3. Define L2(x)=max{2,log2(max{1,x})}, and, for j≥ 3, let Lj(x) be the least number of iterations of Lj−1 needed to reach a value at most $16$. We prove that f(n,k)=Θk(Lk(n)). In particular, f(n,3)=Θ(log*n), where log*n denotes the iterated logarithm. We also determine the asymptotic behaviour of the layered-tree threshold c(n,k) arising from Gao's insertion-tree method: c(n,k)=log2 Lk(n)+Ok(1). Consequently, f(n,k)=Θk (2c(n,k)). Our result gives a negative answer to Gao's question in the case k=3.
Related
BibTeX
@misc{yang2026distinct,
title = {{On the distinct maximal-clique sizes in $k$-uniform hypergraphs}},
author = {Jiabao Yang and Lixiang Yu and Leilei Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.27837},
eprint = {2607.27837},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.27837},
}
RIS
TY - UNPB
TI - On the distinct maximal-clique sizes in k-uniform hypergraphs
AU - Jiabao Yang
AU - Lixiang Yu
AU - Leilei Zhang
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2607.27837
UR - https://arxiv.org/abs/2607.27837
AB - Let g(n,k) be the maximum number of distinct sizes of maximal cliques in an n-vertex k-uniform hypergraph, and let f(n,k)=n−g(n,k). We determine the asymptotic order of f(n,k) for every fixed integer k≥ 3. Define L_2(x)=max{2,log_2(max{1,x})}, and, for j≥ 3, let L_j(x) be the least number of iterations of L_j−1 needed to reach a value at most $16$. We prove that f(n,k)=Θ_k(L_k(n)). In particular, f(n,3)=Θ(log^*n), where log^*n denotes the iterated logarithm. We also determine the asymptotic behaviour of the layered-tree threshold c(n,k) arising from Gao's insertion-tree method: c(n,k)=log_2 L_k(n)+O_k(1). Consequently, f(n,k)=Θ_k (2^c(n,k)). Our result gives a negative answer to Gao's question in the case k=3.
ER -