On a refinement of the Ahlswede–Katona Theorem

Jianfeng Hou, Xizhi Liu, Yixiao Zhang · 2025

Read On a refinement of the Ahlswede–Katona Theorem by Jianfeng Hou, Xizhi Liu, Yixiao Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-19681.txt.

Introduction

Jianfeng Hou, Xizhi Liu, and Yixiao Zhang refine a classical theorem of Ahlswede and Katona about small patterns inside graphs. The original theorem fixes the maximum possible density of the two-edge star, a vertex joined to two others, in any graph with a given edge density. The question belongs to extremal graph theory, which asks how much of a pattern a graph can hold under constraints.

Motivated by applications to hypergraph Turán problems, the authors add an assumption: the graph contains a large independent set whose vertices all have high degree. Under that extra structure they establish a sharper version of the Ahlswede-Katona result. The refinement gives Turán-type arguments a stronger tool for controlling star densities.

Catalog record

CREATORJianfeng Hou, Xizhi Liu, Yixiao Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-19681

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On a refinement of the Ahlswede–Katona Theorem Jianfeng Hou, Xizhi Liu, Yixiao Zhang Abstract A classical theorem of Ahlswede and Katona [ AK78 ] determines the maximum density of the 2 2 -edge star in a graph with a given edge density. Motivated by its application in hypergraph Turán problems, we establish a refinement of their result under the additional assumption that the graph contains a large independent set in which every vertex has high degree. Keywords: the Ahlswede–Katona Theorem, counting stars, the first Zagreb index MSC2020: 05C35, 05D05, 05C07 1 Introduction 1.1 Definitions and main results We identify a graph F with its edge set, and use V(F) to denote its vertex set. The number of edges in F is denoted by |F| . Given integers n and m with m\leq\binom{n}{2} , let \mathcal{G}(n,m) be the collection of all graphs on n vertices with exactly m edges. For graphs F and G , let N(F,G) denote the number of subgraphs of G that are isomorphic to F . A classical problem in extremal graph theory is to determine the maximum possible value of N(F,G) when G\in\mathcal{G}(n,m) . One of the earliest result on this topic is the seminal Kruskal–Katona theorem [ Kru63 , Kat68 ] , which determines the maximum number of K_{\ell} , the complete graph on \ell vertices, in a graph with a prescribed number of vertices and edges. In this work, we focus on the case F=S_{2} , the star with two edges (also known as a cherry). We first introduce two classes of graphs. Let n and m be integers satisfying m\leq\binom{n}{2} . Write m=\binom{k}{2}+\ell , with k and \ell are nonnegative integers with \ell\leq k-1 . The quasi-clique C(n,m) is the graph on vertex set [n] with edge set \displaystyle\binom{[k]}{2}\cup\big\{\{i,k+1\}\colon i\in[\ell]\big\}. The quasi-star S(n,m) is the graph on vertex set [n] , defined as the complement of C\left(n,\binom{n}{2}-m\right) . The classical theorem of Ahlswede–Katona [ AK78 ] is stated as follows. Theorem 1.1 (Ahlswede–Katona [ AK78 ] ) . Let n and m be integers satisfying m\leq\binom{n}{2} . Suppose that G\in\mathcal{G}(n,m) . Then \displaystyle N(S_{2},G)\leq\max\big\{N\big(S_{2},S(n,m)\big),~N\big(S_{2},C(n,m)\big)\big\}. The extension of the Ahlswede–Katona Theorem to S_{\ell} with \ell\geq 3 , the star with \ell edges was achieved asymptotically only recently by Reiher–Wagner [ RW18 ] (see also Cairncross–Mubayi [ CM25 ] for related remarks). In this work, we focus on the asymptotic behavior of N(S_{2},G) . Given a graph G on n vertices, we define its edge density \rho(G) and its S_{2} -density (or cherry density ) \rho(S_{2},G) by \displaystyle\rho(G)\coloneqq\frac{|G|}{\binom{n}{2}}\quad\text{and}\quad\rho(S_{2},G)\coloneqq\frac{N(S_{2},G)}{3\binom{n}{3}}. The asymptotic version of Theorem 1.1 is as follows. Suppose that G is a graph on n vertices with edge density x\in[0,1] . Then \displaystyle\rho(S_{2},G) \displaystyle\leq\max\big\{2x-1+(1-x)^{3/2},~x^{3/2}\big\}+o(1) \displaystyle=o(1)+\begin{cases}2x-1+(1-x)^{3/2},&\quad\text{if}\quad x\in\left[0,\tfrac{1}{2}\right],\\ x^{3/2},&\quad\text{if}\quad x\in\left[\tfrac{1}{2},1\right].\end{cases} Note that for x\in\left[\tfrac{1}{2},1\right] , the bound x^{3/2} is asymptotically attained by the quasi-clique construction. Observe that this construction does not contain a large independent set in which every vertex has a large degree. This motivates us to study the following refinement of Theorem 1.1 . Let G be a graph. We use d_{G}(v) to denote the degree of a vertex v in G . For every set S\subseteq V(G) , let \displaystyle\delta_{G}(S)\coloneqq\min\left\{d_{G}(v)\colon v\in S\right\}. Let n,m,\ell,k be nonnegative integers with m\leq\binom{n}{2} and k\ell\leq m . Define \mathcal{G}(n,m,\ell,k) to be the family of graphs G\in\mathcal{G}(n,m) for which there exists an independent set I of size \ell in G such that \delta_{G}(I)\geq k , that is, \mathcal{G}(n,m,\ell,k)\\ \coloneqq\left\{G\in\mathcal{G}(n,m)\colon\text{$G$ contains an independent set $I$ with $|I|\geq\ell$ and $\delta_{G}(I)\geq k$}\right\}. Problem 1.2 . Let n,m,\ell,k be nonnegative integers with m\leq\binom{n}{2} and k\ell\leq m . Determine \displaystyle\max\left\{N(S_{2},G)\colon G\in\mathcal{G}(n,m,\ell,k)\right\}. Another motivation for considering Problem 1.2 comes from its relevance to the study of hypergraph Turán problems in the \ell_{2} -norm, such as [ HLZ25 ] . Since we are interested in the asymptotic behavior of the solution to Problem 1.2 , for real numbers \rho,\alpha,\beta\in[0,1] , define \displaystyle I(S_{2},\rho,\alpha,\beta)\coloneqq\limsup_{n\to\infty}\left\{\rho(S_{2},G)\colon G\in\mathcal{G}\big(n,\rho\tbinom{n}{2},\alpha n,\beta n\big)\right\}. Write m=k\ell+\binom{a}{2}+b , where a and b are nonnegative integers with b\in[0,a-1] . Let G_{1}(n,m,\ell,k) be the graph with vertex set [n] obtained as follows: (i) place a complete graph on vertex set [a] , (ii) place a k\times\ell complete bipartite graph with parts [k] and [n-\ell+1,n] , (iii) connect the vertex a+1 to all vertices in [b] . Write m=a\ell+\binom{a}{2}+b , where a and b are integers with b\in[0,a+\ell-1] . Let G_{2}(n,m,\ell,k) be the graph with vertex set [n] obtained as follows: (i) place a complete graph on vertex set [a] , (ii) place an a\times\ell complete bipartite graph with parts [a] and [a+1,a+\ell] , (iii) connect the vertex a+\ell+1 to all vertices in [b] . The constructions S(n,m) , G_{1}(n,m,\ell,k) , and G_{2}(n,m,\ell,k) provide the following lower bounds for I(S_{2},\rho,\alpha,\beta) , respectively. Fact 1.3 . Let \rho,\alpha,\beta\in[0,1] be real numbers with \rho\geq 2\alpha\beta+\beta^{2} . Then I(S_{2},\rho,\alpha,\beta)\\ \geq\max\left\{2\rho-1+(1-\rho)^{3/2},~\alpha^{2}\beta+\beta^{2}\alpha+\rho\sqrt{\rho-2\alpha\beta},~\alpha^{3}+(\rho-\alpha^{2})\sqrt{\rho+\alpha^{2}}\right\}. The main results of this work are as follows. Theorem 1.4 . Suppose that \rho\in\left[\frac{17}{25},\frac{7}{10}\right] and \alpha\in\left[\frac{17}{100},\frac{23}{100}\right] . Then \displaystyle I(S_{2},\rho,\alpha,\alpha)=\alpha^{3}+(\rho-\alpha^{2})\sqrt{\rho+\alpha^{2}}. Theorem 1.5 . Suppose that \rho\in\left[\frac{17}{25},\frac{7}{10}\right] and \alpha\in\left[\frac{1}{3},\frac{2}{5}\right] . Then \displaystyle I\left(S_{2},\rho,\alpha,\tfrac{1}{5}\right)=\max\left\{2\rho-1+(1-\rho)^{3/2},~\alpha^{3}+(\rho-\alpha^{2})\sqrt{\rho+\alpha^{2}}\right\}. 1.2 Counting cherries in bipartite graphs In this subsection, we consider the problem of maximizing the number of copies of S_{2} in an r\times s bipartite graph with a given number of edges. Let r,s,m be nonnegative integers with m\leq rs and r\geq s . Write m=pr+q , where p and q are nonnegative integers with q\in[0,r-1] . Define B(r,s,m) as the bipartite graph with two parts U=\{u_{1},\ldots,u_{r}\} and W=\{w_{1},\ldots,w_{s}\} and with edge set \displaystyle\big\{\{u_{i},w_{j}\}\colon(i,j)\in[r]\times[p]\big\}\cup\big\{\{u_{i},w_{p+1}\}\colon i\in[q]\big\}. In the same paper [ AK78 ] , Ahlswede–Katona proved the following result for bipartite graphs. Theorem 1.6 (Ahlswede–Katona [ AK78 ] ) . Let r,s,m be nonnegative integers with m\leq rs and r\geq s . Suppose that G is an r\times s bipartite graph with m edges. Then \displaystyle N(S_{2},G)\leq N\big(S_{2},B(r,s,m)\big). Let r,s,\ell,k,m be integers with r\geq\ell , s\geq k , and k\ell\leq m\leq rk . Write m=k\ell+p(r-\ell)+q , where p and q are nonnegative integers with q\in[0,r-\ell-1] . Define B_{1}(r,s,m,\ell,k) as the bipartite graph with parts U=\{u_{1},\ldots,u_{r}\} and W=\{w_{1},\ldots,w_{s}\} , and with edge set: (i) \big\{\{u_{i},w_{j}\}\colon(i,j)\in[r]\times[p]\big\} , (ii) \big\{\{u_{i},w_{p+1}\}\colon i\in[\ell+q]\big\} , and (iii) \big\{\{u_{i},w_{j}\}\colon(i,j)\in[\ell]\times[p+2,k]\big\} . Write m=k\ell+pk+q , where p and q are nonnegative integers with q\in[0,k-1] . Define B_{2}(r,s,m,\ell,k) as the bipartite graph with parts U=\{u_{1},\ldots,u_{r}\} and W=\{w_{1},\ldots,w_{s}\} , and with edge set \displaystyle\big\{\{u_{i},w_{j}\}\colon(i,j)\in[\ell+p]\times[k]\big\}\cup\big\{\{u_{\ell+p+1},w_{i}\}\colon i\in[q]\big\}. Theorem 1.7 . Let r,s,\ell,k,m be integers with r\geq s , \ell\geq k , r\geq\ell , s\geq k , and k\ell\leq m\leq rs . Let G=G[U,W] be an r\times s bipartite graph with m edges. Suppose that there exists a subset I\subseteq U with |I|=\ell and \delta_{G}(I)\geq k . Then \displaystyle N(S_{2},G)\leq\begin{cases}N\big(S_{2},B_{1}(r,s,m,\ell,k)\big),&\quad\text{if}\quad m\leq rk~\text{and}~k+\ell\leq r,\\[5.0pt] N\big(S_{2},B_{2}(r,s,m,\ell,k)\big),&\quad\text{if}\quad m\leq rk~\text{and}~k+\ell>r,\\[5.0pt] N\big(S_{2},B(r,s,m)\big),&\quad\text{if}\quad m\geq rk.\end{cases} An argument analogous to that in the proof of Theorem 1.7 yields the following result. Theorem 1.8 . Let r,s,\ell,k,m be integers with r\geq s , \ell\geq k , r\geq\ell , s\geq k , and k\ell\leq m\leq rs . Let G=G[U,W] be an r\times s bipartite graph with m edges. Suppose that there exists a subset I\subseteq W with |I|=k and \delta_{G}(I)\geq\ell . Then \displaystyle N(S_{2},G)\leq\begin{cases}N\big(S_{2},B_{1}(r,s,m,\ell,k)\big),&\quad\text{if}\quad m\leq rk~\text{and}~k+\ell\leq r,\\[5.0pt] N\big(S_{2},B_{2}(r,s,m,\ell,k)\big),&\quad\text{if}\quad m\leq rk~\text{and}~k+\ell>r,\\[5.0pt] N\big(S_{2},B(r,s,m)\big),&\quad\text{if}\quad m\geq rk.\end{cases} This paper is organized as follows. Section 2 introduces some definitions and preliminary results. In Section 3 ,

Read the complete text