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$?



Celebrity vertices in graphs
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}.$$


