On Unique Neighborhoods in Bipartite and Expander Graphs

Stefan Rass · 2025

Read On Unique Neighborhoods in Bipartite and Expander Graphs by Stefan Rass (2025) 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-2505-06329.txt.

Introduction

Stefan Rass, writing alone, studies what makes a node stand out in a network in this 2025 paper. A network has unique neighborhoods if no two nodes share the exact same set of neighbors. In that case the links of a node can act like an identity, no matter how the nodes are named.

Rass looks at this trait in two kinds of networks. One kind splits nodes into two groups with links only across the split. The other kind spreads links widely, so paths between nodes stay short. He studies both fixed and random versions of these networks. The question matters for telling nodes apart from link patterns alone.

Catalog record

CREATORStefan Rass
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE15 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-06329

Browse the full library · About the Tower of Babel

Full text

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

On Unique Neighborhoods in Bipartite and Expander Graphs Stefan Rass Abstract An undirected graph is said to have unique neighborhoods if any two distinct nodes have also distinct sets of neighbors. In this way, the connections of a node to other nodes can characterize a node like an “identity”, irrespectively of how nodes are named, as long as two nodes are distinguishable. We study the uniqueness of neighborhoods in (random) bipartite graphs, and expander graphs. 1 Introduction This note is an extension to [ 3 ] on UNN , where we study some two additional classes of graphs, namely bipartite and expander graphs for having (or not having) the UNN property. The main results are the facts that random bipartite graphs with edges only between two subsets V,W almost surely exhibit unique neighborhoods, if V and W are asymptotically of the same cardinalities. For expander graphs, we show that unique neighborhoods are logically independent of the graph to be or not to be an expander; more precisely, the UNN property neither follows from or is refutable from any value of the graph’s Cheeger constant. Definition 1 ( UNN [ 3 ] ) . A graph G=(V,E) is a UNN , if no neighborhood is a subset of another node’s neighborhood. That is, for every v , there is some u\in\text{nb}(v) with u\notin\text{nb}(w) for all w\neq v , or equivalently, there is a nonempty symmetric difference \text{nb}(u)\triangle\text{nb}(v)\neq\emptyset for all distinct u,v . To ease our notation, we let the set of all UNN be denoted by \mathrm{UNN} , meaning that G\in\mathrm{UNN} is a shorthand for unique neighborhoods in G , and G\notin\mathrm{UNN} implying that at least two nodes in G have the same neighborhood. More formally, the definition of a UNN is the following: 2 UNN in Random Bipartite Graphs We start from [ 3 , equation (2)] , B_{ij}:=(\mathbf{A}\cdot\mathbf{1}_{N\times N}-\mathbf{A}^{2})_{ij}=\sum_{k=1}^{N}a_{ik}\cdot 1-\sum_{k=1}^{N}a_{ik}a_{kj}=\sum_{k=1}^{N}a_{ik}(1-a_{kj}). where we put N=n+m as the total number of nodes in the graph, and let \mathbf{A} be its (usual) adjacency matrix 1 1 1 for bipartite graphs, the bi-adjacency matrix of n\times m shape is an occasional alternative, but explicitly not used here . Therein, a_{ik}=1 if i\in V_{1} and k\in V_{2} become connected, which happens with a constant probability 0<p<1 . Thus, \Pr(a_{ik}=1)=\Pr(i\in V_{1}\land k\in V_{2}\land S) , if S is the event of this edge to appear, with \Pr(S)=p . The selection of i and k is made independently and uniformly from V_{1},V_{2} , and likewise is S independent of both, and has the same probability for all possible edges. From this, we get \displaystyle\Pr(a_{ik}=1) \displaystyle=\Pr(i\in V_{1})\cdot\Pr(k\in V_{2})\cdot p \displaystyle=\frac{n}{n+m}\cdot\frac{m}{n+m}\cdot p so that \displaystyle\Pr(a_{ik}=1\land a_{kj}=0) \displaystyle=\left(\frac{n}{n+m}\cdot\frac{m}{n+m}\cdot p\right)\cdot\left(1-\frac{n}{n+m}\cdot\frac{m}{n+m}\cdot p\right) \displaystyle=:q Now, we have all terms inside the definition of B_{ij} be values in \left\{0,1\right\} considering that \Pr(B_{ij}=0)=(1-q)^{N} by a binomially distributed choice of zero from B_{ij}\in\left\{0,1,\ldots,N\right\} . It remains to show that q is bounded between 0 and 1, and this will depend on the growth of \left|V_{1}\right|=n relative to \left|V_{2}\right|=m . For example, if we let N\to\infty , while keeping either n or m bounded, unique neighborhoods are impossible by the pigeon hole principle. However, if we assume \left|V_{1}\right|\in\Theta(\left|V_{2}\right|) , then there are two constants a,b>0 such that for sufficiently large m,n , we have \left|V_{1}\right|\leq a\cdot\left|V_{2}\right| and \left|V_{2}\right|\leq b\cdot\left|V_{1}\right| , which puts q strictly inside the unit interval (0,1) . From this point onwards, the proof carries over verbatim from [ 3 , equation (3)] , giving the conclusion that the bipartite graph will grow into a UNN . This proves the following result: Theorem 1 . Let a random bipartite graph G_{n,m} be given with n=\left|V_{1}\right|,m=\left|V_{2}\right| and n\in\Theta(m) . Let the edges of G appear with a probability p that does not depend on n or m . Then, as n+m\to\infty , G_{m,n} will almost surely be a UNN . 3 UNN in Expander Graphs We will show the logical independence of unique neighborhoods from the value of the graph’s Cheeger constant. To this end, let us briefly recall the respective definitions. Let G=(V,E) be a graph with n=\left|V\right| vertices. For a subset S\subseteq V , write \partial S=\left\{\{u,v\}:u\in S,v\notin S\right\} for the set of edges that connect a node inside S with a node outside S . The Cheeger constant h(G) is defined as h(G)=\min_{S\subset V:\left|S\right|\leq\left|V\right|/2}\frac{\left|\partial S\right|}{\left|S\right|} . We call G an (n,\varepsilon,d) -expander 2 2 2 We remark that the definition of expander families is not entirely consistent throughout the literature, since other authors denote the relevant parameters in different order or form , if all nodes in G have a degree \leq d , and the graph has a Cheeger constant h(G)\geq\varepsilon . If \lambda_{2} is the second-largest eigenvalue of the normalized Laplacian matrix of the graph, which is \mathbf{L}=\mathbf{I}-\mathbf{D}^{-1/2}\cdot\mathbf{A}\cdot\mathbf{D}^{1/2} , where \mathbf{D}=\text{diag}(\text{deg}(v_{1}),\ldots,\text{deg}(v_{n})) is the diagonal matrix with node degrees, and \mathbf{A} is the graph’s adjacency matrix. The celebrated Cheeger-inequality states that \lambda_{2}\leq 2h(G)\leq\sqrt{2\lambda_{2}} . The usual interest is in infinite sets of expander graphs with constant d and \varepsilon , and we denote such a set by \mathcal{G}(N,\varepsilon,d) , including graphs of all sizes n\in N\subseteq\mathds{N} , but all with the same d and \varepsilon , and with \left|N\right|=\infty . Specifically, let \varepsilon be arbitrary but fixed, then we will construct example graphs for the following four cases. For each case, we let n>1 be arbitrary, implying that there is an infinitude of graphs with the given properties. Table 1: Logical independence of UNN from the size of the graph’s Cheeger constant Cheeger constant \geq\varepsilon Cheeger constant <\varepsilon UNN complete graph; Lemma 1 circle graph; Lemma 2 not a UNN complete bipartite graph; Lemma 3 any graph G(V,\emptyset) with V\neq\emptyset ; see also Lemma 4 Lemma 1 . For every \varepsilon>0 there is some n>1 and a graph G_{n}\in\mathrm{UNN} of size n that has a Cheeger constant h(G_{n})\geq\varepsilon . Proof. Simply consider the complete graph K_{n}=(V,V\times V) with \left|V\right|=n , which is a UNN [ 3 , Lemma 5] . For A\subseteq V , with size \left|A\right| , we have \left|\partial{A}\right|=\left|A\right|\cdot(n-\left|A\right|) many edges outgoing from A , giving the \frac{\left|A\right|\cdot(n-\left|A\right|)}{\left|A\right|}=n-\left|A\right| , which is at its minimum for \left|A\right|=n/2 , giving the Cheeger constant h(G)=n/2 . The result follows by making n>2\varepsilon . ∎ Lemma 2 . For every \varepsilon>0 there is some n\in\mathds{N} and a graph G_{n}\in\mathrm{UNN} of size n that has a Cheeger constant h(G_{n})<\varepsilon . Proof. The sought graph is the circle graph C_{n} with n nodes. This graph is a UNN [ 3 , Lemma 5] . Its Cheeger constant is easily to find by considering the set A=\left\{1,2,\ldots,\lfloor n/2\rfloor\right\} , having outgoing edges \left\{\{\lfloor n/2\rfloor,\lfloor n/2\rfloor+1\},\{n,1\}\right\} , which gives \frac{\partial A}{\left|A\right|}=\frac{2}{\lfloor n/2\rfloor}\to 0 as n\to\infty . Thus, for sufficiently large n , the Cheeger constant will become <\varepsilon . ∎ Lemma 3 . For every \varepsilon>0 there is some n>1 and a graph G_{n}\notin\mathrm{UNN} of size n with a Cheeger constant h(G_{n})\geq\varepsilon . Proof. The sought graph is the complete bipartite graph K_{n/2,n/2} for even n . This is a well-known example of a Ramanujan-graph, whose spectral gap is largest possible; specifically, with the second-smallest eigenvalue \lambda_{2} of the graph’s Laplacian, we have a diverging spectral gap, if we let d=n/2\to\infty . The divergence of the Cheeger

Read the complete text