2 trix, as explained below) we will use periodic bound- ary conditions in the x direction. Note that the proper q -coloring constraint implies that FBC$_{z}$ and PBC$_{z}$ are equivalent if L$_{z}$ = 2. The number of vertices for G = sc [( L$_{x}$ )$_{BCx}$ × ( L$_{y}$ )$_{BCy}$ × ( L$_{z}$ )$_{BCz}$] is n = L$_{x}$L$_{y}$L$_{z}$ . The specific form of Eq. (1.1) for our calculation is tion, we will denote the limit lim$_{L}$$_{x}$$_{, L}$$_{y}$ →∞ sc [( L$_{x}$ )$_{BCx}$ × ( L$_{y}$ )$_{BCy}$ × ( L$_{z}$ )$_{BCz}$] simply as S$_{(}$$_{L}$$_{z}$$_{)}$$_{BC}$$_{z}$ , where S stands for “slab”. We will consider both free (F) and periodic (P) boundary conditions in the z direction, and thus slabs such as S$_{3}$$_{F}$ , S$_{3}$$_{P}$ , etc. For technical reasons (to get an expression involving a trace of a coloring ma- To derive a lower bound on W ( S$_{(}$$_{L}$$_{z}$$_{)}$$_{BC}$$_{z}$ , q ), we gen- eralize the method of Refs. [11]-[14] from two to three dimensions. We consider two adjacent transverse slices of the slab orthogonal to the x direction, with x values x$_{0}$ and x$_{0}$ +1. These are thus sections of the square lattice of dimension L$_{y}$ × L$_{z}$ , which we denote G$_{x}$$_{0}$ = sq [( L$_{y}$ )$_{BC}$$_{y}$ × ( L$_{z}$ )$_{BC}$$_{z}$]$_{x}$$_{0}$ and G$_{x}$$_{0}$$_{+1}$ = sq [( L$_{y}$ )$_{BC}$$_{y}$ × ( L$_{z}$ )$_{BC}$$_{z}$]$_{x}$$_{0}$$_{+1}$. We label a particular color assignment to the vertices of G$_{x}$$_{0}$ that is a proper q -coloring of these vertices as C ( G$_{x}$$_{0}$ ) and similarly for G$_{x}$$_{0}$$_{+1}$ . The total number of proper q -colorings of G$_{x}$$_{0}$ is λ$_{T,max}$ . It follows that Now for the transverse slices G$_{x}$$_{0}$ and G$_{x}$$_{0}$$_{+1}$ , denoted generically as ts (( L$_{z}$ )$_{BC}$$_{z}$), the chromatic polynomial has the form where the c$_{j}$ are coefficients whose precise form is not needed here. The set of λ$_{ts}$$_{((}$$_{L}$$_{z}$$_{)}$$_{BC}$$_{z}$$_{)}$$_{,j}$ ’s is indepen- dent of the length L$_{y}$ and although this set depends on BC$_{y}$ , the maximal one (having the largest magnitude), λ$_{ts}$$_{((}$$_{L}$$_{z}$$_{)}$$_{BC}$$_{z}$$_{)}$$_{,max}$ , is independent of BC$_{y}$ (e.g., [16] and references therein). Hence, W ( S$_{(}$$_{L}$$_{z}$$_{)}$$_{BCz}$, q ) = lim L$_{y}$ →∞ lim L$_{x}$ $_{→∞}$[ P ( sc [( L$_{x}$ )$_{P}$ × ( L$_{y}$ )$_{BCy}$ × ( L$_{z}$ )$_{BCz}$] , q )] 1 /n . (2.1) lim L$_{x}$ $_{→∞}$[ P ( sc [( L$_{x}$ )$_{P}$ × ( L$_{y}$ )$_{BCy}$ × ( L$_{z}$ )$_{BC}$$_{z}$] , q )] 1 /L$_{x}$ = λ$_{T,max}$ . (2.4) P ( G$_{x}$$_{0}$, q ) = P ( G$_{x}$$_{0}$$_{+1}$, q ) = ∑ j c$_{j}$ ( λ$_{ts}$$_{((}$$_{L}$$_{z}$$_{)}$$_{BC}$$_{z}$$_{)}$$_{,j}$ ) L$_{y}$ (2.5) N = P ( G$_{x}$$_{0}$, q ) = P ( G$_{x}$$_{0}$$_{+1}$, q ) . (2.2) lim L$_{y}$ $_{→∞}$[ P ( G$_{x}$$_{0}$, q )] 1 /L$_{y}$ ≡ lim L$_{y}$ $_{→∞}$( N ) 1 /L$_{y}$ = λ$_{ts}$$_{((}$$_{L}$$_{z}$$_{)}$$_{BC}$$_{z}$$_{)}$$_{,max}$ . (2.6) P ( sc [2$_{F}$ × ( L$_{y}$ )$_{BCy}$ × ( L$_{z}$ )$_{BC}$$_{z}$] , q ) = ∑ j c ′ j ( λ$_{tube}$$_{((}$$_{L}$$_{z}$$_{)}$$_{BC}$$_{z}$$_{)}$$_{,j}$ ) L$_{y}$ (2.7) P ( sc [( L$_{x}$ )$_{P}$ × ( L$_{y}$ )$_{BCy}$ × ( L$_{z}$ )$_{BC}$$_{z}$] , q ) = Tr( T $^{L$_{x}$}$) . (2.3) lim L$_{y}$ →∞ [ P ( sc [2$_{F}$ × ( L$_{y}$ )$_{BCy}$ × ( L$_{z}$ )$_{BC}$$_{z}$] , q )] 1 /L$_{y}$ = = λ$_{tube}$$_{((}$$_{L}$$_{z}$$_{)}$$_{BC}$$_{z}$$_{)}$$_{,max}$ . (2.8) CS$_{j}$ ( T ) = N ∑ i =1 T$_{ij}$ , (2.9) Now let us add the edges in the x direction that join these two adjacent transverse slices of the slab together. Among the N 2 color configurations that yield proper q - colorings of these two separate yz transverse slices, some will continue to be proper q -colorings after we add these edges that join them in the x direction, while others will not. We define an N × N -dimensional coloring compat- ibility matrix T with entries T$_{C}$$_{(}$$_{G}$$_{x}$$_{0}$$_{)}$$_{,C}$$_{(}$$_{G}$$_{x}$$_{0}$$_{+1}$$_{)}$ equal to (i) 1 if the color assignments C ( G$_{x}$$_{0}$ ) and C ( G$_{x}$$_{0}$$_{+1}$ ) are proper q -colorings after the edges in the x direction have been added joining G$_{x}$$_{0}$ and G$_{x}$$_{0}$$_{+1}$ , i.e., if the color as- signed to each vertex v ( x$_{0}$, y, z ) in G$_{x}$$_{0}$ is different from the color assigned to the vertex v ( x$_{0}$ + 1 , y, z ) in G$_{x}$$_{0}$$_{+1}$ ; and (ii) 0 if the color assignments C ( G$_{x}$$_{0}$ ) and C ( G$_{x}$$_{0}$$_{+1}$ ) are not proper q -colorings after the edges in the x di- rection have been added, i.e., there exists some color as- signed to a vertex v ( x$_{0}$, y, z ) in G$_{x}$$_{0}$ that is equal to a color assigned to the vertex v ( x$_{0}$ + 1 , y, z ) in G$_{x}$$_{0}$$_{+1}$ . Clearly, T$_{ij}$ = T$_{ji}$ . The chromatic polynomial for the slab is then given by the trace The two adjacent slices together with the edges in the x direction that join them constitute the graph sc [2$_{F}$ × ( L$_{y}$ )$_{BCy}$ × ( L$_{z}$ )$_{BC}$$_{z}$]. We denote the chromatic polynomial for this section (tube) of the sc lattice as P ( sc [2$_{F}$ × ( L$_{y}$ )$_{BCy}$ × ( L$_{z}$ )$_{BC}$$_{z}$] , q ) (which is equal to P ( sc [2$_{P}$ ( L$_{y}$ )$_{BCy}$ ( L$_{z}$ )$_{BC}$$_{z}$] , q ) because of the proper q -coloring condition). This has the form where c ′ j are coefficients analogous to those in (2.5). Therefore, Now let us denote the column sum (CS) Since T is a real symmetric matrix, there exists an or- thogonal matrix A that diagonalizes T : ATA $^{−}$1 = T$_{diag.}$ . Let us denote the N eigenvalues of T as λ$_{T,j}$ , 1 ≤ j ≤ N . Since T is a real non-negative matrix, we can apply the generalized Perron-Frobenius theorem [17, 18] to infer that T has a real maximal eigenvalue, which we denote