Month: May 2005

Interdisciplinary research: Building off a provocative post by Eszter Hargittai at Crooked Timber, Cosma Shalizi posts some interesting thoughts on how to do (and how not to do) interdisciplinary scientific research. Look for the followups too, including the link to Aaron Clauset’s post.

How does quantum information and computation stack up in this vein? One healthy thing is that quite a few computer scientists attend conferences that are predominantly physics-oriented. Conversely, while there’s only one regular conference in the field that’s predominantly computer science oriented (QIP), so far as I know, a reasonable number of physicists attend that.

I like Macs. I always have, ever since the day I first saw MacPaint running on one of the original Macs (I believe it 128k!)

But I do have a question for all the Mac zealots out there. If System 10 is so terrific, then why did it take the brilliant engineers at Apple two decades to figure out that running Unix was a good idea? Unix hasn’t changed so much in that time.

I’m going to switch topics now, moving to the more physical topic of Fermions and the Jordan-Wigner transform. I’ve actually written papers using this stuff, but it’s only in writing these notes that I really feel like I’ve understood it well.

The series on expanders isn’t finished – I’ll be back with another installment in a day or two, and there will be several more installments after that.

General introductory note and prerequisites: This post is one in a series describing fermi algebras, and a powerful tool known as the Jordan-Wigner transform, which allows one to move back and forth between describing a system as a collection of qubits, and as a collection of fermions. The posts assume familiarity with elementary quantum mechanics, comfort with elementary linear algebra (but not advanced techniques), and a little familiarity with the basic nomenclature of quantum information science (qubits, the Pauli matrices).

Introduction

When you learn undergraduate quantum mechanics, it starts out being all about wavefunctions and Hamiltonians, finding energy eigenvalues and eigenstates, calculating measurement probabilities, and so on.

If your physics education was anything like mine, at some point a mysterious jump occurs. People teaching more advanced subjects, like quantum field theory, condensed matter physics, or quantum optics, start “imposing canonical commutation relations” on various field operators.

Any student quickly realizes that “imposing canonical commutation relations” is extremely important, but, speaking personally, at the time I found it quite mysterious exactly what people meant by this phrase. It’s only in the past few years that I’ve obtained a satisfactory understanding of how this works, and understood why I had such trouble in the first place.

These notes contain two parts. The first part is a short tutorial explaining the Fermionic canonical commutation relations (CCRs) from an elementary point of view: the different meanings they can have, both mathematical and physical, and what mathematical consequences they have. I concentrate more on the mathematical consequences than the physical in these notes, since having a good grasp of the former seems to make it relatively easy to appreciate the latter, but not so much vice versa. I may come back to the physical aspect in some later notes.

The second part of the notes describes a beautiful application of the Fermionic CCRs known as the Jordan-Wigner transform. This powerful tool allows us to map a system of interacting qubits onto an equivalent system of interacting Fermions, or, vice versa, to map a system of Fermions onto a system of qubits.

Why is this kind of mapping interesting? It’s interesting because it means that anything we understand about one type of system (e.g., Fermions) can be immediately applied to learn something about the other type of system (e.g., qubits).

I’ll describe an application of this idea, taking what appears to be a very complicated one-dimensional model of interacting spin-[tex]\frac 12[/tex] particles, and showing that it is equivalent to a simple model of non-interacting Fermions. This enables us to solve for the energy spectrum and eigenstates of the original Hamiltonian. This has, of course, intrinsic importance, since we’d like to understand such spin models – they’re important for a whole bundle of reasons, not the least of which is that they’re perhaps the simplest systems in which quantum phase transitions occur. But this example is only the tip of a much larger iceberg: the idea that the best way of understanding some physical systems may be to map those systems onto mathematically equivalent but physically quite different systems, whose properties we already understand. Physically, we say that we introduce a quasiparticle description of the original system, in order to simplify its understanding. This idea has been of critical importance in much of modern physics, including the understanding of superconductivity and the quantum Hall effect.

Another application of the Jordan-Wigner transform, which I won’t describe in detail here, but which might be of interest to quantum computing people, is to the quantum simulation of a system of Fermions. In particular, the Jordan-Wigner transform allows us to take a system of interacting Fermions, and map it onto an equivalent model of interacting spins, which can then, in principle, be simulated using standard techniques on a quantum computer. This enables us to use quantum computers to efficiently simulate systems of interacting Fermions. This is not a trivial problem, as can be seen from the following quote from Feynman, in his famous 1982 paper on quantum computing:

“[with Feynman’s proposed quantum computing device] could we imitate every quantum mechanical system which is discrete and has a finite number of degrees of freedom? I know, almost certainly, that we could do that for any quantum mechanical system which involves Bose particles. I’m not sure whether Fermi particles could be described by such a system. So I leave that open.”

It wasn’t until 20 years later, and the work by Somma, Ortiz, Gubernatis, Knill and Laflamme (Physical Review A, 2002) that this problem was resolved, by making use of the Jordan-Wigner transform.

The next post will introduce the canonical commutation relations for fermions, and discuss something of their mathematical and physical significance.

Note: This post is one in a series introducing one of the deepest ideas in modern computer science, expander graphs. Expanders are one of those powerful ideas that crop up in many apparently unrelated contexts, and that have a phenomenally wide range of uses. The goal of the posts is to explain what an expander is, and to learn just enough about them that we can start to understand some of their amazing uses. The posts require a little background in graph theory, computer science, linear algebra and Markov chains (all at about the level of a first course) to be comprehensible. I am not an expert on expanders, and the posts are just an introduction. They are are mostly based on some very nice 2003 lecture notes by Nati Linial and Avi Wigderson, available on the web at http://www.math.ias.edu/~boaz/ExpanderCourse/.

Today’s post digresses to explain one of the most interesting ideas in graph theory, namely, to describe a graph through its adjacency matrix. By describing a graph in terms of matrices we enable all the powerful tools of linear algebra to be brought to bear on graph theory, and we’ll see that there are all sorts of interesting connections between graphs and linear algebraic concepts such as eigenvalues. The connection to expanders will be explained in later posts, where we’ll see that the expansion parameter is connected to the second largest eigenvalue of the adjacency matrix. I believe (but have not checked) that it is this result which is used to establish that the graphs described in the previous post are actually expanders.

Graphs and their adjacency matrices

How can we prove that a family of graphs is an expander? Stated another way, how does the expansion parameter [tex]h(G)[/tex] vary as the graph [tex]G[/tex] is varied over all graphs in the family?

One way of tackling the problem of computing [tex]h(G)[/tex] is to do a brute force calculation of the ratio [tex]|\partial S|/|S|[/tex] for every subset [tex]S[/tex] of vertices containing no more than half the vertices in the graph. Doing this is a time-consuming task, since if there are [tex]n[/tex] vertices in the graph, then there are exponentially many such subsets [tex]S[/tex].

Problem: In general, how hard is it to find the subset [tex]S[/tex] minimizing [tex]|\partial S|/|S|[/tex]? Can we construct an NP-Complete variant of this problem? I don’t know the answer to this question, and I don’t know if anyone else does, either.

Fortunately, there is an extraordinarily beautiful approach to the problem of determining [tex]h(G)[/tex] which is far less computationally intensive. It involves the adjacency matrix [tex]A(G)[/tex] of the graph [tex]G[/tex]. By definition, the rows and columns of the adjacency matrix are labelled by the vertices of [tex]V[/tex]. For vertices [tex]v[/tex] and [tex]w[/tex] the entry [tex]A(G)_{vw}[/tex] is defined to be [tex]1[/tex] if [tex](v,w)[/tex] is an edge, and [tex]0[/tex] if it is not an edge.

It is a marvellous fact that properties of the eigenvalue spectrum of the adjacency matrix [tex]A(G)[/tex] can be used to understand properties of the graph [tex]G[/tex]. This occurs so frequently that we refer to the spectrum of [tex]A(G)[/tex] as the spectrum of the graph [tex]G[/tex]. It is useful because the eigenvalue spectrum can be computed quickly, and certain properties, such as the largest and smallest eigenvalue, the determinant and trace, can be computed extremely quickly.

More generally, by recasting graphs in terms of adjacency matrices, we open up the possibility of using tools from linear algebra to study the properties of graphs. Although we’re most interested in studying expanders, for the rest of this post I’m going to digress from the study of expanders, studying how the linear algebraic point of view can help us understand graphs, without worrying about how this connects to expanders. This digression is partially motivated by the fact that this is beautiful stuff (at least in my opinion), and is partially because our later discussion of expanders will be based on this linear algebraic point of view, and so it’s good to get comfortable with this point of view.

The following exercise provides a good example of how graph properties can be related to the eigenvalues of the graph.

Exercise: Prove that if two graphs are isomorphic, then they have the same spectrum.

This result is often useful in proving that two graphs are not isomorphic: simply compute their eigenvalues, and show that they are different. A useful extension of the exercise is to find an example of two graphs which have the same spectra, but which are not isomorphic.

Note that the adjacency matrix may be considered as a matrix over any field, and the result of the exercise is true over any field. (I’ve often wondered if the converse is true, but don’t know the answer.) Nonetheless, by and large, we’ll consider the adjacency matrix as a matrix over the field [tex]R[/tex] of real numbers. Assuming that [tex]G[/tex] is an undirected graph, we see that [tex]A(G)[/tex] is a real symmetric matrix, and thus can be diagonalized. We will find it convenient to write the eigenvalues of a graph [tex]G[/tex] in non-increasing order, as [tex]\lambda_1(G) \geq \lambda_2(G) \geq \ldots \geq \lambda_n(G)[/tex].

A fact we’ll make a lot of use of is that when [tex]G[/tex] is [tex]d[/tex]-regular the largest eigenvalue of [tex]G[/tex] is just [tex]d[/tex]. To see this, note that the vector [tex]\vec 1 \equiv (1,1,\ldots,1)[/tex] is an eigenvector of [tex]G[/tex] with eigenvalue [tex]d[/tex]. To prove that [tex]d[/tex] is the largest eigenvalue seems to be a little bit harder. We’ll just sketch a proof. To prove this it is sufficient to show that [tex]v^T A(G) v \leq d[/tex] for all normalized vectors [tex]v[/tex]. From the [tex]d[/tex]-regularity of [tex]G[/tex] it follows that [tex]A(G)/d[/tex] is a doubly stochastic matrix, i.e., has non-negative entries, and all rows and columns sum to one. A theorem of Birkhoff ensures that [tex]A(G)/d[/tex] can be written as a convex combination of permutation matrices, so [tex]A(G) = d \sum_j p_j P_j[/tex], where [tex]p_j[/tex] are probabilities, and the [tex]P_j[/tex] are permutation matrices. This gives [tex]v^T A(G) v = d \sum_j p_j v^T P_j v[/tex]. But [tex]v^T P_j v \leq 1[/tex] for any permutation [tex]P_j[/tex], which gives the desired result.

The following proposition gives another example of the relationships one can find between a graph and its spectrum.

Proposition: A [tex]d[/tex]-regular graph [tex]G[/tex] is connected if and only if [tex]\lambda_1(G) > \lambda_2(G)[/tex].

Proof: The easy direction is the reverse implication, for which we prove the contrapositive, namely, that a [tex]d[/tex]-regular disconnected graph has [tex]\lambda_1(G) = \lambda_2(G)[/tex]. This follows by breaking [tex]G[/tex] up into disconnected components [tex]G_1[/tex] and [tex]G_2[/tex], and observing that [tex]A(G) = A(G_1) \oplus A(G_2)[/tex], where [tex]\oplus[/tex] is the matrix direct sum. Since both [tex]G_1[/tex] and [tex]G_2[/tex] are [tex]d[/tex]-regular it follows that they both have maximal eigenvalue [tex]d[/tex], and so [tex]d[/tex] appears at least twice in the spectrum of [tex]A(G)[/tex].

At the moment, I don’t see an easy way of proving the forward implication. One not very satisfying proof is to observe that [tex]A(G)/d[/tex] is the Markov transition matrix for a random walk on the graph, and that since the graph is connected, the random walk must converge to a unique distribution, which implies that in the limit of large [tex]n[/tex] there can only be one vector [tex]v[/tex] such that [tex](G^n/d^n) v = v[/tex]. This means that [tex]G^n[/tex]’s largest eigenvalue is non-degenerate, from which it follows that [tex]G[/tex]’s largest eigenvalue is non-degenerate. This is a sketch, but it can all be established rigorously with a little work and the aid of well-known theorems on Markov chains.

The proof sketched in the previous paragraph is not really satisfactory, since it involves an appeal to theorems which are in some sense less elementary than the result under discussion. Another possibility which I’ve explored but haven’t made work with complete rigour is to investigate [tex]G^n/d^n[/tex] more explicitly. With a little thought one can prove that the entry [tex]G^n_{vw}[/tex] is just the number of paths between [tex]v[/tex] and [tex]w[/tex] of length [tex]n[/tex]. Since [tex]G[/tex] is connected, we’d expect in the limit of large [tex]n[/tex] this number would be dominated by a term which does not depend on [tex]w[/tex], and would just scale like the total number of paths of length [tex]n[/tex] starting at [tex]v[/tex] (which is [tex]d^n[/tex]), divided by the total number of possible destinations [tex]w[/tex], which is [tex]n[/tex], giving [tex]G^n_{vw}/d^n \rightarrow 1/n[/tex]. (This would only be true if [tex]G[/tex] has self-loops [tex](v,v)[/tex].) Of course, the matrix whose entries are all [tex]1/n[/tex] has a single eigenvalue [tex]1[/tex], with all the rest [tex]0[/tex], which would suffice to establish the theorem.

QED

Problem: How should we interpret the determinant of a graph? What about the trace?

Problem: If we consider [tex]A(G)[/tex] as a matrix over the field [tex]Z_2 = \{0,1\}[/tex], then it is possible to define a matrix sum [tex]G_1+G_2[/tex], whose adjacency matrix is just [tex]A(G_1)+A(G_2)[/tex], and a matrix product [tex]G_1 \times G_2[/tex] whose adjacency matrix is just [tex]A(G_1) A(G_2)[/tex]. Many questions naturally suggest themseves: (1) when is there an edge between [tex]v[/tex] and [tex]w[/tex] in [tex]G_1+G_2[/tex]; (2) when is there an edge between [tex]v[/tex] and [tex]w[/tex] in [tex]G_1 \times G_2[/tex] (these first two questions are easy to answer); (3) for which graphs is [tex]A(G)[/tex] invertible, and thus a natural inverse graph [tex]G^{-1}[/tex] exists; (4) how can we interpret the inverse graph; (5) when do two graphs commute?

Problem: Along similar lines to the previous problem, it’s possible to define a tensor product of graphs. What are the properties of the graph tensor product?

The ideas I’ve described in this post are examples of the important general principle that once you’ve defined a mathematical object, you should seek out alternate representations (or even just partial representations) of that object in terms of mathematical objects that you already understand. By recasting graphs as matrices, we open up the possibility of using all the tools of linear algebra to answer questions about graphs. This can work in one of two ways: we can ask a question about graphs, and try to see if it’s possible to give a linear algebraic answer, or we can ask what implication known results of linear algebra have for graphs – what does the Gaussian elimination procedure correspond to, or the spectral decomposition, or two matrices commuting, or the wedge product, or whatever. Exploring such connections has the potential to greatly enrich both subjects.

In this post we’ve started to get a feel for how the properties of graphs can be studied using linear algebra. In the next post we’ll turn our attention back to expanders, and understand how the expansion coefficient can be related to the gap [tex]\lambda_1(G)-\lambda_2(G)[/tex] between the largest and second largest eigenvalues of [tex]G[/tex].

Note: This post is one in a series introducing one of the deepest ideas in modern computer science, expander graphs. Expanders are one of those powerful ideas that crop up in many apparently unrelated contexts, and that have a phenomenally wide range of uses. The goal of the posts is to explain what an expander is, and to learn just enough about them that we can start to understand some of their amazing uses. The posts require a little background in graph theory, computer science, linear algebra and Markov chains (all at about the level of a first course) to be comprehensible. I am not an expert on expanders, and the posts are just an introduction. They are are mostly based on some very nice 2003 lecture notes by Nati Linial and Avi Wigderson, available on the web at http://www.math.ias.edu/~boaz/ExpanderCourse/.

Today’s post is a short post, giving some extremely useful explicit examples of expander graphs.

Explicit examples of expanders

We’ve seen previously that a family of [tex]d[/tex]-regular random graphs on [tex]n[/tex] vertices defines an expander. For applications it is often more useful to have more explicit constructions for expanders. In particular, for applications to algorithms it is often useful to construct expanders on [tex]O(2^n)[/tex] vertices, where [tex]n[/tex] is some parameter describing problem size. Just to store a description of a random graph on so many vertices requires exponentially much time and space, and so is not feasible. Fortunately, more parsimonious constructions are possible, which we now describe.

Example: In this example the family of graphs is indexed by a prime number, [tex]p[/tex]. The set of vertices for the graph [tex]G_p[/tex] is just the set of points in [tex]Z_p[/tex], the field of integers modulo [tex]p[/tex]. We construct a [tex]3[/tex]-regular graph by connecting each vertex [tex]x \neq 0[/tex] to [tex]x-1,x+1[/tex] and [tex]x^{-1}[/tex]. The vertex [tex]x=0[/tex] is connected to [tex]p-1,0[/tex] and [tex]1[/tex]. According to the lecture notes by Linial and Wigderson, this was proved to be a family of expanders by Lubotsky, Phillips and Sarnak in 1988, but I don’t know a lower bound on the expansion parameter. Note that even for [tex]p = O(2^n)[/tex] we can do basic operations with this graph (e.g., random walking along its vertices), using computational resources that are only polynomial in time and space. This makes this graph potentially far more useful in applications than the random graphs considered earlier.

Example: A similar but slightly more complex example is as follows. The vertex set is [tex]Z_m \times Z_m[/tex], where [tex]m[/tex] is some positive integer, and [tex]Z_m[/tex] is the additive group of integers modulo [tex]m[/tex]. The degree is [tex]4[/tex], and the vertex [tex](x,y)[/tex] has edges to [tex](x\pm y,y)[/tex], and [tex](x,x \pm y)[/tex], where all addition is done modulo [tex]m[/tex]. Something which concerns me a little about this definition, but which I haven’t resolved, is what happens when [tex]m[/tex] is even and we choose [tex]y = m/2[/tex] so that, e.g., the vertices [tex](x+y,y)[/tex] and [tex](x-y,y)[/tex] coincide with one another. We would expect this duplication to have some effect on the expansion parameter, but I haven’t thought through exactly what.

Unfortunately, I don’t know any more examples of expanders, although I’m sure there are some! Still, hopefully you will agree that these examples are pretty nice: they are easy to describe, and allow us to work with expander graphs on exponentially large vertex sets, without expending too much effort. I haven’t proved that these families are expanders: doing that requires some extra technical tools based on the adjacency matrix of a graph, which is the subject of the next post.

Note: This post is one in a series introducing one of the deepest ideas in modern computer science, expander graphs. Expanders are one of those powerful ideas that crop up in many apparently unrelated contexts, and that have a phenomenally wide range of uses. The goal of the posts is to explain what an expander is, and to learn just enough about them that we can start to understand some of their amazing uses. The posts require a little background in graph theory, computer science, linear algebra and Markov chains (all at about the level of a first course) to be comprehensible. I am not an expert on expanders, and the posts are just an introduction. They are are mostly based on some very nice 2003 lecture notes by Nati Linial and Avi Wigderson, available on the web at http://www.math.ias.edu/~boaz/ExpanderCourse/.

Introduction to expanders

Expander graphs are one of the deepest tools of theoretical computer science and discrete mathematics, popping up in all sorts of contexts since their introduction in the 1970s. Here’s a list of some of the things that expander graphs can be used to do. Don’t worry if not all the items on the list make sense: the main thing to take away is the sheer range of areas in which expanders can be applied.

• Reduce the need for randomness: That is, expanders can be used to reduce the number of random bits needed to make a probabilistic algorithm work with some desired probability.
• Find good error-correcting codes: Expanders can be used to construct error-correcting codes for protecting information against noise. Most astonishingly for information theorists, expanders can be used to find error-correcting codes which are efficiently encodable and decodable, with a non-zero rate of transmission. This is astonishing because finding codes with these properties was one of the holy grails of coding theory for decades after Shannon’s pioneering work on coding and information theory back in the 1940s.
• A new proof of PCP: One of the deepest results in computer science is the PCP theorem, which tells us that for all languages [tex]L[/tex] in NP there is a randomized polyonomial-time proof verifier which need only check a constant number of bits in a purported proof that [tex]x \in L[/tex] or [tex]x \not \in L[/tex], in order to determine (with high probability of success) whether the proof is correct or not. This result, originally established in the earlier 1990s, has recently been given a new proof based on expanders.

What’s remarkable is that none of the topics on this list appear to be related, a priori, to any of the other topics, nor do they appear to be related to graph theory. Expander graphs are one of these powerful unifying tools, surprisingly common in science, that can be used to gain insight into an an astonishing range of apparently disparate phenomena.

I’m not an expert on expanders. I’m writing these notes to help myself (and hopefully others) to understand a little bit about expanders and how they can be applied. I’m not learning about expanders with any specific intended application in mind, but rather because they seem to behind some of the deepest insights we’ve had in recent years into information and computation.

What is an expander graph? Informally, it’s a graph [tex]G = (V,E)[/tex] in which every subset [tex]S[/tex] of vertices expands quickly, in the sense that it is connected to many vertices in the set [tex]\overline S[/tex] of complementary vertices. Making this definition precise is the main goal of the remainder of this post.

Suppose [tex]G = (V,E)[/tex] has [tex]n[/tex] vertices. For a subset [tex]S[/tex] of [tex]V[/tex] we define the edge boundary of [tex]S[/tex], [tex]\partial S[/tex], to be the set of edges connecting [tex]S[/tex] to its complement, [tex]\overline S[/tex]. That is, [tex]\partial S[/tex] consists of all those edges [tex](v,w)[/tex] such that [tex]v \in S[/tex] and [tex]w \not \in S[/tex]. The expansion parameter for [tex]G[/tex] is defined by

[tex] h(G) \equiv \min_{S: |S| \leq n/2} \frac{|\partial S|}{|S|}, [/tex]

where [tex]|X |[/tex] denotes the size of a set [tex]X[/tex].

One standard condition to impose on expander graphs is that they be [tex]d[/tex]-regular graphs, for some constant [tex]d[/tex], i.e., they are graphs in which every vertex has the same degree, [tex]d[/tex]. I must admit that I’m not entirely sure why this [tex]d[/tex]-regularity condition is imposed. One possible reason is that doing this simplifies a remarkable result which we’ll discuss later, relating the expansion parameter [tex]h(G)[/tex] to the eigenvalues of the adjacency matrix of [tex]G[/tex]. (If you don’t know what the adjacency matrix is, we’ll give a definition later.)

Example: Suppose [tex]G[/tex] is the complete graph on [tex]n[/tex] vertices, i.e., the graph in which every vertex is connected to every other vertex. Then for any vertex in [tex]S[/tex], each vertex in [tex]S[/tex] is connected to all the vertices in [tex]\overline S[/tex], and thus [tex]|\partial S| = |S| \times |\overline S| = |S|(n-|S|)[/tex]. It follows that the expansion parameter is given by

[tex] h(G) = \min_{S: |S|\leq n/2} n-|S| = \left\lceil \frac{n}{2} \right\rceil. [/tex]

For reasons I don’t entirely understand, computer scientists are most interested in the case when the degree, [tex]d[/tex], is a small constant, like [tex]d = 2,3[/tex] or [tex]4[/tex], not [tex]d=n-1[/tex], as is the case for the complete graph. Here’s an example with constant degree.

Example: Suppose [tex]G[/tex] is an [tex]n \times n[/tex] square lattice in [tex]2[/tex] dimensions, with periodic boundary conditions (so as to make the graph [tex]4[/tex]-regular). Then if we consider a large connected subset of the vertices, [tex]S[/tex], it ought to be plausible that that the edge boundary set [tex]\partial S[/tex] contains roughly one edge for each vertex on the perimeter of the region [tex]S[/tex]. We expect there to be roughly [tex]\sqrt{|S|}[/tex] such vertices, since we are in two dimensions, and so [tex]|\partial S|/|S| \approx 1/\sqrt{|S|}[/tex]. Since the graph can contain regions [tex]S[/tex] with up to [tex]O(n^2)[/tex] vertices, we expect

[tex] h(G) = O\left( \frac{1}{n} \right) [/tex]

for this graph. I do not know the exact result, but am confident that this expression is correct, up to constant factors and higher-order corrections. It’d be a good exercise to figure out exactly what [tex]h(G)[/tex] is. Note that as the lattice size is increased, the expansion parameter decreases, tending toward [tex]0[/tex] as [tex]n\rightarrow \infty[/tex].

Example: Consider a random [tex]d[/tex]-regular graph, in which each of [tex]n[/tex] vertices is connected to [tex]d[/tex] other vertices, chosen at random. Let [tex]S[/tex] be a subset of at most [tex]n/2[/tex] vertices. Then a typical vertex in [tex]S[/tex] will be connected to roughly [tex]d \times |\overline S|/n[/tex] vertices in [tex]\overline S[/tex], and thus we expect [tex]|\partial S| \approx d \times |S| |\overline S|/n[/tex], and so

[tex] \frac{|\partial S|}{|S|} \approx d \frac{|\overline S|}{n}. [/tex]

Since [tex]|\overline S|[/tex] has its minimum at approximately [tex]n/2[/tex] it follows that [tex]h(G) \approx d/ 2[/tex], independent of the size [tex]n[/tex].

Exercise: Show that a disconnected graph always has expansion parameter [tex]0[/tex].

In each of our examples, we haven’t constructed just a single graph, but rather an entire family of graphs, indexed by some parameter [tex]n[/tex], with the property that as [tex]n[/tex] gets larger, so too does the number of vertices in the graph. Having access to an entire family in this way turns out to be much more useful than having just a single graph, a fact which motivates the definition of expander graphs, which we now give.

Suppose we have a family [tex]G_j = (V_j,E_j)[/tex] of [tex]d[/tex]-regular graphs, indexed by [tex]j[/tex], and such that [tex]|V_j| = n_j[/tex] for some increasing function [tex]n_j[/tex]. Then we say that the family [tex]\{ G_j \}[/tex] is a family of expander graphs if the expansion parameter is bounded strictly away from [tex]0[/tex], i.e., there is some small constant [tex]c[/tex] such that [tex]h(G_j) \geq c > 0[/tex] for all [tex]G_j[/tex] in the family. We’ll often abuse nomenclature slightly, and just refer to the expander [tex]\{ G_j \}[/tex], or even just [tex]G[/tex], omitting explicit mention of the entire family of graphs.

In this post we’ve defined expanders, said a little about what they’re useful for, and given an example – [tex]d[/tex]-regular random graphs – of an expander. In the next post, I’ll describe some more explicit and much more useful examples of expander graphs.

Over the next few weeks I’m going to try out an experimental blogging style, posting a series of rather more technical expository notes than has been my wont in the past.

I’m going to try to keep the tone light, but inevitably these posts will be more technical and demanding than most – though not all – of what I’ve posted in the past. I’ll also continue to post less technical stuff.

I expect it’ll take me a little while to settle into a style that works well. I’m aiming to keep things light and personal, but must admit that after drafting material for the past couple of weeks, I’m finding this more difficult than I imagined it would be.

I don’t think this difficulty is because it’s intrinsically especially difficult to do, but rather a reflection of habit: I’m most used to writing technical material – even expository material – in the impersonal manner common to journals. Getting out of that habit is going to take some work to get right. Feedback will help me figure out what works and what doesn’t, so keep the comments coming!

The initial topics will be: (1) a series on expander graphs, which are one of the most useful and beautiful tools in computer science, and (2) a series on Fermi algebras and the Jordan-Wigner transform, which are extremely useful tools in condensed matter physics.

These are, obviously, pretty specialized topics. I’ve tried to choose topics that are simultaneously: (1) subjects I wish to understand better; and (2) contain deep ideas of reasonably broad and current interest. I don’t expect that they’d be of much interest to, say, philosophers, but expect that the central ideas are of interest to a wide cross-section of physicists, mathematicians, and computer scientists. Furthermore, I’ll try focus on big ideas, and their relationship to the rest of science. Once again, learning to do this well is partially a question of style, and I expect I’ll get better at making these connections as I go along.

Depending on how things go, I may post further expository series in the future. I expect they’ll cover topics in some mixture of physics, computer science, mathematics, and self-development, with occasional digressions into other areas. I expect to range around a lot, through whatever interests me.

On a personal note, I’ve occasionally gotten queries from people about my blog, wondering if it “takes time away from your research”.

With this experiment I’m trying to integrate my blog more thoroughly with my research. Certainly, I find that writing expository notes like these is a good way of building up my own understanding of new subjects, and of preparing the way for new research projects. Indeed, I expect that some of these pieces will be useful warm-ups for some expository journal articles (and possibly books) that I hope to write in the future. I also feel very strongly about the value of synthesis and exposition for Science as a whole, especially the value of trying to explain things as simply as possible.

Finally, I must admit that I’m a little nervous about how this goes. These subjects are more specialized than much of what I’ve posted in the past, and I do enjoy having at least some regular readers! Here’s hoping I don’t drive you all away!

An email correspondent asks:

Is it valuable to have an “internal” blog area accessible only by members of your research group, for the sake of internal communication?

I’m about to set this up for my group, so I can’t give a definite yes or no from personal experience. I certainly think it’s worth trying, and I’ve heard from others who’ve tried it that it can be an effective way of helping keep people within a research group aware of what everyone else is doing. Wikis may also be useful for this purpose.

Aside from the warm feeling from having made a positive contribution to the community, has running a public blog been helpful to you?

I’ve spent quite a bit of time drafting and redfrafting responses to that. It was more difficult to answer than I expected, because while it seems like a simple question, it’s really a whole bundle of different questions. Blogging combines: (1) the discipline, clarity of thought, and creative impulse that comes from writing things down; (2) interaction with friends and colleagues; (3) interaction with a wider audience; (4) education and outreach; (5) publicity for one’s work, field, organization and profession; (6) the excitement of being part of a new medium, which is evolving quickly; (7) the opportunity to pontificate; (8) a bunch of other things that I’ve either forgotten or are ignorant of.

When you look at it this way, blogging combines a very wide range of activities, and all of these in some sense benefit various people (not always, but often, including me). So, yes, there is definitely a considerable benefit. Whether it is worth the time and effort is difficult to say. Personally, I think I’m only just now really figuring out how to blog in a way that I feel is effective, and fully justifies the investment of time.

My partner and I took up dancing recently (rhumba, waltz, jive, etc), and it’s been great fun. The music varies quite a bit, but never more so than in last night’s first choice of song, that well-known piece of music for progressive dance, AC/DC’s “Thunderstruck”.