JournalofCombinatorialTheory,SeriesA132(2015)58–101 ContentslistsavailableatScienceDirect Journal of Combinatorial Theory, Series A www.elsevier.com/locate/jcta Circular planar electrical networks: Posets and positivity Joshua Alman, Carl Lian, Brandon Tran Department of Mathematics, Massachusetts Institute of Technology, United States a r t i c l e i n f o a b s t r a c t Article history: Following de Verdière–Gitler–Vertigan and Curtis–Ingerman– Received 15 January 2014 Morrow, we prove a host of new results on circular planar Available online xxxx electrical networks. We first construct a poset EPn of electrical networks with nboundary vertices, and prove that KPleaynwaor rgdrsa:ph it is graded by number of edges of critical representatives. We Resistor network then answer various enumerative questions related to EPn, Network response adapting methods of Callan and Stein–Everett. Finally, we Poset study certain positivity phenomena of the response matrices Laurent phenomenon arising from circular planar electrical networks. In doing Electrical positroid so, we introduce electrical positroids, extending work of Postnikov, and discuss a naturally arising example of a Laurent phenomenon algebra, as studied by Lam–Pylyavskyy. ©2014 Elsevier Inc. Allrightsreserved. 1. Introduction Circular planar electrical networks are objects from classical physics: given a resistor network, one can compute its response to imposed voltages via the Dirichlet-to-Neumann map. An inverse boundary problem for electrical networks was studied in detail by de Verdière, Gitler, and Vertigan [5] and Curtis, Ingerman, and Morrow [4]: given the Dirichlet-to-Neumann map, can the network be recovered? E-mail addresses: [email protected](J.Alman), [email protected](C.Lian), [email protected] (B.Tran). http://dx.doi.org/10.1016/j.jcta.2014.11.004 0097-3165/©2014 Elsevier Inc. Allrightsreserved. J. Alman et al. / Journal of Combinatorial Theory, Series A 132 (2015) 58–101 59 In general, the answer is “no,” though much can be said about the information that can be recovered. If, for example, the underlying graph of the electrical network is known and is critical, the resistances are uniquely determined [4, Theorem 2]. Moreover, any two networks that produce the same response matrix can be related by a certain class of combinatorial transformations, the local equivalences [5, Théorème 4]. The goal of this paper is to study more closely the rich theory of circular planar electrical networks. We define a poset EP of circular planar graphs, under the operations n of contraction and deletion of edges, and investigate its properties. By [4, Theorem4]and [5, Théorème 3], the space of response matrices for circular planar electrical networks of order n decomposes as a disjoint union of open cells, each diffeomorphic to a product of copies of the positive real line. We then have: Theorem 3.1.3. If [H] and [G] are equivalence classes of circular planar graphs, then [H] ≤ [G] in EP if and only if Ω(H) ⊂ Ω(G), where Ω(H) denotes the space of n response matrices for conductances on H. Using the important tool of medial graphs developed in [4] and [5], we also prove: Theorem 3.2.4. EP is graded by number of edges of critical representatives. n We then obtain the following enumerative properties of EP via medial graphs, adapt- n ing techniques of Callan [3] and Stein and Everett [21]. Theorem 4.2.5. Put X =|EP |, the number of equivalence classes of electrical networks n n of order n. Then: (a) X =1 and 1 n(cid:2)−2 Xn =2(n−1)Xn−1+ (j−1)XjXn−j. j=2 (b) [tn−1]X(t)n = n ·(2n −3)!!, where X(t) is the generating function for the sequence {X }. i (c) X /(2n −1)!! →e−1/2 as n →∞. n Associated to any circular planar electrical network of order n is its n ×n response matrix, the Dirchlet-to-Neumann map expressed in a canonical basis. Response matrices are characterized in [4, Theorem 4] as the symmetric matrices with row sums equal to zero and circular minors non-negative. Furthermore, the strictly positive minors can be identified combinatorially using [4, Lemma 4.2]. A natural question that arises is: which sets of circular minors can be positive, while the others are zero? Postnikov [16] studied a similar question in the totally nonnegative 60 J. Alman et al. / Journal of Combinatorial Theory, Series A 132 (2015) 58–101 Grassmannian: for k ×n matrices A, with k < n and all k ×k minors nonnegative, which sets (matroids) of k×k minors can be the set of positive minors of A1? These special matroids, called positroids by Knutson, Lam, and Speyer [11], were found in [16] to index many interesting combinatorial objects. Two of these objects, plabic graphs and alternating strand diagrams, are highly similar to circular planar electrical networks and medial graphs. In light of this question, we give an axiomatization of electrical positroids, motivated by the Grassmann–Plücker relations. The following theorem shows that this notion is, in a sense, a natural extension of Postnikov’s theory of positroids: Theorem 5.2.1. A set S of circular pairs is the set of positive circular minors of a response matrix if and only if S is an electrical positroid. Finally, we consider positivity testsfor response matrices. In [8], Fominand Zelevinsky describe various positivity tests for totally positive matrices: given an n ×nmatrix, there exist sets of n2 minors whose positivity implies the positivity of all minors. Moreover, positivity tests are related to each other combinatorially via double wiring diagrams. Fomin and Zelevinsky later introduced cluster algebras in [9], in part, to study similar positivity phenomena. (cid:3) (cid:4) In a similar way, we describe positivity tests of size n for n ×nmatrices. Some such 2 sets were first described by Kenyon [10, §4.5.3]. While they do not form clusters in a cluster algebra, our positivity tests form clusters in a Laurent phenomenon algebra, as introduced by Lam and Pylyavskyy in [12]. We find: Theorem 6.2.16. There exists an LP algebra LM , isomorphic to the polynomial ring on (cid:3) (cid:4) n n generators, with an initial seed D of diametric circular minors. D is a positivity 2 n n test for circular minors, and furthermore, all “Plücker clusters” in LM , that is, clusters n of circular minors, are positivity tests. Moreover, LM is “doubly-covered” by a cluster algebra CM that behaves similarly n n to LM when we restrict to certain types of mutations. Further investigation of the n clusters leads to an analogue of weak separation, as studied by Oh, Speyer, and Postnikov [15] and Scott [19]. Conjecturally, the “Plücker clusters,” of LM correspond exactly n to the maximal pairwise weakly separated sets of circular pairs. We conjecture that these maximal pairwise weakly separated sets are related to each other by mutations corresponding to the Grassmann–Plücker relations, and present evidence to this end. The roadmap of the paper is as follows. We briefly review terminology and known results in Section 2, where we also establish some basic properties of electrical networks. In Section 3, we define the poset EP and establish its most important properties in n 1 It is worth noting that the introduction of the totally nonnegative Grassmannian was motivated in part by the study of electrical networks, see [16, p.2]. J. Alman et al. / Journal of Combinatorial Theory, Series A 132 (2015) 58–101 61 Theorems 3.1.3 and 3.2.4. The study of enumerative properties of EP is undertaken in n Section 4, where we prove the three parts of Theorem 4.2.5. In Section 5, we motivate and introduce electrical positroids, the main result being Theorem 5.2.1. Finally, in Section 6, we construct LM using positivity tests and prove Theorem 6.2.16, then n conclude by establishing weak forms of Conjecture 6.3.4, which relates the clusters of LM to positivity tests and our analogue of weak separation. n 2. Electrical networks We begin a systematic discussion of electrical networks by recalling various notions and results from [4]. We will also introduce some new terminology and conventions which will aid our exposition, in some cases deviating from [4]. 2.1. Circular planar electrical networks, up to equivalence Definition 2.1.1. A circular planar electrical network is a circular planar graph (i.e., a planar graph embedded in a disk, where vertices on the boundary of the disk are referred to as boundary vertices) Γ, together with a conductance map γ :E(Γ) →R . >0 To avoid cumbersome language, we will henceforth refer to these objects as electrical networks. We will also call the number of boundary vertices of an electrical network (or a circular planar graph) its order. We also adopt the following convention: cur- rent going in to the disk is measured to be negative. This convention is the opposite of that used in [4], but we will prefer it for the ensuing elegance of the statement of Theorem 2.2.6. Associated to an electrical network (Γ, γ)is itsresponse matrix(see [4, §3]), measuring the network’s response to potentials applied at boundary vertices. Two electrical networks (Γ , γ ), (Γ , γ ) are equivalent if they have the same response matrix. The resulting 1 1 2 2 equivalence relation ∼ may be described combinatorially: Theorem 2.1.2. (See [5, Théorème 4].) Two electrical networks are equivalent if and only if they are related by a sequence of local equivalences (and their inverses): removal of self-loops or spikes, replacement of edges in series or in parallel, or Y-Δtransformations. The relation ∼ is also an equivalence relation on underlying circular planar graphs, and, when there is no likelihood for confusion, we will often mean this underlying graph when referring to an “electrical network.” 2.2. Circular pairs and circular minors Circular pairs and circular minors are central to the characterization of response matrices. 62 J. Alman et al. / Journal of Combinatorial Theory, Series A 132 (2015) 58–101 Definition 2.2.1. Let P = {p , p , ..., p } and Q = {q , q , ..., q } be disjoint ordered 1 2 k 1 2 k subsets of the boundary vertices of an electrical network (Γ, γ). We say that (P; Q) is a circular pair if p , ..., p , q , ..., q are in clockwise order around the circle. We will 1 k k 1 refer to k as the size of the circular pair. (cid:5) (cid:5) (cid:5) Remark 2.2.2. We will take (P; Q) to be the same circular pair as (Q; P), where P denotes the ordered set P with its elements reversed. Definition 2.2.3. Let (P; Q) and (Γ, γ) be as in Definition 2.2.1. We say that there is a connectionfrom P to Qin Γ if there exists a collection of vertex-disjoint paths from p to i q in Γ, and furthermore each path in the collection contains no boundary vertices other i than its endpoints. We denote the set of circular pairs (P; Q) for which P is connected to Q by π(Γ). Definition 2.2.4. Let (P; Q)and (Γ, γ)be as in Definition2.2.1, and let M be the response matrix. We define the circular minor associated to (P; Q) to be the determinant of the k×k matrix M(P; Q) with M(P; Q) =M . i,j pi,qj Remark 2.2.5. When there is no ambiguity, we refer to submatrices and their determi- nants both as minors, interchangeably. We are interested in circular minors and connections because of the following results, which are immediate corollaries of [4, Theorem 4] and [4, Theorem 4.2]: Theorem 2.2.6. Let M be an n ×n matrix. Then: (a) M is the response matrix for an electrical network (Γ, γ)if and only if M is symmet- ric with row and column sums equal zero, and each of the circular minors M(P; Q) is non-negative. (b) If M is the response matrix for an electrical network (Γ, γ), the positive circular minors M(P; Q) are exactly those for which there is a connection from P to Q. 2.3. Critical graphs In this section, we introduce critical graphs, a particular class of circular planar graphs, and give some important properties. Definition 2.3.1. Let G be a circular planar graph. G is said to be critical if, for any removal of an edge via deletion or contraction (note that an edge between two boundary vertices cannot be contracted), there exists a circular pair (P; Q)for which P is connected to Q through G before the edge removal, but not afterward. J. Alman et al. / Journal of Combinatorial Theory, Series A 132 (2015) 58–101 63 Theorem 2.3.2. (See [5, Théorème 2].) Every equivalence class of circular planar graphs has a critical representative. Theorem 2.3.3. (See [4, Theorem 1].) Suppose G , G are critical. Then, G and G are 1 2 1 2 Y-Δ equivalent (that is, related by a sequence of Y-Δ transformations) if and only if π(G ) =π(G ). 1 2 Corollary 2.3.4. Let G , G be arbitrary circular planar graphs. Then, G ∼ G if and 1 2 1 2 only if π(G ) =π(G ). 1 2 Theorem 2.3.5. (See [4, Theorem 4].) Suppose that G is critical and has N edges. Put π = π(G), and let Ω(π) denote the set of response matrices whose positive minors are exactly those corresponding to the elements of π. Then, the map r :RN →Ω(π), taking G >0 the conductances on the edges of Gto the resulting response matrix, is a diffeomorphism. It follows that the space of response matrices for electrical networks of order n is the disjoint union of the cells Ω(π), some of which are empty. The non-empty cells Ω(π) are those which correspond to critical graphs G with π(G) = π. We will describe how these cells are attached to each other in Proposition 3.1.2. Later, we will prefer to index these cells by their underlying (equivalence classes of) circular planar graphs: Ω(G) will denote the space of response matrices for conductances on G. Theorem 2.3.6. Let (Γ, γ) be an electrical network. The following are equivalent: (1) Γ is critical. (2) Given the response matrix M of (Γ, γ), γ can uniquely be recovered from M and Γ. (3) Γ has the minimal number of edges among elements of its equivalence class. (4) The medial graph (see [4, §6]) M(Γ) of Γ is lensless. Proof. Apply [4, Lemma 13.1], [4, Lemma 13.2], and Proposition 2.3.4. (cid:2) 2.4. Medial graphs Medial graphs are constructed in [4, §6] as a dual object to electrical networks, and will be an important tool in our study thereof. Their significance is already evident from Theorem 2.3.6. If Gis a critical graph, the geodesics of M(G)consist of n“wires” connecting pairs of the 2n boundary medial vertices. Thus, any critical graph G gives a perfect matching of the medial boundary vertices. Furthermore, suppose H ∼Gis critical. By Theorem2.3.3 and Proposition 2.3.4, G and H are related by Y-Δ transformations, so M(G) and M(H) are related by motions. In particular, M(G) and M(H) match the same pairs of boundary medial vertices, so we have a well-defined map from critical circular planar graph equivalence classes to matchings. In fact, this map is injective: 64 J. Alman et al. / Journal of Combinatorial Theory, Series A 132 (2015) 58–101 Proposition 2.4.1. Suppose that the geodesics of two lensless medial graphs M(G), M(H) match the same pairs of medial boundary vertices. Then, the medial M(G) and M(H) are related by motions, or equivalently, G and H are Y-Δ equivalent. Proof. Implicit in [4, Theorem 7.2]. (cid:2) Definition 2.4.2. Given the boundary vertices of a circular planar graph embedded in a disk D, take 2n medial boundary vertices as before. A wiring diagram is collection of n smooth curves (wires) embedded in D, each of which connects a pair of medial boundary vertices in such a way that each medial boundary vertex has exactly one incident wire. We require that wiring diagrams have no triple crossings or self-loops. As with electrical networks and medial graphs, theorderof the wiring diagram is defined to be equal ton. It is immediate from Proposition 2.4.1 that, given a set of boundary vertices, perfect matchings on the set of medial boundary vertices are in bijection with motion-equivalence classes of lensless wiring diagrams. Thus, we have an injection G (cid:7)→M(G) from critical graph equivalence classes to motion-equivalence classes of lensless wiring diagram, but this map is not surjective. We describe the image of this injection in the next definition: Definition 2.4.3. Given boundary vertices V , ..., V and a wiring diagram W on the 1 n same boundary circle, adividing linefor W is a line V V with i (cid:8)=j such that there does i j not exist a wire connecting two points on opposite sides of V V . The wiring diagram is i j called full if it has no dividing lines. It is obvious that fullness is preserved under motions. Now, suppose that we have a lensless full wiring diagram W; we now define a critical graph E(W). Let D be the disk in which our wiring diagram is embedded. The wires of W divide D into faces, and it is well-known that these faces can be colored black and white such that neighboring faces have opposite colors. The condition that W be full means that each face contains at most one boundary vertex. Furthermore, all boundary vertices are contained in faces of the same color; without loss of generality, assume that this color is black. Then place an additional vertex inside each black face which does not contain a boundary vertex. The boundary vertices, in addition to these added interior vertices, form the vertex set for E(W). Finally, two vertices of E(W) are connected by an edge if and only if their corresponding faces share a common point on their respective boundaries, which must be an intersection p of two wires of W. This edge is drawn as to pass through p. An example is shown in Fig. 1. It is straightforward to check that M and E are inverse maps. We have thus proven the following result: Theorem 2.4.4. The associations G (cid:7)→M(G) and W (cid:7)→E(W) are inverse bijections be- tween equivalence classes of critical graphs and motion-equivalence classes of full lensless wiring diagrams. J. Alman et al. / Journal of Combinatorial Theory, Series A 132 (2015) 58–101 65 Fig.1.Recovering an electrical network from its (lensless) medial graph. The square vertices are the vertices of the medial graph, and the dashed edges are edges of the medial graph, while the circle vertices are the vertices of the network. The middle vertex was recovered. Fig.2.Breakingacrossing,intwoways. Finally, let us discuss the analogues of contraction and deletion in medial graphs. Each operation corresponds to the breaking of a crossing, as shown in Fig. 2. A crossing may be broken in two ways: breaking outward from the corresponding edge of the underlying electrical network corresponds to contraction, and breaking along the edge corresponds to deletion. In the same way that contraction or deletion of an edge in a critical graph is not guaranteed to yield a critical graph, breaking a crossing in lensless medial graphs does not necessarily yield a lensless medial graph. Not all breakings of crossings are valid, as some crossings may be broken in a particular way to create a dividing line. In fact, it is straightforward to check that creating a dividing line by breaking a crossing corresponds to contracting a boundary edge, which we also do not allow. Thus, we allow all breakings of crossings as long as no dividing lines are created; such breakings are called legal. 3. The electrical poset EP n We now consider EP , the poset of circular planar graphs under contraction and n deletion. We will find that, equivalently, EP is the poset of disjoint cells Ω(G), as n defined in Section 2.3 under containment in closure. 66 J. Alman et al. / Journal of Combinatorial Theory, Series A 132 (2015) 58–101 Fig.3.EP3. 3.1. Construction Before constructing EP , we need a lemma to guarantee that the order relation will n be well-defined. Lemma 3.1.1. Let G be a circular planar graph, and suppose that H can be obtained from G by a sequence of contractions and deletions. Consider a circular planar graph G(cid:2) with G(cid:2) ∼ G. Then, there exists a sequence of contractions and deletions starting from G(cid:2) whose result is some H(cid:2) ∼H. Proof. By induction, we may assume that H can be obtained from Gby one contraction or one deletion. Furthermore, by Theorem 2.1.2, we may assume by induction that G and G(cid:2) are related by a local equivalence. From here, the proof is a matter of checking that, for each of the possible local equivalences G ∼G(cid:2) (see Theorem 2.1.2), a sequence of contractions and deletions may be applied to G(cid:2) to obtain some H(cid:2) ∼ H. This is straightforward. (cid:2) For distinct equivalence classes [G], [H], we may now define [H] < [G] if, given any G ∈[G], there exists a sequence of contractions and deletions that may be applied to G to obtain an element of [H]. We thus have a (well-defined) electrical poset of order n, denoted EP , of equivalence classes of circular planar graphs or order n. If H ∈[H] and n G ∈[G] with [H] <[G], we will write H <G. Fig. 3 shows EP , with elements represented as medial graphs (left) and electrical 3 networks (right). Theorem2.3.2guarantees that the electrical networks may be taken to J. Alman et al. / Journal of Combinatorial Theory, Series A 132 (2015) 58–101 67 be critical. Note that EP is isomorphic to the Boolean Lattice B , because all critical 3 3 graphs of order 3 arise from taking edge-subsets of the top graph. Let us now give an alternate description of the poset EP . Associated to each circular n planar graph G, we have an open cell Ω(G)of response matrices for conductances on G, where Ω(G) is taken to be a subset of the space Ω of symmetric n ×n matrices. It is n clear that, if G ∼G(cid:2), we have, by definition, Ω(G) =Ω(G(cid:2)). Proposition 3.1.2. Let G be a circular planar graph. Then, (cid:10) Ω(G)= Ω(H), (3.1.1) H≤G where Ω(G) denotes the closure of Ω(G) in Ω , and the union is taken over equivalence n classes of circular planar graphs H ≤G in EP . n Because the Ω(G) are pairwise disjoint when we restrict ourselves to equivalence classes of circular planar graphs (a consequence of Theorems 2.2.6 and 2.3.3), we get: Theorem 3.1.3. [H] ≤[G] in EP if and only if Ω(H) ⊂Ω(G). n Proof of Proposition 3.1.2. Without loss of generality, we may take G to be critical. Let N be the number of edges of G. By 2.3.5, the map r : RN → Ω(G) ⊂ Ω , G >0 n sending a collection of conductances of the edges of G the resulting response matrix, is a diffeomorphism. We will describe a procedure for producing a response matrix for any electrical network whose underlying graph H is obtainable from G by a sequence of contractions and deletions (that is, H ≤G). Given γ ∈ RN , write γ = (γ , ..., γ ). Note that for each i ∈ [1, N] and fixed >0 1 N conductances γ1, ..., γ(cid:6)i, ..., γn, the limit limγi→0rG(γ) must exist; indeed, sending the conductance γ to zero is equivalent to deleting its associated edge. This fact is most i easily seen by physical reasoning: an edge of zero conductance has no current flowing through it, and thus the network may as well not have this edge. Thus, limγi→0rG(γ) is just rG(cid:2)(γ1, ..., γ(cid:6)i, ..., γn), where G(cid:2) is the result of deleting efrom G. Similarly, we find that limγi→∞rG(γ) is rG(cid:2)(cid:2)(γ1, ..., γˆi, ..., γn), where G(cid:2)(cid:2) is the result of contracting e. It follows easily, then, that for all H which can be obtained from Gby a contraction or deletion, we have Ω(H) ⊂Ω(G), because, by the previous paragraph, Ω(H) =Im(r ) ⊂ H Ω(G). By induction, we have the same for all H ≤G. It is left to check that any M ∈ Ω(G) is in some cell Ω(H) with H ≤ G. We have that M is a limit of response matrices M , M , ... ∈ Ω(G). The determinants of the 1 2 circular minors of M are limits of determinants of the same minors of the M , and thus i non-negative. It follows that M is the response matrix for some network H, that is, M ∈Ω(H). We claim that H ≤G, which will finish the proof. Consider the sequence {C } defined by C = r−1(M ), which is a sequence of con- k k G k ductances on G. For each edge e ∈ G, we get a sequence {C(e) } of conductances of k