{'fraction_non_alphanumeric': 0.0568162282963727, 'fraction_numerical': 0.013666838576585868, 'mean_word_length': 3.5484753713838937, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
AN UPPER BOUND ON THE CHEEGER CONSTANT OF A DISTANCE-REGULAR GRAPH

We present an upper bound on the Cheeger constant of a distance-regular graph. Recently, the authors found an upper bound on the Cheeger constant of distance-regular graph under a certain restriction in their previous work. Our new bound in the current paper is much better than the previous bound, and it is a general bound with no restriction. We point out that our bound is explicitly computable by using the valencies and the intersection matrix of a distance-regular graph. As a major tool, we use the discrete Green’s function, which is defined as the inverse of β-Laplacian for some positive real number β. We present some examples of distance-regular graphs, where we compute our upper bound on their Cheeger constants.


Introduction
A notion of the Cheeger constant of a graph has an important geometric meaning in graph theory. The Cheeger constant of a graph is closely related to the problem of separating a graph into two large components by making a small edge-cut. In fact, the Cheeger constant of a connected graph is strictly positive. If the Cheeger constant of a connected graph is "small", then it means that there are two large sets of vertices with "few" edges between them. On the other hand, if a graph has "large" Cheeger constant, then it indicates that there are two sets of vertices with "many" edges between these two subsets. In general, computation of the Cheeger constant of a graph is a hard task. Only limited research has been done for finding the Cheeger constant of a graph. We are interested in finding bounds of Cheeger constants of graphs.
We begin with introducing some definitions in graph theory. Let Γ = (V, E) be a simple and connected graph, where V is the vertex set of Γ and E is the Proposition A ( [3]). Let Γ be a distance-regular graph with more than one vertex. Then its edge-connectivity equals its valency k, and the only disconnecting sets of k edges are the sets of edges incident with a single vertex. Proposition B ( [4]). Let Γ be a non-complete distance-regular graph of valency k > 2. Then the vertex-connectivity κ(Γ) equals k, and the only disconnecting sets of vertices of size not more than k are the point neighbourhoods.
Proposition C ( [14]). Let Γ = (V, E) be a simple graph with the vertexconnectivity κ(Γ) and the edge-connectivity λ(Γ). Then where S is a subset of V with |S| ≤ |V | 2 . The Cheeger constants [9,15] are related to the eigenvalues of the Laplacians of distance-regular graphs, and their eigenvalues are also involved with the intersection numbers of distance-regular graphs [13,16]. However, in general, it is a hard task to compute the Cheeger constant of a distance-regular graph. Distance-regular graphs introduced by Biggs [2] are connected with coding theory and design theory; well-known examples of distance-regular graphs are the Hamming graphs and the Johnson graphs. In [11,12], by using the relationship between a discrete Green's function and the Cheeger constant, we obtain an upper bound on the Cheeger constant of a distance-regular graph under a certain condition.
We find a general upper bound on the Cheeger constant of a distance-regular graph with no additional condition. Furthermore, our bound is a much more improved one comparing with the bound in [12] under the same additional condition; in Example 7 and Example 8, we show that our bound is much more improved one comparing with the bound in [12] under the same additional condition: βvr 1+λ1 . We point out that our bound is explicitly computable by using the valencies and the intersection matrix of a distance-regular graph; first, our bound is expressed in terms of q-numbers, and in general, it is not easy to compute the q-numbers. For resolving this problem, we obtain an alternative expression of our bound using the valencies and the intersection matrix of a distance-regular graph. In Example 10 and Example 11, we compute the upper bound on the Cheeger constant using the alternative expression in Theorem 2 and Remark 6. As a major tool, we use the discrete Green's function, which is defined as the inverse of β-Laplacian for some positive real number β. We present some examples which show our upper bound on the Cheeger constant for some distance-regular graphs.
We discuss our main result in more detail for the rest of this section. In this paper, we study distance-regular graphs. Let Γ = (V, E) be a distance-regular graph of order v, diameter d and valency k. Let A 1 be the adjacency matrix of Γ and P be the transition probability matrix of Γ. Two adjacent vertices x, y are denoted by x ∼ y. For a function f : Let L β be the β-normalized Laplacian βI + ∆. For β > 0, let G β be a discrete Green's function denoted by the symmetric matrix which satisfies L β G β = I; that is, G β is defined as the inverse of the β-Laplacian L β [5,6,7]. As in [11], for any positive real number β, let r (β) i (i = 0, 1, . . . , d) denote the components of a Green's function G β . We define α i to be the limit of a sequence {α In fact, we can express α i 's by the eigenvalues λ j of the Laplacian L β and the q-numbers q j (i) of the P-polynomial scheme [1,8,10,11]: We also see that 0 < α d < α d−1 < · · · < α e < λ 1 for some e.
The authors obtain the following result [12] on an upper bound on the Cheeger constant of a distance-regular graph with a certain restricted condition as follows.
Theorem A ( [12]). Let Γ be a distance-regular graph with diameter d and βvr 1+λ1 for β ≤ α d . Let λ 1 be the smallest eigenvalue of the Laplacian.
Then we have for e ∈ C ′ β . Main results of this paper are the following Theorem 1, Theorem 2 and Corollary 3. Theorem 1 presents an upper bound on the Cheeger constant of a distance-regular graph. In Theorem 2, we find an explicit expression for the bound given in Theorem 1 by using the valencies k j and the basis of nullspace sub ). This shows that our new bound is a computable bound using the valencies and the intersection matrix of a distance-regular graph. Corollary 3 shows that our generalized bound in Theorem 1 and Theorem 2 improves the bound given in Theorem A [12] under the same additional condition.
Theorem 1. Let Γ be a distance-regular graph of diameter d. Then we have the following upper bound: Theorem 2. Let Γ be a distance-regular graph of order v and diameter d.
where k j are valencies as in Lemma 4 and α d is the same as in Lemma 5.
Corollary 3. Let Γ be a distance-regular graph, and h Γ be a Cheeger constant of Γ. If βvr where λ 1 is the smallest positive eigenvalue of the Laplacian and α d is the same as in (1).
In Section 2, we introduce some notations and facts about distance-regular graph and some properties of the Green's function G β . In Section 3, we find a new upper bound on the Cheeger constant of a distance-regular graph. We also obtain an alternative expression of our upper bound by using the valencies k j and the basis of nullspace N (L (α d ) sub ). Finally, in Section 4, we present some examples about our upper bound on the Cheeger constant of some distanceregular graphs.

Preliminaries and Green's function
We introduce definitions of the distance-regular graphs and the P -polynomial schemes. A connected graph Γ with diameter d is called a distance-regular graph if there are constants c i , a i , b i such that for all i = 0, 1, . . . , d, and all vertices x and y at distance i = d(x, y), among the neighbors of y, there are c i at distance i − 1 from x, a i at distance i, and b i at distance i + 1. It follows that Γ is a regular graph with valency k = b 0 , and that c i + a i + b i = k for all i = 0, 1, . . . , d. By these equations, the intersection numbers a i can be expressed in terms of the others, and it is a standard to put these others in the so-called intersection array (b 0 , b 1 , . . . , b d−1 ; c 1 , c 2 , . . . , c d ). We describe the relations by its adjacency matrices A i (i = 0, 1, . . . , d) which are v × v matrices defined by [1,8]. Let X be a nonempty finite set and R = {R 0 , R 1 , . . . , R d } be a family of relations defined on X. We say that the pair (X, R) is a symmetric association scheme with d classes if it satisfies the following conditions.
(1) A 0 = I (indentity matrix). ( A symmetric association scheme X = (X, R) is called a P -polynomial scheme with respect to the ordering R 0 , R 1 , . . . , R d , if there exist some complex coefficient polynomials υ i (x) of degree i (i = 0, 1, . . . , d) such that A i = υ i (A 1 ), where A i is the adjacency matrix with respect to R i .
It is known [1,8] that a distance-regular graph is equivalent to a P -polynomial scheme X with respect to some relations R 0 , R 1 , . . . , R d on a vertex set V with |V | = v. Thus, we can define the Green's function over a P -polynomial scheme, and then by using the Green's function we will obtain an upper bound on the Cheeger constant of a distance-regular graph.
The first intersection matrix B 1 of a distance-regular graph is a tridiagonal matrix with non-zero off diagonal entries: Let A be the algebra spanned by the adjacency matrices A 0 , A 1 , . . . , A d . Then A is called the Bose-Mesner algebra of X, and A has two distinguished bases {A i } and {E i }, where the latter consists of primitive idempotent matrices. For A i and E i , we can express one in terms of the other as the following: for j = 0, 1, . . . , d. The (d + 1) × (d + 1) matrix P = (p j (i)) (respectively, Q = (q j (i))) is called the first eigenmatrix (respectively, the second eigenmatrix) of the P-polynomial scheme X, where p j (i) (respectively, q j (i)) is a p-number (respectively, a q-number).
As defined in Section 1, the Green's function G β is the inverse of the β-Laplacian L β . For β > 0, we thus have G β (βI + I − P ) = I. Therefore, we get That is, G β is a linear combination of adjacency matrices A i as follows: . In [10,11], a d × (d + 1) matrix L (β) sub is introduced as a matrix obtained by the removal of the first row of B 1 − k 1 (β + 1)I.
Green's function of a distance-regular graph Γ of order v. Then we have (a) G β can be expressed as G β = tu (β)

A new improved bound on the Cheeger constant
In this section we prove Theorem 1 and Theorem 2. We need the following lemma for the proof of Theorem 2 and Theorem 3. We consider a set > 0} as a subset of {0, 1, 2, . . . , d}; then C β is a non-empty set by Lemma 4. When β is sufficiently close to 0 + , we consider a set C ′ β = {i | βvr 11]). For β > 0, let Γ be a distance-regular graph of order v, and let G β = r (β) . . , d) as given in Eq. (1). Then for i ∈ C ′ β , we have the following: Proof of Theorem 1. Let S be a subset of the vertex set V of Γ with vol(S) ≤ vol(V )/2 and |∂S| vol(S) = h Γ . Let S ′ be a subset of V with |∂S ′ | vol(S ′ ) = h Γ . Then there exists some β with 0 < β < 1 such that .
We first note that for a positive integer n, this follows immediately from We claim that for any ǫ > 0, there exists a positive integer N ε such that (5) α (α d β n ) d < α 2 d + ε for any n ≥ N ε ; we use Lemma 5 for the proof as follows. Let f n = α d β n vr Then lim n→∞ f n = 1 − by Lemma 5(a). Thus, for sufficiently large positive integer n, we obtain the following approximations: so our claim in Eq. (5) follows. From Eq. (4) and Eq. (5), we thus have that Taking ε > 0 to be such that ε < vol(S) |∂S| − 1 α 2 d (noting that the right hand side of this inequality is positive), we obtain this is because from Eq. (3) and Eq. (6), we get the following: Consequently, the result follows as desired.
Proof of Theorem 2. From Theorem 1, we have By Lemma 5, we have