# 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:
(1)
the density of numbers $$n$$ for which $$R=0$$;
(2)
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
(1)
the density of numbers for which $$R=0$$ is $$2-\sqrt{2}$$;
(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$$.
##### MSC:
 05C35 Extremal problems in graph theory 05C07 Vertex degrees 11K06 General theory of distribution modulo $$1$$
Full Text: