BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Alan D. Sokal contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
I give a combinatorial interpretation of the multiple Laguerre polynomials of the first kind of type II, generalizing the digraph model found by Foata and Strehl for the ordinary Laguerre polynomials. I also give an explicit integral representation for these polynomials, which shows that they form a multidimensional Stieltjes moment sequence whenever $x \le 0$.
We solve analytically the differential equations for a skier on a circular hill and for a particle on a loop-the-loop track when the hill or track is endowed with a coefficient of kinetic friction $μ$. For each problem, we determine the exact "phase diagram" in the two-dimensional parameter plane.
We find Stieltjes-type and Jacobi-type continued fractions for some "master polynomials" that enumerate permutations, set partitions or perfect matchings with a large (sometimes infinite) number of simultaneous statistics. Our results contain many previously obtained identities as special cases, providing a common refinement of all of them.
I show that a hypergeometric function ${}_{p}F_q(a_1,\ldots,a_p;b_1,\ldots,b_q;\,\cdot\,)$ with $p \le q$ belongs to the Laguerre--Pólya class $LP^+$ for arbitrarily large $b_{p+1},\ldots,b_q > 0$ if and only if, after a possible reordering, the differences $a_i - b_i$ are nonnegative integers. This result arises as an easy corollary of the case $p=q$ proven two decades ago by Ki and Kim. I also give explicit examples for the case ${}_{1}F_2$.
I give a short and completely elementary proof of Takagi's 1921 theorem on the zeros of a composite polynomial $f(d/dz) \, g(z)$.
We show that, for Hankel matrices, total nonnegativity (resp. total positivity) of order r is preserved by sum, Hadamard product, and Hadamard power with real exponent t \ge r-2. We give examples to show that our results are sharp relative to matrix size and structure (general, symmetric or Hankel). Some of these examples also resolve the Hadamard critical-exponent problem for totally positive and totally nonnegative matrices.
Two decades ago, Chauve, Dulucq and Guibert showed that the number of rooted trees on the vertex set $[n+1]$ in which exactly $k$ children of the root are lower-numbered than the root is $\binom{n}{k} \, n^{n-k}$. Here I give a simpler proof of this result.
We define an infinite sequence of generalizations, parametrized by an integer $m \ge 1$, of the Stieltjes--Rogers and Thron--Rogers polynomials; they arise as the power-series expansions of some branched continued fractions, and as the generating polynomials for $m$-Dyck and $m$-Schröder paths with height-dependent weights. We prove that all of these sequences of polynomials are coefficientwise Hankel-totally positive, jointly in all the (infinitely many) indeterminates. We then apply this theory to prove the coefficientwise Hankel-total positivity for combinatorially interesting sequences of polynomials. Enumeration of unlabeled ordered trees and forests gives rise to multivariate Fuss--Narayana polynomials and Fuss--Narayana symmetric functions. Enumeration of increasing (labeled) ordered trees and forests gives rise to multivariate Eulerian polynomials and Eulerian symmetric functions, which include the univariate $m$th-order Eulerian polynomials as specializations. We also find branched continued fractions for ratios of contiguous hypergeometric series ${}_r \! F_s$ for arbitrary $r$ and $s$, which generalize Gauss' continued fraction for ratios of contiguous ${}_2 \! F_1$; and for $s=0$ we prove the coefficientwise Hankel-total positivity. Finally, we extend the branched continued fractions to ratios of contiguous basic hypergeometric series ${}_r \! ϕ_s$.
We introduce the generic Lah polynomials $L_{n,k}(ϕ)$, which enumerate unordered forests of increasing ordered trees with a weight $ϕ_i$ for each vertex with $i$ children. We show that, if the weight sequence $ϕ$ is Toeplitz-totally positive, then the triangular array of generic Lah polynomials is totally positive and the sequence of row-generating polynomials $L_n(ϕ,y)$ is coefficientwise Hankel-totally positive. Upon specialization we obtain results for the Lah symmetric functions and multivariate Lah polynomials of positive and negative type. The multivariate Lah polynomials of positive type are also given by a branched continued fraction. Our proofs use mainly the method of production matrices; the production matrix is obtained by a bijection from ordered forests of increasing ordered trees to labeled partial Lukasiewicz paths. We also give a second proof of the continued fraction using the Euler--Gauss recurrence method.
We find a Thron-type continued fraction (T-fraction) for the ordinary generating function of the Ward polynomials, as well as for some generalizations employing a large (indeed infinite) family of independent indeterminates. Our proof is based on a bijection between super-augmented perfect matchings and labeled Schröder paths, which generalizes Flajolet's bijection between perfect matchings and labeled Dyck paths.
I give an elementary proof of Wall's continued-fraction characterization of Hausdorff moment sequences.
We consider two different interpretations of the Chu--Vandermonde identity: as an identity for polynomials, and as an identity for infinite matrices. Each interpretation leads to a class of possible generalizations, and in both cases we obtain a complete characterization of the solutions.
I study the sequences of Euler and Springer numbers from the point of view of the classical moment problem.
We introduce a new graph invariant Λ(G) that we call maxmaxflow, and put it in the context of some other well-known graph invariants, notably maximum degree and its relatives. We prove the equivalence of two "dual" definitions of maxmaxflow: one in terms of flows, the other in terms of cocycle bases. We then show how to bound the total number (or more generally, total weight) of various classes of subgraphs of G in terms of either maximum degree or maxmaxflow. Our results are motivated by a conjecture that the modulus of the roots of the chromatic polynomial of G can be bounded above by a function of Λ(G).
We prove that the (real or complex) chromatic roots of a series-parallel graph with maxmaxflow Lambda lie in the disc |q-1| < (Lambda-1)/log 2. More generally, the same bound holds for the (real or complex) roots of the multivariate Tutte polynomial when the edge weights lie in the "real antiferromagnetic regime" -1 \le v_e \le 0. This result is within a factor 1/log 2 \approx 1.442695 of being sharp
Let R_αbe the Riesz distribution on a simple Euclidean Jordan algebra, parametrized by the complex number α. I give an elementary proof of the necessary and sufficient condition for R_αto be a locally finite complex measure (= complex Radon measure).
We prove, by simple manipulation of commutators, two noncommutative generalizations of the Cauchy-Binet formula for the determinant of a product. As special cases we obtain elementary proofs of the Capelli identity from classical invariant theory and of Turnbull's Capelli-type identities for symmetric and antisymmetric matrices.
The multivariate Tutte polynomial (known to physicists as the Potts-model partition function) can be defined on an arbitrary finite graph G, or more generally on an arbitrary matroid M, and encodes much important combinatorial information about the graph (indeed, in the matroid case it encodes the full structure of the matroid). It contains as a special case the familiar two-variable Tutte polynomial -- and therefore also its one-variable specializations such as the chromatic polynomial, the flow polynomial and the reliability polynomial -- but is considerably more flexible. I begin by giving an introduction to all these problems, stressing the advantages of working with the multivariate version. I then discuss some questions concerning the complex zeros of the multivariate Tutte polynomial, along with their physical interpretations in statistical mechanics (in connection with the Yang--Lee approach to phase transitions) and electrical circuit theory. Along the way I mention numerous open problems. This survey is intended to be understandable to mathematicians with no prior knowledge of physics.
I show that the zeros of the chromatic polynomials P_G(q) for the generalized theta graphs Θ^{(s,p)} are, taken together, dense in the whole complex plane with the possible exception of the disc |q-1| < 1. The same holds for their dichromatic polynomials (alias Tutte polynomials, alias Potts-model partition functions) Z_G(q,v) outside the disc |q+v| < |v|. An immediate corollary is that the chromatic zeros of not-necessarily-planar graphs are dense in the whole complex plane. The main technical tool in the proof of these results is the Beraha-Kahane-Weiss theorem on the limit sets of zeros for certain sequences of analytic functions, for which I give a new and simpler proof.
At zero temperature, the 3-state antiferromagnetic Potts model on a square lattice maps exactly onto a point of the 6-vertex model whose long-distance behavior is equivalent to that of a free scalar boson. We point out that at nonzero temperature there are two distinct types of excitation: vortices, which are relevant with renormalization-group eigenvalue 1/2; and non-vortex unsatisfied bonds, which are strictly marginal and serve only to renormalize the stiffness coefficient of the underlying free boson. Together these excitations lead to an unusual form for the corrections to scaling: for example, the correlation length diverges as β\equiv J/kT \to \infty according to ξ\sim A e^{2β} (1 + bβe^{-β} + ...), where b is a nonuniversal constant that may nevertheless be determined independently. A similar result holds for the staggered susceptibility. These results are shown to be consistent with the anomalous behavior found in the Monte Carlo simulations of Ferreira and Sokal.
I show that there exist universal constants $C(r) < \infty$ such that, for all loopless graphs $G$ of maximum degree $\le r$, the zeros (real or complex) of the chromatic polynomial $P_G(q)$ lie in the disc $|q| < C(r)$. Furthermore, $C(r) \le 7.963906... r$. This result is a corollary of a more general result on the zeros of the Potts-model partition function $Z_G(q, {v_e})$ in the complex antiferromagnetic regime $|1 + v_e| \le 1$. The proof is based on a transformation of the Whitney-Tutte-Fortuin-Kasteleyn representation of $Z_G(q, {v_e})$ to a polymer gas, followed by verification of the Dobrushin-Kotecký-Preiss condition for nonvanishing of a polymer-model partition function. I also show that, for all loopless graphs $G$ of second-largest degree $\le r$, the zeros of $P_G(q)$ lie in the disc $|q| < C(r) + 1$. Along the way, I give a simple proof of a generalized (multivariate) Brown-Colbourn conjecture on the zeros of the reliability polynomial for the special case of series-parallel graphs.
The generalized theta graph Θ_{s_1,...,s_k} consists of a pair of endvertices joined by k internally disjoint paths of lengths s_1,...,s_k \ge 1. We prove that the roots of the chromatic polynomial $pi(Θ_{s_1,...,s_k},z) of a k-ary generalized theta graph all lie in the disc |z-1| \le [1 + o(1)] k/\log k, uniformly in the path lengths s_i. Moreover, we prove that Θ_{2,...,2} \simeq K_{2,k} indeed has a chromatic root of modulus [1 + o(1)] k/\log k. Finally, for k \le 8 we prove that the generalized theta graph with a chromatic root that maximizes |z-1| is the one with all path lengths equal to 2; we conjecture that this holds for all k.
We study the antiferromagnetic q-state Potts model on the square lattice for q=3 and q=4, using the Wang-Swendsen-Kotecky (WSK) Monte Carlo algorithm and a powerful finite-size-scaling extrapolation method. For q=3 we obtain good control up to correlation length $ξ\sim 5000$; the data are consistent with $ξ(β) = A e^{2β} β^p (1 + a_1 e^{-β} + ...)$ as $β\to\infty$, with $p \approx 1$. The staggered susceptibility behaves as $χ_{stagg} \sim ξ^{5/3}$. For q=4 the model is disordered ($ξ\ltapprox 2$) even at zero temperature. In appendices we prove a correlation inequality for Potts antiferromagnets on a bipartite lattice, and we prove ergodicity of the WSK algorithm at zero temperature for Potts antiferromagnets on a bipartite lattice.