pith. sign in

arxiv: 2606.02546 · v1 · pith:QI6JBSIXnew · submitted 2026-06-01 · 🧮 math.CO

Abundance of Unique Subhypergraphs

classification 🧮 math.CO
keywords uniquevertexgraphcontainsdeltagraphshypergraphssubhypergraph
0
0 comments X
read the original abstract

Given $k$-uniform hypergraphs $G$ and $H$, we say that $G$ is a unique subhypergraph of $H$ if $H$ contains exactly one subhypergraph isomorphic to $G$. For an $n$-vertex $k$-graph $H$, let $f_k(H)$ be the number of non-isomorphic unique subhypergraphs of $H$, normalized by $2^{\binom n k}/n!$, and let $f_k(n)$ be the maximum of $f_k(H)$ over all $n$-vertex $k$-graphs $H$. In the graph case $k=2$, Erd\H{o}s asked whether there exists a constant $\delta>0$ such that $f_2(n)>\delta$ for all $n$, offering \$100 for a proof and \$25 for a disproof. Recently, Brada\v{c} and Christoph answered this question in the negative,, proving that $f_2(n)$ tends to $0$, or equivalently that no $n$-vertex graph contains a positive proportion of all $n$-vertex graphs as unique subgraphs. In this paper we show that the situation is fundamentally different for $k$-uniform hypergraphs with $k\ge3$. In particular, for every fixed integer $k\ge 3$, we prove that $\liminf_{n\to\infty} f_k(n) \ge 2/9$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.