You are an expert at summarizing long articles. Proceed to summarize the following text: 
a ramanujan graph is a @xmath0-regular finite graph with nontrivial eigenvalues @xmath1 satisfying @xmath2 this condition is equivalent to the `` graph theoretical riemann hypothesis '' for the ihara zeta function associated to the graph , see @xcite for more information . the above equivalence was first formulated by sunada in @xcite . infinite families of @xmath0-regular ramanujan graphs of increasing size are examples of the more general families of expander graphs . in fact , the families of ramanujan graphs are the expander families that are optimal from the spectral point of view , according to the bounds by alon and boppana . furthermore , the known constructions of families of ramanujan graphs are essentially number theoretical ; for instance , the proof of the ramanujan property ( [ eqn : ramprop ] ) for the original families is related to the ramanujan conjecture for modular forms of weight 2 . the families of expanders have applications to engineering and computer science , among others areas @xcite . the original construction of families of ramanujan graphs was presented by lubotzky , phillips and sarnak in @xcite _ _ * * _ _ , and independently by margulis in @xcite . the former construction consists of cayley graphs on projective linear groups over a finite field . the use of cayley graphs allows to utilize the properties of the underlying group and the generating set to determine structural and spectral properties of the graph . for example , the irreducible representations of the underlying group are directly related to the eigenvalues of the graph . recently , there has been work on generalizing the notion of group determinant as a function of a group - subgroup pair using the representation theory of @xmath3-determinants @xcite . the resulting wreath determinant for group - subgroup pairs shares some of the properties of the group determinant , but there is a nontrivial relation with the chosen ordering of the group and subgroup elements . some results on factorization for this determinant can be found on @xcite , it turns out to be closely related to the representation of the symmetric groups associated with the given group and subgroup and their wreath product . it was suggested to the author by masato wakayama that one could employ the same strategy to extend existing constructions , or to conceive new constructions , of ramanujan graphs and expanders based on groups , in particular , by generalizing cayley graphs . in this paper , we apply these ideas to introduce an extension of cayley graphs for a group - subgroup pair . the motivation is twofold , one is to have further tools to solve problems , in particular the construction of ramanujan graphs ; and to continue the work on this incipient group - subgroup study philosophy .    the main purpose of this paper is to introduce the concept of group - subgroup pair graph based on these considerations and show its elementary properties . in particular , the degree of the vertices of the pair graph is determined by the coset structure of the subgroup and the chosen generating set . the organization of the paper is as follows . in section 2 , the definition , examples and basic properties are presented . namely , the determination of the degrees of the vertices of the graph , and the conditions for the graph to be regular . in section 3 , conditions for connectedness of the graph are completely determined , along with the number and properties of connected components for disconnected graphs . additionally , sufficient conditions for the graphs to be bipartite and the notion of trivial eigenvalues are introduced for the group - subgroup pair graphs . in section 4 we limit the discussion to the regular graph case and assert a symmetry relation between the spectrum for different choices of generating set for fixed group and subgroup , this result is applied to give a sufficient condition on the size of the generating set that guarantees that the resulting graphs are ramanujan graphs . we provide two examples of ramanujan graphs obtained by using this condition . the common theme throughout this paper is to compare and relate the results on group - subgroup pair graphs with results on cayley graphs . in this section we introduce the group - subgroup pair graph , a cayley - type graph construction for group - subgroup pairs ; relate the definition with the group matrix and establish some elementary properties of the graphs . first , we introduce the conventions and notation used in this paper . all groups are assumed to be finite unless otherwise stated and @xmath4 always represents the identity of a given group g. for a subgroup @xmath5 of @xmath6 , all cosets are assumed to be right cosets and we say that @xmath7 is incongruent to @xmath8 modulo @xmath5 when @xmath9 . a subset @xmath10 is said to be symmetric if @xmath11 . for a given group @xmath6 and symmetric subset @xmath12 we denote the corresponding cayley graph by @xmath13 . the characteristic function of a subset @xmath14 is denoted @xmath15 and the notation @xmath16 $ ] for @xmath17 is used for the set @xmath18 . [ def]let @xmath6 be a group , @xmath5 a subgroup and @xmath19 a subset such that @xmath20 is a symmetric subset of @xmath6 . then the * group - subgroup pair graph * @xmath21 is the graphwith vertex set g and edges @xmath22    equivalently , the group - subgroup pair graph @xmath21 can be defined as @xmath23 where @xmath24 , @xmath25 and @xmath26 is the generalized edge sum operator , as defined in @xcite . the graph @xmath27 is a cayley graph and the graph @xmath28 is the graph with vertices @xmath6 and edges @xmath29 according to the alternative definition , the group - subgroup pair graph @xmath21 can be thought informally as the undirected graph consisting of an inner cayley graph of @xmath5 determined by @xmath30 and an outer graph that connects vertices of @xmath5 with vertices of @xmath31 . the notation @xmath32 and @xmath30 is used throughout this paper with the same meaning as in the previous definition .    when @xmath33 , the generating set is @xmath34 and the corresponding graphs is a cayley graph , in other words , @xmath35 . this justifies the claim that the group - subgroup pair graphs are a generalization of the cayley graphs and the seemingly artificial condition of symmetry of @xmath36 . when @xmath12 is empty , we call the resulting pair graph @xmath21 or cayley graph @xmath13 trivial . [ example1]let @xmath37 , @xmath38 , and @xmath39 , then @xmath40 and @xmath41 . the corresponding pair - graph @xmath21 can be seen on figure [ graph1 ] . [ finitefield]let @xmath42 , and the prime field @xmath43 of @xmath44 considered as a subgroup of the additive group @xmath44 , then @xmath44 is the direct sum of seven copies of @xmath5 . let @xmath45 be the norm map of @xmath44 as a field extension of @xmath5 , then if @xmath46 , we obtain the following pair - graph @xmath47    this graph consists of vertices of degree 2,4 and 16 . [ random]matrix groups over finite fields have been used in the construction of families of ramanujan graphs . set @xmath48 , where @xmath49 is the finite field of @xmath50 elements and @xmath51 , then for a random subset @xmath12 of 7 elements taken from the complement of @xmath5 in @xmath6 , we obtain the following pair - graph @xmath21 . this connected graph has 480 vertices with vertices of degrees @xmath52 and @xmath53 . note that none of the graphs of the preceding examples can be constructed as cayley graphs . we briefly mention another generalization of cayley graphs for group @xmath6 and subgroup @xmath5 , the _ schreier coset graph_. for a symmetric subset @xmath12 of @xmath6 , the schreier coset graph is defined as the graph with the set @xmath54 of coset as vertices and where two cosets @xmath55 and @xmath56 are adjacent when there is an @xmath57 such that @xmath58 a schreier coset graph can have multiples edges and loops ( even when @xmath59 ) . this kind of graphs have been used for coset enumeration techniques . a detailed exposition can be found in @xcite .    for a given group @xmath6 , the schreier coset graph is a cayley graph when @xmath60 , whereas the group - subgroup pair graph is a cayley graph when @xmath61 . as stated in the introduction , one of the motivation for the group - subgroup pair graph comes from the extension of the group determinant for a group - subgroup pair , called _ wreath determinant for group - subgroup pair_s . in this subsection we show how one can relate the adjacency matrix of a cayley graph with the group matrix of the corresponding group ; then , by extending the idea for the matrix used for the wreath determinant for group - subgroup pairs we obtain the rows corresponding to the subgroup on the adjacency matrix of a certain group - subgroup pair graph , which is enough to determine the complete adjacency graph .    for a group @xmath62 , consider a polynomial ring @xmath63 containing the indeterminates @xmath64 , for @xmath65 , then the _ group matrix _ is a matrix @xmath66 in @xmath67 defined by @xmath68 for @xmath69 $ ] and where @xmath70 $ ] is an enumeration function for @xmath6 , used implicitly . the determinant @xmath71 of the group matrix is called _ group determinant _ of @xmath6 and does not depend on the chosen enumeration of the elements of @xmath6 . for @xmath72 we have @xmath73 , therefore for any element @xmath74 , the corresponding transpose element is @xmath75 . similarly , for a group @xmath6 of order @xmath76 , and subgroup @xmath5 of order @xmath77 one can construct the matrix @xmath78 by @xmath79 for @xmath80 , @xmath81 , @xmath82 , j \in [ n k ]   $ ] and where @xmath83 $ ] and  @xmath84 $ ] are enumerations functions for @xmath6 and @xmath5 . considering only the columns corresponding to elements of @xmath5 of the matrix @xmath85 one obtains the group matrix of @xmath5 with respect to the ordering @xmath86 .    for a matrix @xmath87 , the wreath determinant of @xmath88 is defined as @xmath89 } ) , \ ] ] where @xmath90}$ ] is the row @xmath0-flexing of the matrix @xmath88 and @xmath91is the @xmath3-determinant , for an extensive exposition of the wreath determinant and its properties the reader is referred to @xcite . in the paper @xcite , the authors define the wreath determinant for the pair @xmath6 and @xmath5 by @xmath92 in contrast with the ordinary group determinant , this wreath determinant for @xmath6 and @xmath5 depends on the enumeration functions @xmath93 and @xmath86 .    for a given group @xmath6 and symmetric subset @xmath12 , by evaluating the corresponding group matrix @xmath66 by the rule @xmath94 for @xmath57 and @xmath95 for @xmath96 one obtains a symmetric matrix . since @xmath97 implies @xmath98 , the corresponding matrix is the adjacency matrix of the cayley graph @xmath13 . consider @xmath99 , the symmetric group on three letters with the ordering @xmath93 given by @xmath100 , the group matrix is @xmath101 where @xmath102 stands for @xmath64 . considering @xmath103 and evaluating in the way mentioned before we get @xmath104 which can be verified to be the adjacency matrix of the cayley graph @xmath105 . likewise , for group @xmath6 , subgroup @xmath5 and subset @xmath12 as in definition [ def ] , by evaluating the group - subgroup matrix with the rule @xmath94 for @xmath57 and @xmath95 otherwise , we obtain a matrix with nonzero entries @xmath106 when @xmath107 . in other words , there are ones in the matrix exactly when @xmath108 , which is the relation for the edges of the group - subgroup pair graph @xmath21 in definition @xmath109 . the resulting matrix corresponds to the rows associated with the elements of @xmath5 in the adjacency matrix of the pair - graph @xmath110 and can be completed by symmetry to obtain the complete adjacency matrix . let @xmath37 , @xmath38 , and @xmath111 as in example [ example1 ] , the corresponding matrix with respect to natural orderings @xmath93 and @xmath86 is @xmath112 then , evaluating as describe before @xmath113 which can be verified to correspond to the rows of the vertices of @xmath5 of the adjacency matrix of the pair - graph @xmath114 of example [ example1 ] . note that the group matrix can also be defined as @xmath115 . using this definition the resulting cayley graph is defined by left multiplication , the same is true for the group - subgroup matrix for the wreath determinant and the group - subgroup pair graph . an isolated vertex is one that is not connected to any other vertices . in contrast with nontrivial cayley graphs , group - subgroup pair graphs may contain isolated vertices even when the generating subset is non empty . the following result characterizes the presence of isolated vertices in group - subgroup pair graphs . [ isolated]i ) the pair - graph @xmath21 contains no isolated vertices if and only if @xmath12 contains a representative for each coset of @xmath5 on @xmath6 different from @xmath116 . \ii ) the vertices @xmath5 are isolated in @xmath21 if and only if @xmath12 is the empty set . suppose @xmath12 is not empty and contains a representative for each coset , then take @xmath117 , and @xmath118 the representative of @xmath55 , then there is @xmath119 such that @xmath120 , and therefore @xmath121 is connected to @xmath122 . conversely , if there are no isolated vertices , by the definition we must have @xmath123 . the second statement follows directly from the definition . consider any group @xmath6 of order @xmath77 and @xmath124 , then the graph @xmath21 with @xmath125 has no isolated vertices . in fact , @xmath21 is a @xmath126 _ star graph_.    the second part of the proposition shows the relation with cayley graphs , as a cayley graph is empty if and only if @xmath12 is the empty set . a graph in which all the vertices have the same degree is called a _ regular graph _ , more precisely , if the vertices have degree @xmath0 , the graph is called a @xmath0-_regular graph . _ an important property of a cayley graph @xmath13 is that it is @xmath127-regular . example [ example1 ] shows that this is not true in general for @xmath110 , but there is still uniformity on the degree of the vertices in each coset . [ coset]in a pair - graph @xmath21 , all the vertices in the same coset have the same degree . [ cor1]namely , the vertices in @xmath5 have degree @xmath127 and for @xmath128 the degree of the vertices in the coset @xmath55 is @xmath129 . it is clear by the definition of the outer graph @xmath130 that any vertices @xmath131 in the same coset @xmath55 have the same degree @xmath132 . the vertices in @xmath5 have degree @xmath127 by construction . returning to example [ example1 ] , @xmath133 , @xmath134 , and the cardinality of these sets corresponds to the degree of the vertex in the respective cosets . we call those types of graphs , _ multi - regular _ or more precisely @xmath135-regular graphs , where @xmath136 is the degree of the vertices on a given partition . the preceding discussion suggests that the structure of @xmath54 , the set of cosets of @xmath5 on g , is closely related to the structure of the graph . let @xmath6 be a group and @xmath5 a subgroup of index @xmath137 = k+1 $ ] . for a subset @xmath138 with @xmath30 symmetric , consider the pair - graph @xmath21 . if @xmath139 is a set of representatives of the cosets of h incongruent to @xmath4 , then for @xmath140 , @xmath141 with equality only when @xmath142 . in particular , a nontrivial @xmath21 is regular if and only if @xmath40 and @xmath137 = 2 $ ] , or @xmath137 = 1 $ ] . the inequality follows from proposition [ cor1 ] and the fact that @xmath143 , and the equality happens only when @xmath144 . the _ if _ part of the proof follows directly from the inequality and the definitions . for the _ only if _ part , consider a @xmath145-regular @xmath21 graph , then by the preceding proposition @xmath146 and @xmath147 for @xmath148 . it follows from the inequality above that @xmath149 and therefore @xmath0 is necessarily @xmath150 or @xmath151 . if @xmath137 = 2 $ ] , then @xmath152 , so @xmath153 and the case @xmath137 = 1 $ ] gives a cayley graph . note that in view of proposition [ coset ] , we can consider @xmath154 as the degree of any of the elements of the coset . in that case , the above identity can be written as @xmath155 with equality happening only when @xmath30 is empty . in this section we consider the connectedness for pair graphs @xmath156 . recall that a cayley graph @xmath13 is connected if and only if @xmath157 . we begin by considering the case @xmath158 empty , in other words , none of the vertices of @xmath5 are adjacent in @xmath21 . [ conectbip]let @xmath159 be a group , h a subgroup and  @xmath160 subset with @xmath30 symmetric . if @xmath142 then in the pair - graph @xmath21 the vertices of @xmath5 are in the same connected component if and only if @xmath161 = h.    if @xmath162 , then it suffices to prove that the identity @xmath4 is connected to an arbitrary @xmath140 . for @xmath140 , we have @xmath163 with @xmath164 , then if we set @xmath165 , @xmath166 is adjacent to @xmath167 and @xmath122 is adjacent to @xmath168 so @xmath166 is connected to @xmath122 . by repeating this process we conclude that @xmath4 is connected to @xmath122 .    on the other hand , if in the graph @xmath21 , all the vertices of @xmath5 are in the same connected component , @xmath140 is connected to @xmath169 . since there are no direct connections between two elements of @xmath5 or @xmath170 , there must be path from @xmath4 to @xmath122 where every even vertex is is an element of @xmath5 , so we have a sequence @xmath171 of elements of @xmath5 , where @xmath172 and @xmath173 is connected to @xmath102 @xmath174 with @xmath175 . that is , we have a sequence of edges @xmath176 , as shown in the following diagram .     to @xmath177 . ]    then , for @xmath178 @xmath179 thus , @xmath180 it follows that @xmath181 and @xmath182 . note that since a group - subgroup pair graph may contain isolated vertices , the condition of the lemma alone is not sufficient for connectedness . [ connectbip]with the same notation as before , if @xmath142 then the pair - graph @xmath21 is connected if and only if @xmath183 and s contains representatives of all the cosets of @xmath184different from @xmath5 . the result follows from part follows from lemma [ conectbip ] , proposition [ isolated ] and the observation that any vertex @xmath185 must be connected to some @xmath140 which is in turn connected to the identity @xmath186 . [ connectness]a pair - graph @xmath187is connected if and only if @xmath188 and @xmath12 contains representatives of all the cosets of @xmath5 different from the coset @xmath5 . first we see that the vertices of @xmath5 are in the same connected component if and only if @xmath189=h . the proof of this fact is the same as that of lemma [ conectbip ] while considering that in the path from a @xmath190 to @xmath140 there may be edges connecting elements @xmath191 from @xmath5 , in such case we have @xmath192 , with @xmath193 . then the result follows like in proposition [ connectbip ] . [ example2]let @xmath194 , @xmath195 . set @xmath196 and @xmath197 , the corresponding group - subgroup pair graphs are the following . note that @xmath198  and @xmath199 , so neither graph is connected , as can be seen in the diagrams . on the other hand , as there are no elements of the coset @xmath200 on @xmath201 , all the vertices of that coset are isolated on @xmath202 .    if a graph is not connected , the characterization of the connected components of the graph is desirable . for cayley graphs , the connected component of the identity is the subgroup @xmath203 , and each of the cosets in @xmath6 are the connected components of the graph . this identification is not identical for group - subgroup pair graphs as the connected component of the identity may include vertices from @xmath170 . in particular , the subgroup @xmath204 of @xmath5 contains the elements of @xmath5 that are in the connected component of the identity and the cosets of this subgroup are the intersection of @xmath5 with certain connected components of the graph . [ comps]with the same notation as before , let @xmath205 , then the identity component @xmath206 of @xmath207 consists of the vertices @xmath208 . the remaining connected components of the pair - graph @xmath21 are either of the type @xmath209 for @xmath140 or the type @xmath210 for @xmath211 . the first statement follows from the preceding discussion and the definition of the pair - graph @xmath21 . any path @xmath212 from the identity @xmath4 to @xmath213 corresponds uniquely to a path @xmath214 from @xmath122 to @xmath215 so the connected component of @xmath140 is @xmath209 . for @xmath185 if @xmath121 is an isolated vertex its connected component is @xmath210 , otherwise it is connected to an @xmath140 so its connected component is of the type @xmath216 . a consequence of the above proposition is that an arbitrary connected component @xmath217 of @xmath21 has cardinality equal to @xmath218 or 1 . moreover , for first case , we also have @xmath219 .    for cayley graphs , the number of connected components of the graph is the index @xmath220 $ ] . the existence of isolated vertices even for non empty generating sets makes the situation for pair - graphs slightly more complicated . [ components]the number of connected components of @xmath221 is @xmath222 { } { } +   \vert g - h \vert   -   \left\vert \bigcup_{s \in s_{o } } h s \right\vert .\ ] ]    by the preceding proposition , the first term in the formula is the number of connected components @xmath216 that occur on @xmath5 , the second and third terms count the number of isolated points in @xmath170 , by proposition [ isolated ] . since there are not connections between elements of @xmath170 , this is the number of connected components of the graph .    proposition [ comps ] and theorem [ components ] completely characterize the connected components for the pair - graphs @xmath21 for given group @xmath6 , subgroup h and valid subset @xmath138 .    for the pair - graph of example [ example1 ] we have @xmath39 , since @xmath223 , @xmath5 is generated by @xmath224 and the first term is 1 , the second term is 8 and since all the cosets are represented the last term is 8 , and we get 1 connected component . for the pair - graphs generated by @xmath201 and @xmath225 of example [ example2 ] , in both cases the first term is 2 , the next term is @xmath226 , and the final term is @xmath227 for the graph generated by @xmath201 and @xmath226 for the graph generated by @xmath225 , therefore @xmath228 has 6 connected components and @xmath229 has 2 connected components as confirmed visually in the diagrams . a graph is _ vertex transitive _ when for any pair of different vertices @xmath121 and @xmath230 there is graph automorphism @xmath45 such that @xmath231 . cayley graphs are naturally vertex transitive by means of left translations @xmath232 with @xmath233 . any vertex transitive graph must be regular , therefore by proposition [ coset ] , we have the following result . nontrivial pair - graphs @xmath21 are not vertex transitive when @xmath137 \geqslant 3 $ ] .    however , we still see restricted transitivity when considering left translations by elements of @xmath5 on @xmath21 .    [ leftaction]the left action of h in @xmath21 is a graph automorphism . moreover , for any @xmath234 , the action is transitive . the same holds for any coset @xmath5x , @xmath235 .    for @xmath140 and @xmath57 , the edge @xmath236 is in @xmath237 . now , for @xmath238 , the images of @xmath122 , and @xmath239 under the left action @xmath240 are @xmath241 and @xmath242 , which are adjacent in @xmath243 . the map is a bijection , and has inverse @xmath244 so it is a graph automorphism . for @xmath234 , consider @xmath245 , then @xmath246 as required . for @xmath247 , take @xmath238 such that @xmath248 . note that the left action of arbitrary @xmath233 is not necessarily a graph automorphism . for instance , in example [ graph1 ] the action of @xmath249 is not a graph endomorphism , as the image of @xmath150 is @xmath151 , and @xmath250 , but @xmath251 . let @xmath252 be the set of complex valued functions defined on @xmath6 , and consider @xmath253 the left regular representation of @xmath5 given by the action @xmath254 for h@xmath255 and @xmath235 . recall that for any graph with vertices on @xmath6 we can associate the adjacency operator @xmath88 , acting on @xmath252 in the following way , @xmath256    [ leftreg]let @xmath88 be the adjacency matrix for a group - subgroup pair graph @xmath21 , then for any @xmath140 @xmath257    note that for the pair - graph @xmath21 and @xmath258 , the adjacency operator is given by    @xmath259    the result then follows from direct calculation by considering that for any @xmath235 , @xmath121 and @xmath260 are in the same coset , in other words , @xmath261 for any @xmath140 . for @xmath140 , @xmath262 is a permutation matrix for the elements of @xmath6 corresponding to the left multiplication by @xmath122 . by theorem 15.2 of @xcite , a bijection @xmath45 of the vertices of a graph is a graph automorphism if @xmath263 , where @xmath264 is the permutation matrix associated with @xmath45 ; therefore proposition [ leftreg ] is only a representation theoretic restatement of proposition [ leftaction ] . the trivial eigenvalue of a @xmath0-regular graph is @xmath265 and it corresponds to any constant eigenfunction @xmath266 on the vertices of the graph . by extension , the trivial eigenvalue of a cayley graph @xmath13 is @xmath265 . in this section we extend this notion to the group - subgroup pair graphs . [ trivialeigen]let @xmath6 be a group , @xmath5 a subgroup of @xmath6 of index @xmath267 = k+1 $ ] with @xmath268 , and  @xmath138 a nonempty subset with @xmath30 symmetric and @xmath269 . consider @xmath270 a set of representatives of the cosets of @xmath5 in @xmath6 and set @xmath271 , for @xmath272 $ ] .  then @xmath273 are eigenvalues of the graph @xmath21 . a corresponding eigenfunction is defined by    @xmath274 . \end{cases}\ ] ]    note that the numbers @xmath275 satisfy @xmath276 then , for @xmath140 , we have @xmath277 similarly , for @xmath278 , @xmath279 , @xmath280    note that for the case @xmath281 , @xmath282 is an eigenvalue with corresponding eigenvector @xmath283 as defined in the above theorem , but @xmath284 so it is not an eigenfunction .    with the same notation as before , the eigenvalue @xmath282 is the largest eigenvalue of the graph @xmath21 with multiplicity @xmath285 $ ] . first , consider the case of a connected pair - graph @xmath21 , in particular @xmath286 for all @xmath272 $ ] and the eigenfunction @xmath283 takes only positive values . by thm . 8.1.4 and cor . 8.1.5 of @xcite , any eigenfunction that only takes nonzero values of the same sign corresponds to the largest eigenvalue , which has multiplicity 1 . the proposed eigenfunction satisfies this condition , therefore corresponds to the largest eigenvalue and it is an eigenvalue of multiplicity one , so the statement of the proposition follows .    for the remaining case , let @xmath140 and consider the connected component @xmath216 as a subgraph of @xmath21 and note that @xmath287 is an eigenfunction of @xmath216 with eigenvalue @xmath282 . then by  the same argument as before , @xmath282 is the largest eigenvalue of @xmath216 with multiplicity 1 . now , it is well known that the characteristic polynomial @xmath288 of the graph @xmath289 is the product of the characteristic polynomials of its connected components , @xmath290 where @xmath291 is the number of connected components of @xmath21 containing elements of @xmath5 and @xmath292 the number of isolated vertices . moreover , since @xmath275 is the largest root of @xmath293 for each @xmath80 , then is the largest root of @xmath294 and therefore the largest eigenvalue of @xmath21 . furthermore , since @xmath282 is a simple eigenvalue for each of the subgraphs @xmath295 , then by theorem [ components ] @xmath282 is an eigenvalue of @xmath21 with multiplicity equal to @xmath285 $ ] .    from the decomposition of the characteristic polynomial of the adjacency matrix , we can obtain a bound for the multiplicity of the eigenvalue @xmath296 .    with the same notation as before , @xmath297 is an eigenvalue of multiplicity at least @xmath298 of the nontrivial pair - graph @xmath21 . first , suppose that the pair - graph @xmath21 contains isolated vertices , then from the decomposition of the characteristic polynomial of the adjacency matrix we have that @xmath296 is an eigenvalue with multiplicity at least the number of isolated components , by [ components ] this number is @xmath299 . for a general pair - graph @xmath21 , consider an eigenfunction @xmath266 associated with the eigenvalue @xmath300 with @xmath301 for @xmath140 , then @xmath266 must satisfy the @xmath302 linear equations @xmath303 the matrix @xmath304 corresponding to this system is a @xmath305 matrix , then from elementary linear algebra it holds that @xmath302 is an upper bound for the rank of @xmath304 . therefore the kernel of @xmath306 has dimension at least @xmath307 , so the multiplicity of the eigenvalue @xmath296 is at least @xmath307 . the result follows from considering the two cases at the same time . the pair - graph in example [ finitefield ] , has @xmath308 , with four cosents of degree 2 and two cosets of degree 4 , therefore the trivial eigenvalues are @xmath309 . the pair - graph in example [ random ] has @xmath310 , with two cosets of degree 2 and one coset of degree 3 , then @xmath311 are the corresponding trivial eigenvalues . the pair - graph in example [ bipartite ] has @xmath312 , @xmath313 , therefore the trivial eigenvalues are @xmath314 and @xmath315 . a graph is _ bipartite _ when there is a bipartition @xmath316 of the vertices such that any pair of vertices in the same subset are not adjacent . for a group @xmath6 and symmetric subset @xmath12 , if there is an homomorphism @xmath317 , such that @xmath318 then the cayley graph @xmath13 is bipartite , this condition is also necessary when the graph is connected .    if a group homomorphism @xmath317 , such that @xmath319 exists , then the graph @xmath21 is bipartite . the converse is true if @xmath21 is connected and @xmath12 is symmetric . the proof of this proposition is the same as the one for cayley graphs , see for example chapter 4 of @xcite . note that if such a homomorphism exists then @xmath320 , so the elements of @xmath12 and @xmath321 would be on the same partition . [ bipartite]let @xmath322 , the alternating group of 4 letters , @xmath5 , the klein four group embedded as a subgroup of @xmath6 , and @xmath323 , @xmath324 , @xmath325 , @xmath326 , @xmath327 , @xmath328 , using cycle notation . observe that @xmath329 , the inverse of @xmath330 , is not contained in @xmath12 . the resulting @xmath21 is a bipartite graph . any homomorphism @xmath317 with @xmath331 , would have @xmath332 , but in this case @xmath333 , therefore there are no homomorphisms that satisfy the conditions .    for the case @xmath334 , the sets @xmath5 and @xmath170 are a bipartition of @xmath21 , so the nontrivial pair - graphs @xmath110 with with @xmath334 are bipartite . an example can be seen in figure [ graph1 ] . from the results of section @xmath335 , a group - subgroup pair graph @xmath156 is regular when @xmath61 , or when @xmath5 is a subgroup or order 2 and @xmath30 is empty . in this section we restrict to the latter case , where the resulting pair - graph is also bipartite . [ bipcayley]let @xmath6 , @xmath5 and @xmath12 be as described above . if @xmath12 is a symmetric set , the resulting @xmath21 is a cayley graph . namely , @xmath336 . the conditions imply that @xmath41 , then by the alternative definition of the pair - graph the edges are given by @xmath337 since s is symmetric one can simply write @xmath338 , @xmath339 , @xmath340 , which is the definition of cayley graph . proposition [ bipcayley ] states another way in which the graph @xmath341 can be seen as a generalization of certain class of bipartite cayley graphs . as an example , for @xmath342,@xmath343 prime numbers , when @xmath342 is not a square modulo @xmath343 , the @xmath344 ramanujan graphs from lubotzky , phillips and sarnak @xcite can be identified with pair - graphs @xmath345 .      in this section and the next one we fix a group @xmath6 and subgroup @xmath5 of order @xmath77 and index 2 . let @xmath346 denote the power set of @xmath170 . in this section we consider transformations on the generating sets that result in isomorphic group - subgroup pair graphs . [ rigact]let @xmath347 , if @xmath348 , where @xmath349 is the right translation by @xmath238 , then @xmath350 . for @xmath238 consider the map @xmath351 , defined as @xmath352 for @xmath117 and @xmath353 for @xmath140 . the map is clearly bijective , then for @xmath354 , we have @xmath355 with @xmath356 , therefore is an graph homomorphism with inverse @xmath357 and the graphs @xmath228 and @xmath229 are isomorphic . let @xmath347 , if @xmath358 , where @xmath359 is a group automorphism of g , then the pairs graphs @xmath228 and @xmath360 are isomorphic .    since @xmath137 = 2 $ ] , @xmath5 is invariant under @xmath359 , then for any @xmath361 , @xmath362 with @xmath363 , therefore @xmath359 is a graph isomorphism with inverse @xmath364 . any orbit on @xmath346 of right actions @xmath365 by elements of @xmath5 and group isomorphisms @xmath359 of @xmath6 consists of sets that generate isomorphic graphs .      as mentioned in the beginning of the section , under the current assumptions the pair - graphs @xmath21 are regular bipartite . the spectrum of these graphs is symmetric about 0 and its largest eigenvalue is the trivial eigenvalue @xmath366 . moreover , any eigenvalue @xmath1 satisfies latexmath:[$| \mu    pair - graph @xmath21 is given by    @xmath368    if @xmath369 and @xmath370 , then the adjacency operator of @xmath371 is the sum of the adjacency operators of @xmath228 and @xmath229 .    follows from the definition @xmath372    for a graph @xmath373 , the complement graph is @xmath374 , where @xmath375 , if and only if @xmath376 for @xmath377 . the eigenvector and eigenvalues of a @xmath0-regular graph and its complement can be related , see for example lemma 8.5.1 of @xcite . we present a relation between the of eigenvalues and eigenvectors for pair - graphs @xmath228 and @xmath378 with @xmath369 and @xmath370 . first , assume that @xmath379 , @xmath380 , then any constant function @xmath266 is an eigenfunction of both of the pair - graphs @xmath381 and @xmath229 corresponding to @xmath382 and @xmath383 respectively . similarly , for @xmath384 , the function @xmath385 is an eigenfunction of @xmath228 and @xmath229 corresponding to @xmath386 and @xmath387 . [ symmetry]let @xmath201 and @xmath225 as before with @xmath388 for numbers @xmath389 , then    \(i ) if @xmath228 is not connected , then there are independent eigenfunctions @xmath266 and @xmath390 of @xmath228 associated to @xmath391 such that @xmath392 is an eigenfunction of of @xmath229 corresponding to the eigenvalue @xmath393 . \(ii ) if @xmath266 is an eigenfunction of @xmath228 associated with an eigenvalue @xmath394 , then @xmath266 is an eigenfunction of @xmath229 corresponding to the eigenvalue @xmath393 . denote the adjacency graph operator of graphs @xmath395 , @xmath229 , @xmath371 as @xmath396 respectively , so that @xmath397 .    _ ( i ) _ for a connected components @xmath217 of @xmath202 , consider the function @xmath398 or @xmath399 , which can be verified to be eigenfunctions corresponding to @xmath265 and @xmath400 , respectively . we can similarly define @xmath390 with respect to a different connected component @xmath401 of @xmath228 . note that there are no isolated vertices on the graph , therefore by proposition [ comps ] , all the connected components have the same cardinality , in particular @xmath402 and @xmath403 . then , we have @xmath404    it follows that @xmath405 or @xmath406 depending on the whether @xmath265 or @xmath400 . by the preceding discussion , we have @xmath407 and @xmath408 _ ( iii ) _ for an eigenfunction @xmath266 of @xmath88 corresponding to an eigenvalue @xmath409 , we have @xmath410 therefore it suffices to prove @xmath411 . in other words , it suffices to prove the two equalities @xmath412 @xmath413 first , not that for fixed @xmath414 we have @xmath415 then , by summing over all elements of @xmath201 , @xmath416 since @xmath266 is an eigenfunction associated with @xmath1 , we have @xmath417 therefore we have @xmath418 similarly , by fixing @xmath414 and using the equation @xmath419 we obtain the relation @xmath420 finally , combining ( [ eqn : eqn1 ] ) and ( [ eqn : eqn2 ] ) , we obtain the equations @xmath421 @xmath422 since @xmath423 , we conclude @xmath424 @xmath425 and the proof is complete . recall that when @xmath228 is not connected , by theorem [ trivialeigen ]  the eigenvalue @xmath265 has multiplicity equal to the number @xmath426 of connected components of @xmath228 , then by @xmath427 the graph @xmath229 also has the eigenvalue @xmath428 with multiplicity @xmath429 . we can reformulate the result as follows . [ symm]for group @xmath6 and subgroup @xmath5 of index @xmath335 and order @xmath77 . let @xmath430 with @xmath431 and @xmath432 the spectrum of the pair - graph @xmath21 . then there is a @xmath433-regular pair - graph @xmath434 with spectrum @xmath435 such that @xmath436 for @xmath437 .    for @xmath438 , @xmath439 ,  and @xmath440 , @xmath441 , @xmath442 , @xmath50 , @xmath443 , @xmath444 , @xmath445 , @xmath446 we have the @xmath228 and @xmath229 pair - graphs shown in figure [ fig : corrgraphs ] . table [ table1 ] contains the values of the positive eigenvalues for both of the graphs . since both graphs are bipartite the remaining eigenvalues correspond to the negatives of the ones shown . .the positive values of the spectrum of the previous graphs . [ cols="^,^",options="header " , ]     note that @xmath447 , but @xmath448 is such that @xmath449 by proposition [ rigact ] , and @xmath450 . recall that a ramanujan graph is a connected @xmath0-regular graph such that for every eigenvalue @xmath1 different from @xmath451 , one has @xmath452    [ eigenbound]with the same assumptions as before . if the pair graph @xmath21 is connected and @xmath453 then it is a bipartite ramanujan graph .    due to theorem [ symmetry ] any @xmath0-regular pair - graph @xmath237 has nontrivial eigenvalues @xmath1 satisfying @xmath454 . also , the pair - graph @xmath21 is a ramanujan graph when said trivial eigenvalues satisfy @xmath455 . considering the two inequalities , it follows that all @xmath0-regular pair - graphs @xmath21 with @xmath456 or @xmath457 are ramanujan graphs . let @xmath458 , @xmath459 . the set @xmath460 , @xmath461 , @xmath462 , @xmath463 , @xmath464 , @xmath465 , @xmath466 , @xmath467 is such that @xmath468 satisfy the bound of the corollary , so the corresponding @xmath21 graph is ramanujan . its spectrum consist of @xmath469 with multiplicity 1 , @xmath470 with multiplicity 2 and 0 with multiplicity 18 . note that it contains the eigenvalues @xmath470 and as expected by theorem [ symmetry ] , the corresponding @xmath227-regular graph , generated by @xmath471 , @xmath472 , @xmath473 , @xmath474 has 3 connected components . both of the pair - graphs are shown in figure [ fig : ramgcor ] . let @xmath475 and @xmath476 . then @xmath477 and @xmath478 , in this case by corollary [ eigenbound ] , for any subset @xmath12 with @xmath479 , the resulting pair - graph @xmath21 graph is ramanujan . for a random choice of @xmath12 we obtain the @xmath445-regular ramanujan pair graph @xmath21 shown in figure [ fig : ramgff ] .    in this case , the pair - graph @xmath480 of figure [ ramgraph2 ] , generated by the complement of @xmath12 in @xmath170 , is a @xmath53-regular ramanujan graph . this shows that the result of corollary [ eigenbound ] is not a necessary condition , as mentioned in the above remark . as mentioned in the introduction , ramanujan graphs are graphs with good connectivity ( as measured by the isoperimetric constant of the graph ) . since the addition of edges to a graph results in a graph with greater or equal connectivity , it is expected for graphs with large amount of vertices to have good connectivity . this can be confirmed in the above examples , as the ramanujan pair - graphs @xmath21 resulting from using the bound provided by corollary @xmath481 , for group @xmath6 and subgroup @xmath5 of order @xmath482 , have generating set @xmath12 satisfying @xmath483 . then , corollary @xmath481 can also be stated as follows : the set of graphs @xmath484 consists only of ramanujan graphs when @xmath485 , where @xmath5 is a subgroup of order @xmath77 and @xmath137 = 2 $ ] . [ diagramsummary ]     the general properties of group - subgroup pair graphs according to the choice of @xmath486 and @xmath487 are shown in diagram [ diagramsummary ] . for arbitrary pair - graph @xmath21 a set of trivial eigenvalues can be determined including  the largest eigenvalue of the graph . according to the index of the subgroup the pair - graph can be regular ( index 1 or 2 ) or never be regular . if the generating set is contained in complement of the subgroup , the pair - graph is bipartite or multipartite . the pair - graphs are cayley graphs in two cases : when the subgroup and the group are equal and when the subgroup is of order 2 and the graphs is regular bipartite with symmetric generating set . the symmetry on the generating set also makes easier to verify if the given pair - graph is bipartite . these observations suggest that further research on the matter may be started with graphs with symmetric subsets before considering the general case . the author was supported by the japanese government ( monbukagakusho : mext ) scholarship . the author would like to express his gratitude to professor masato wakayama for providing the motivation for the present work and for the invaluable discussions and support . the author would also like to thank professors yoshinori yamasaki ,  miki hirano and kazufumi kimoto  for their valuable comments and discussion , regarding the definition of the group - subgroup pair graph during the event `` zeta functions in okinawa 2013 '' ; and mr . hiroto inoue for his valuable suggestions on the statements and proofs of some of the results . g. a.  margulis . explicit group - theoritical constructions of combinatorial schemes and their applications to the design of expanders and concentrator . _ journal problems of information transmission _ , 24,1:5160 , 1988 .
in this paper we introduce a cayley - type graph for group - subgroup pairs and present some elementary properties of such graphs , including connectedness , their degree and partition structure , and vertex - transitivity . 
 we relate these properties to those of the underlying group - subgroup pair . from the properties of the group , subgroup and generating set some of the eigenvalues can be determined , including the largest eigenvalue of the graph . 
 in particular , when this construction results in a bipartite regular graph we show a sufficient condition on the size of the generating sets that results on ramanujan graphs for a fixed group - subgroup pair 
 . examples of ramanujan pair - graphs that do not satisfy this condition are also provided , to show that the condition is not necessary .