How large part of a graph can be covered by the neighborhoods of k k vertices?

János Pach · 2026

Read How large part of a graph can be covered by the neighborhoods of k k vertices? by János Pach (2026) 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-2604-27639.txt.

Introduction

Pach answers a question of Simon Griffiths about how much of a graph k neighborhoods can cover, for any fixed k of at least two. For a graph with n vertices and average degree a fraction c of n, some k vertices have neighborhoods covering at least a share set by c and k. The result is essentially tight, meaning no substantially stronger general guarantee is possible. It settles how large a part of such a graph k neighborhoods can always be made to cover.

Catalog record

CREATORJános Pach
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE10264
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.27639

Browse the full library · About the Tower of Babel

Full text

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

How large part of a graph can be covered by the neighborhoods of k k vertices? János Pach Abstract Let k ≥ 2 k\geq 2 be fixed integer, 0 < c < 1 0<c<1 a constant. Consider a graph G G with n n vertices and average degree c ​ n cn . We answer a question of Simon Griffiths by showing that G G has k k vertices such that their neighborhoods together cover at least min ⁡ ( 1 − ( 1 − c ) k , c ) ​ n \min(1-(1-c)^{k},\sqrt{c})n vertices. This result is essentially tight. 1 Introduction Let G be a fixed graph with vertex set V and edge set E , where n=|V|. For any vertex u\in V, let N(u) denote the neighborhood of u in G , that is N(u)=\{x\in V:ux\in E\} . The size of N(u) is the degree of u , and is denoted by d(u) . Let \Delta(G)=\Delta and \overline{d}(G)=\overline{d} stand for the maximum degree and the average degree of the vertices of G . Clearly, we have \Delta\geq\overline{d}. Let k\geq 2 be a fixed integer, and assume that the average degree of the vertices, \overline{d}(G)=\sum_{u\in V}d(u)/n=cn. We want to estimate the largest number h(G) such that G has k vertices, u_{0},u_{1},\ldots u_{k} such that |N(u_{0})\cup\ldots\cup N(u_{k-1})|\geq h(G). We start with two simple examples. Consider a random graph \mathbf{G}(n,c) on n vertices with edge probability c\;(0<c<1) . For a given set of k vertices, u_{0},\ldots,u_{k-1}, the probability that a fixed vertex different from them is not connected to any of them is (1-c)^{k} , Thus, the expected size of \bigcup_{i=0}^{k-1}N(u_{i})\setminus\{u_{0},\ldots,u_{k-1}\}=(n-k)(1-(1-c)^{k})=(1-(1-c)^{k}+o(1))n. It easily follows by Chernoff’s bound [ 1 , 4 ] that, as n\rightarrow\infty , almost surely the size of the union of the neighborhoods of every k -tuple of vertices will be at most (1-(1-c)^{k}+o(1))n. The same estimates hold for quasi-random graphs [ 3 ] . Our second example is a graph G^{\prime} that consists of a complete graph with \lceil\sqrt{c}n\rceil+1 vertices and its remaining vertices are isolated. Clearly, the average degree of G^{\prime} satisfies \overline{d}(G^{\prime})\geq cn , but the size of the union of no set of neighborhoods in G^{\prime} exceeds \lceil\sqrt{c}n\rceil+1 . At the problem session of the 60th birthday conference of Bruce Reed (Oxford, July 2022), Simon Griffiths conjectured that for every c,\;0<c<1, one of the above two graphs is asymptotically optimal, that is, the following theorem is true. Theorem 1 . Let k\geq 2 , and let G=(V,E) be a graph on n vertices with average degree cn , where 0\leq c\leq 1 . Then there exist vertices u_{0},\dots,u_{k-1}\in V such that \bigl|N(u_{0})\cup\cdots\cup N(u_{k-1})\bigr|\geq\min\bigl\{(1-(1-c))^{k}n,\,\sqrt{c}\,n\bigr\}. The problem was also featured as Questions 1 and 2 in the seminal paper of José D. Alvarado, Leonardo Gonçalves de Oliveira, and Simon Griffiths [ 2 ] (page 842). In the next section, we prove the above result. Note that formally the theorem is true for k=1 , too, and also for c=0 or c=1 , but these cases are trivial. Before turning to the proof, we remark that an easy averaging argument shows that the theorem is asymptotically true for k=2 , provided that G is regular , that is d(u)-cn for every u\in V . Let H denote the complement of G , and let N_{H}(w) stand for the neighborhood of w in H . Using the fact that |N(u_{1})\cup N(u_{2})|\geq n-2-|N_{H}(u_{1})\cap N_{H}(u_{2})|, it is sufficient to show that there exist u_{1},u_{2}\in V such that |N_{H}(u_{1})\cap N_{H}(u_{2})|\leq((1-c)^{2}+o(1))n. (1) To see this, estimate the sum of |N_{H}(u_{1})\cap N_{H}(u_{2})| over all the \binom{n}{2} unordered pairs of distinct vertices \{u_{1},u_{2}\}. We have \sum_{\{u_{1},u_{2}\}}|N_{H}(u_{1})\cap N_{H}(u_{2})|=\sum_{v\in V}\binom{d_{H}(v)}{2}=n\binom{n-1-cn}{2}. Dividing the right-hand side by \binom{n}{2}, inequality ( 1 ) follows. After this initial success, we expected that, with a little extra effort, the argument could be extended to all degree sequences. We explored several plausible greedy strategies to find k neighborhoods that collectively maximize vertex coverage; however, their outcomes proved resistant to analysis. Ultimately, we returned to the averaging approach, albeit with a small tweak: we started the procedure with a vertex of maximum degree. Miraculously, this slight modification made the underlying calculations tractable. The devil resides in the details of the calculus! 2 Proof of Theorem 1 Choose a vertex u_{0}\in V of maximum degree \Delta, and denote its neighborhood in N(u_{0}) by S . Write d(u_{0})=\Delta=sn,\qquad S:=N(u_{0}),\qquad T:=V\setminus S. Since \Delta is at least the average degree \overline{d}(G) , we have s\geq c . If s\geq\sqrt{c} , then already |N(u_{0})|=\Delta=sn\geq\sqrt{c}\,n, and we are done. Thus, we may assume throughout that c\leq s<\sqrt{c}. Since every vertex of S has degree at most \Delta , we have \sum_{u\in V(G)}|N(u)\cap S|=\sum_{s\in S}d(s)\leq|S|\,\Delta=\Delta^{2}=s^{2}n^{2}. As the total degree sum is cn^{2} , it follows that \sum_{u\in V(G)}|N(u)\cap T|=\sum_{u\in T}d(u)=cn^{2}-\sum_{u\in V(G)}|N(u)\cap S|\geq(c-s^{2})n^{2}. (2) Choose u_{1},\dots,u_{k-1}\in V(G) independently and uniformly at random. For any u\in T . The probability that u lies in at least one of the neighborhoods N(u_{1}),\dots,N(u_{k-1}) is 1-\left(1-\frac{d(u)}{n}\right)^{k-1}. Notice that the function f(x):=1-(1-x)^{k-1}\qquad(0\leq t\leq 1). (3) is nonnegative, concave on the interval [0,1] , and we have f(0)=0,f(1)=1 . Since d(u)/n\leq\Delta/n=s\leq\sqrt{c}\leq 1 , by concavity we obtain \frac{f\!\left(d(u)/n\right)}{d(u)/n}\geq\frac{f(s)}{s}. Therefore, in view of ( 2 ), the expected number of vertices of T covered by N(u_{1})\cup\cdots\cup N(u_{k-1}) is at least \frac{f(s)}{s}\cdot\frac{1}{n}\sum_{u\in T}d(u)\geq\frac{1-(1-s)^{k-1}}{s}\,(c-s^{2})n. Hence, for a suitable choice of (not necessarily distinct) u_{1},\dots,u_{k-1}\in V , we have \bigl|(N(u_{1})\cup\cdots\cup N(u_{k-1}))\cap T\bigr|\geq\frac{1-(1-s)^{k-1}}{s}\,(c-s^{2})n. Adding the neighborhood S=N(u_{0}) , we conclude that \bigl|N(u_{0})\cup N(u_{1})\cup\cdots\cup N(u_{k-1})\bigr|\geq\left(s+\frac{1-(1-s)^{k-1}}{s}(c-s^{2})\right)n. Thus, it remains to prove that for c\leq s\leq\sqrt{c}, the last expression is at least \min\{1-(1-c)^{k},\sqrt{c}\}. This is the content of the next lemma. Let k\geq 2 . To simplify the notation, set F(s):=s+\frac{1-(1-s)^{k-1}}{s}(c-s^{2}),\qquad G(c):=1-(1-c)^{k}. Lemma 2 . Let k\geq 2 be fixed. For every \;0<c<1 and every s\in[c,\sqrt{c}] , we have F(s)\geq\min\{G(c),\sqrt{c}\}. Proof. We split the proof into two cases. Case 1: G(c)\leq\sqrt{c} . It will be convenient to set a new variable x:=1-s, so that we have x\in[1-\sqrt{c},\,1-c] and F(s)=(1-x)x^{k-1}+c\,\frac{1-x^{k-1}}{1-x}=(1-x)x^{k-1}+c\sum_{i=0}^{k-2}x^{i}. Hence, \displaystyle F(s)-G(c) \displaystyle=x^{k-1}-x^{k}+\sum_{i=0}^{k-2}x^{i}-(1-c)\sum_{i=0}^{k-2}x^{i}-1+(1-c)^{k} \displaystyle=(1-c)^{k}-(1-c)\sum_{i=0}^{k-2}x^{i}+\sum_{i=1}^{k-1}x^{i}-x^{k} \displaystyle=\bigl((1-c)^{k}-x^{k}\bigr)+\bigl(x-(1-c)\bigr)\sum_{i=0}^{k-2}x^{i} \displaystyle=\bigl((1-c)-x\bigr)\left(\sum_{i=0}^{k-1}(1-c)^{k-1-i}x^{i}-\sum_{i=0}^{k-2}x^{i}\right). We need to show that F(s)-G(c)\geq 0 . Observe that 1-c-x\geq 0. If 1-c=x, then we are done. Otherwise, \frac{F(s)-G(c)}{1-c-x}=\sum_{i=0}^{k-1}(1-c)^{k-1-i}x^{i}-\sum_{i=0}^{k-2}x^{i}. The right-hand side is a polynomial P(x) of degree k-1 in x , with coefficients (1-c)^{k-1}-1,\ (1-c)^{k-2}-1,\ \dots,\ (1-c)-1,\ 1. Since 0<1-c<1 , this sequence has exactly one sign change. By Descartes’ rule of signs, P(x) has at most one positive root. In view of the fact that P(0)=(1-c)^{k-1}-1<0, it follows that if a positive root exists, then P(x)<0 before the root and P(x)>0 after that. Evaluating P at x_{0}:=1-\sqrt{c} and taking into account our assumption G(c)\leq\sqrt{c} , we find that P(x_{0})=\frac{F(\sqrt{c})-G(c)}{1-c-x_{0}}=\sqrt{c}-G(c)\geq 0. Hence, P(x)\geq 0 for every x\in[x_{0},1-c] , which implies that F(s)-G(c)\geq 0, as required. Case 2: G(c)\geq\sqrt{c} . As before, we set x:=1-s, so that x\in[1-\sqrt{c},\,1-c] . Now we need to show that F(s)\geq\sqrt{c} . A direct calculation, similar to the one used in Case 1, gives that F(s)-\sqrt{c}=(\sqrt{c}-s)Q(x), (4) where Q(x):=\sqrt{c}\sum_{i=0}^{k-2}x^{i}-x^{k-1} is a polynomial of degree k-1 is x . Since \sqrt{c}-s\geq 0 , it remains to show that Q(x)\geq 0 on the interval [1-\sqrt{c},1-c] . The coefficients of Q(x) are \sqrt{c},\ \sqrt{c},\ \dots,\ \sqrt{c},\ -1, so there is exactly one sign change. By Descartes’ rule of signs, Q(x) has at most one positive

Read the complete text