zbMATH — the first resource for mathematics

On a problem of Ahlswede and Katona. (English) Zbl 1224.05253
This work is motivated by a result of R. Ahlswede and G. O. H. Katona [Acta Math. Acad. Sci. Hung. 32, 97–120 (1978; Zbl 0386.05036)]. The issue is to maximize the value of \(p(G)=\sum_{v \in V(G)} {\text{deg}(v) \choose 2}\) if \(e(G)=N\) and \(v(G)=n\) are fixed. It was shown that either the quasi-complete graph \(C_n^N\) or the quasi-star graph \(S_n^N\) is the extremal graph for the function \(p\). \(C_n^N\) consists of a clique \(C\) of size \(a\), where \(N= {a \choose 2}+b\) (\(0 \leq b <a\)), a vertex connected to \(C\) by \(b\) edges and \(n-a-1\) isolated vertices. \(S_n^N\) is the complement of \(C_n^{{n \choose 2}-N}\). These two graphs are taking turns in that role; there exists a real number \(R\) such that \(S_n^N\) is extremal if \(0 \leq N \leq h - R\) and \(h \leq N \leq h + R\), while \(C_n^N\) is extremal if \(h -R \leq N \leq h\) and \(h + R \leq N \leq 2h\), where \(2h={n \choose 2}\). Still, the value of \(R\) remains quite unpredictable and two open questions are posed:
the density of numbers \(n\) for which \(R=0\);
the distribution of \(R/n\).
This paper solves both of these, and communicates that in fact B. M. Ábrego et al. [JIPAM, J. Inequal. Pure Appl. Math. 10, No. 3, Paper No. 64 (2009; Zbl 1182.05032)] also solve (1). The main theorem is that
the density of numbers for which \(R=0\) is \(2-\sqrt{2}\);
the distribution function \(D(x)\) of \(R/n\) is \(2(\sqrt{2}-1-x)/(\sqrt{2}-4x)\) on \(0 \leq x \leq 1-\sqrt{2}/2\), while \(D(x)=0\) for \(x < 0\) and \(D(x)=1\) for \(x > 1-\sqrt{2}/2\).
05C35 Extremal problems in graph theory
05C07 Vertex degrees
11K06 General theory of distribution modulo \(1\)
Full Text: DOI