Celebrity vertices in graphs Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$, let $N(v) = \{w\in V:\{v,w\}\in E\}$ and let $\text{deg}(v) = |N(v)|$. Moreover, we set $L(v) = \{w\in N(v): \text{deg}(w) < \text{deg}(v)\}$, and we say that $v\in V$ is a celebrity if more than half of $v$'s neighbors have fewer neighbors than $v$ does, or more formally, if $$2\cdot |L(v)| > \text{deg}(v).$$
By $\text{Celeb}(G)$ we denote the set of celebrities of $G$.
A real number $r\in [0,1]$ is called a simultaneous celebrity bound if for every simple, finite, undirected graph $G=(V,E)$ we have
$$\text{Celeb}(G) \leq r\cdot |V|.$$
Obviously, $1$ is a simultaneous celebrity bound.
Question. If $S\subseteq [0,1]$ is the set of simultaneous celebrity bounds, what is the value of $\inf S$?
 A: The only bound is $r=1$. I will construct graphs below whose celebrity ratio is arbitrarily close to $1$.
Fix an arbitrarily large parameter $k$. The graph will have vertex set $V=V_0\cup V_1\cup\dots\cup V_k$, where all vertices in $V_i$ have degree $4k-2i+1$. Their neighbours will be distributed so that

*

*each $v\in V_0$ has $2k$ neighbours in $V_0$, and $2k+1$ neighbours in $V_1$;


*for $0<i<k$, each $v\in V_i$ has $2k-i$ neighbours in $V_{i-1}$, and $2k-i+1$ neighbours in $V_{i+1}$;


*each $v\in V_k$ has its $2k+1$ neighbours in $V_{k-1}$.
This ensures that all vertices in $V_0\cup\dots\cup V_{k-1}$ are celebrities. Let $n_i=|V_i|$. Counting the number of edges between $V_i$ and $V_{i+1}$ in two ways, we see that the sizes must satisfy
$$\frac{n_{i+1}}{n_i}=\frac{2k-i+1}{2k-i-1}$$
for $i<k-1$, and
$$\frac{n_k}{n_{k-1}}=\frac{k+2}{2k+1}.$$
Thus, we put
$$n_i=\frac{(2k+1)(2k)}{(2k-i+1)(2k-i)}n_0\qquad\text{for $i<k$,}\qquad n_k=\frac{2k}{k+1}n_0,$$
where $n_0$ is chosen as a multiple of $(2k)!$ so that all $n_i$ are integers. To satisfy the degree requirements above, the edge set consists of:

*

*a $2k$-regular graph with vertex set $V_0$;


*for each $i<k-1$, $n_i/(2k-i-1)=n_{i+1}/(2k-i+1)$ copies of $K_{2k-i-1,2k-i+1}$ between $V_i$ and $V_{i+1}$;


*$n_{k-1}/(2k+1)=n_k/(k+2)$ copies of $K_{2k+1,k+2}$ between $V_{k-1}$ and $V_k$.
Since $n_0\le n_i$ for each $i$, the total size of the graph is at least $(k+1)n_0$, whereas the number of non-celebrities is $n_k<2n_0$, thus the proportion of celebrities is at least
$$1-\frac2{k+1}.$$
