Search

Randomly sampling an acyclic orientation on the complete bipartite graph $K_{n,k}$ with parts of size $n$ and $k$, we investigate the length of the longest path. We provide a probability generating function for the distribution of the longest path length, and we use Analytic Combinatorics to perform asymptotic analysis of the probability distribution in the case of equal part sizes $n = k$ tending toward infinity. We show that the distribution is asymptotically Gaussian, and we obtain precise asymptotics for the mean and variance. These results address a question asked by Peter J. Cameron. Keywords: bipartite graph, directed graph, random graph, acyclic orientation, poly-Bernoulli numbers, lonesum matrices, generating function, analytic combinatorics, asymptotics., Comment: 24 pages

Addressing a problem posed by W. Li and A. Wei (2009), we investigate the average number of (complex) zeros of a random harmonic polynomial $p(z) + \overline{q(z)}$ sampled from the Kac ensemble, i.e., where the coefficients are independent identically distributed centered complex Gaussian random variables. We establish a precise asymptotic, showing that when $\text{deg} p = \text{deg} q = n$ tends to infinity the average number of zeros is asymptotic to $\frac{1}{2} n \log n$. We further consider the average number of zeros restricted to various regions in the complex plane leading to interesting comparisons with the classically studied case of analytic Kac polynomials. We also consider deterministic extremal problems for harmonic polynomials with coefficient constraints; using an indirect probabilistic method we show the existence of harmonic polynomials with unimodular coefficients having at least $\frac{2}{\pi} n \log n + O(n)$ zeros. We conclude with a list of open problems., Comment: 27 pages, 1 figure

We consider gravitational lensing of a background source by a finite system of point-masses. The problem of determining the maximum possible number of lensed images has been completely resolved in the single-plane setting (where the point masses all reside in a single lens plane), but this problem remains open in the multiplane setting. We construct examples of $K$-plane point-mass gravitational lens ensembles that produce $\prod_{i=1}^K (5g_i-5)$ images of a single background source, where $g_i$ is the number of point masses in the $i^\text{th}$ plane. This gives asymptotically (for large $g_i$ with $K$ fixed) $5^K$ times the minimal number of lensed images. Our construction uses Rhie's single-plane examples and a structured parameter-rescaling algorithm to produce preliminary systems of equations with the desired number of solutions. Utilizing the stability principle from differential topology, we then show that the preliminary (nonphysical) examples can be perturbed to produce physically meaningful examples while preserving the number of solutions. We provide numerical simulations illustrating the result of our construction, including the positions of lensed images as well as the structure of the critical curves and caustics. We observe an interesting ``caustic of multiplicity'' phenomenon that occurs in the nonphysical case and has a noticeable effect on the caustic structure in the physically meaningful perturbative case., Comment: 20 pages, 8 figures. The paper will appear in the Journal of Mathematical Physics

Investigating a problem posed by W. Hengartner (2000), we study the maximal valence (number of preimages of a prescribed point in the complex plane) of logharmonic polynomials, i.e., complex functions that take the form $f(z) = p(z) \overline{q(z)}$ of a product of an analytic polynomial $p(z)$ of degree $n$ and the complex conjugate of another analytic polynomial $q(z)$ of degree $m$. In the case $m=1$, we adapt an indirect technique utilizing anti-holomorphic dynamics to show that the valence is at most $3n-1$. This confirms a conjecture of Bshouty and Hengartner (2000). Using a purely algebraic method based on Sylvester resultants, we also prove a general upper bound for the valence showing that for each $n,m \geq 1$ the valence is at most $n^2+m^2$. This improves, for every choice of $n,m \geq 1$, the previously established upper bound $(n+m)^2$ based on Bezout's theorem. We also consider the more general setting of polyanalytic polynomials where we show that this latter result can be extended under a nondegeneracy assumption., Comment: 17 pages, 1 figure

A classically studied geometric property associated to a complex polynomial $p$ is the inradius (the radius of the largest inscribed disk) of its (filled) lemniscate $\Lambda := \{z \in \mathbb{C}:|p(z)| < 1\}$. In this paper, we study the lemniscate inradius when the defining polynomial $p$ is random, namely, with the zeros of $p$ sampled independently from a compactly supported probability measure $\mu$. If the negative set of the logarithmic potential $U_{\mu}$ generated by $\mu$ is non-empty, then the inradius is bounded from below by a positive constant with overwhelming probability. Moreover, the inradius has a determinstic limit if the negative set of $U_{\mu}$ additionally contains the support of $\mu$. On the other hand, when the zeros are sampled independently and uniformly from the unit circle, then the inradius converges in distribution to a random variable taking values in $(0,1/2)$. We also consider the characteristic polynomial of a Ginibre random matrix whose lemniscate we show is close to the unit disk with overwhelming probability., Comment: 21 pages, 4 figures

We prove the existence of complex polynomials $p(z)$ of degree $n$ and $q(z)$ of degree $m

We consider the average number of limit cycles that bifurcate from a randomly perturbed linear center where the perturbation consists of random (bivariate) polynomials with independent coefficients. This problem reduces, by way of classical perturbation theory of the Poincar\'e first return map, to a problem on the real zeros of a random \emph{univariate} polynomial $\displaystyle f_n(x) = \sum_{m=0}^n c_m \xi_m x^m$ with independent coefficients $\xi_m$ having mean zero, variance 1 and $c_m \sim m^{-1/2}$. This polynomial belongs to the class of {\it generalized Kac polynomials} at the critical regime. We provide asymptotics for the average number of real zeros and answer the question on bifurcating limit cycles. Additionally, we provide the correct order of the mean number of real roots in the subcritical regime., Comment: 34 pages, 3 figures

We consider the critical points (equilibria) of a planar potential generated by $n$ Newtonian point masses augmented with a quadratic term (such as arises from a centrifugal effect). Particular cases of this problem have been considered previously in studies of the circular restricted $n$-body problem. We show that the number of equilibria is finite for a generic set of parameters, and we establish estimates for the number of equilibria. We prove that the number of equilibria is bounded below by $n+1$, and we provide examples to show that this lower bound is sharp. We prove an upper bound on the number of equilibria that grows exponentially in $n$. In order to establish a lower bound on the maximum number of equilibria, we analyze a class of examples, referred to as ``ring configurations'', consisting of $n-1$ equal masses positioned at vertices of a regular polygon with an additional mass located at the center. Previous numerical observations indicate that these configurations can produce as many as $5n-5$ equilibria. We verify analytically that the ring configuration has at least $5n-5$ equilibria when the central mass is sufficiently small. We conjecture that the maximum number of equilibria grows linearly with the number of point masses. We also discuss some mathematical similarities to other equilibrium problems in mathematical physics, namely, Maxwell's problem from electrostatics and the image counting problem from gravitational lensing., Comment: 16 pages, 1 figure

We study the number and distribution of the limit cycles of a planar vector field whose component functions are random polynomials. We prove a lower bound on the average number of limit cycles when the random polynomials are sampled from the Kostlan-Shub-Smale ensemble. Investigating a problem introduced by Brudnyi [Annals of Mathematics (2001)] we also consider a special local setting of counting limit cycles near a randomly perturbed center focus, and when the perturbation has i.i.d. coefficients, we prove a limit law showing that the number of limit cycles situated within a disk of radius less than unity converges almost surely to the number of real zeros of a logarithmically-correlated random univariate power series. We also consider infinitesimal perturbations where we obtain precise asymptotics on the global average count of limit cycles for a family of models. The proofs of these results use novel combinations of techniques from dynamical systems and random analytic functions., Comment: 41 pages. In addition to the updates in version 2, this version includes several minor revisions and a sketch of an alternate proof of Theorem 3 using results of A. Lerario and M. Stecconi. The open problem concerning infinitesimal perturbations has been resolved (see the comment in the introduction "added in press"). The paper will appear in Transactions of the American Mathematical Society

We prove the existence of a roof function for arclength null quadrature domains having finitely many boundary components. This bridges a gap toward classification of arclength null quadrature domains by removing an a priori assumption from previous classification results., Comment: 11 pages, 1 figure. In this version, the proof of Theorem 2.2 has been revised along with some additional revisions. The paper will appear in The Bulletin of the London Mathematical Society

We provide bivariate asymptotics for the poly-Bernoulli numbers, a combinatorial array that enumerates lonesum matrices, using the methods of Analytic Combinatorics in Several Variables (ACSV). For the diagonal asymptotic (i.e., for the special case of square lonesum matrices) we present an alternative proof based on Parseval's identity. In addition, we provide an application in Algebraic Statistics on the asymptotic ML-degree of the bivariate multinomial missing data problem, and we strengthen an existing result on asymptotic enumeration of permutations having a specified excedance set., Comment: 16 pages, 3 figures. This version includes a more detailed discussion of applications with two new sections related to an application in Algebraic Statistics. The paper will appear in the journal Advances in Applied Mathematics

We study the topology of a random cubical complex associated to Bernoulli site percolation on a cubical grid. We begin by establishing a limit law for homotopy types. More precisely, looking within an expanding window, we define a sequence of normalized counting measures (counting connected components according to homotopy type), and we show that this sequence of random probability measures converges in probability to a deterministic probability measure. We then investigate the dependence of the limiting homotopy measure on the coloring probability $p$, and our results show a qualitative change in the homotopy measure as $p$ crosses the percolation threshold $p=p_c$. Specializing to the case of $d=2$ dimensions, we also present empirical results that raise further questions on the $p$-dependence of the limiting homotopy measure., Comment: 23 pages, 5 figures, 2 tables. This version includes several minor revisions as well as an additional Section 3.3 on continuity (with respect to the coloring probability p) of each coefficient in the limiting homotopy measure. The paper will appear in the Journal of Applied and Computational Topology

Let $\Omega\subset\mathbb{C}$ be a bounded domain. In this note, we use complex variable methods to study the number of critical points of the function $v=v_\Omega$ that solves the elliptic problem $\Delta v = -2$ in $\Omega,$ with boundary values $v=0$ on $\partial\Omega.$ This problem has a classical flavor but is especially motivated by recent studies on localization of eigenfunctions. We provide an upper bound on the number of critical points of $v$ when $\Omega$ belongs to a special class of domains in the plane, namely, domains for which the boundary $\partial\Omega$ is contained in $\{z:|z|^2 = f(z) + \overline{f(z)}\},$ where $f'(z)$ is a rational function. We furnish examples of domains where this bound is attained. We also prove a bound on the number of critical points in the case when $\Omega$ is a quadrature domain, and conclude the note by stating some open problems and conjectures., Comment: 13 pages, 3 figures

We investigate the topologies of random geometric complexes built over random points sampled on Riemannian manifolds in the so-called "thermodynamic" regime. We prove the existence of universal limit laws for the topologies; namely, the random normalized counting measure of connected components (counted according to homotopy type) is shown to converge in probability to a deterministic probability measure. Moreover, we show that the support of the deterministic limiting measure equals the set of all homotopy types for Euclidean geometric complexes of the same dimension as the manifold., Comment: 24 pages, 1 figure. This version contains minor corrections and more details in the proofs. The Appendix has been moved to a new section on preliminary material. The paper will appear in the journal International Mathematics Research Notices

Random graph models are important constructs for data analytic applications as well as pure mathematical developments, as they provide capabilities for network synthesis and principled analysis. Several models have been developed with the aim of faithfully preserving important graph metrics and substructures. With the goal of capturing degree distribution, clustering coefficient, and communities in a single random graph model, we propose a new model to address shortcomings in a progression of network modeling capabilities. The Block Two-Level Erd{\H{o}}s-R{\'e}nyi (BTER) model of Seshadhri et al., designed to allow prescription of expected degree and clustering coefficient distributions, neglects community modeling, while the Generalized BTER (GBTER) model of Bridges et al., designed to add community modeling capabilities to BTER, struggles to faithfully represent all three characteristics simultaneously. In this work, we fit BTER and two GBTER configurations to several real-world networks and compare the results with that of our new model, the Extended GBTER (EGBTER) model. Our results support that EBGTER adds a community-modeling flexibility to BTER, while retaining a satisfactory level of accuracy in terms of degree and clustering coefficient. Our insights and empirical testing of previous models as well as the new model are novel contributions to the literature., Comment: graph model extending BTER and GBTER, ASONAM conference paper, 2 tables, multiple images

To each generic complex polynomial $p(z)$ there is associated a labeled binary tree (here referred to as a "lemniscate tree") that encodes the topological type of the graph of $|p(z)|$. The branching structure of the lemniscate tree is determined by the configuration (i.e., arrangement in the plane) of the singular components of those level sets $|p(z)|=t$ passing through a critical point. In this paper, we address the question "How many branches appear in a typical lemniscate tree?" We answer this question first for a lemniscate tree sampled uniformly from the combinatorial class and second for the lemniscate tree arising from a random polynomial generated by i.i.d. zeros. From a more general perspective, these results take a first step toward a probabilistic treatment (within a specialized setting) of Arnold's program of enumerating algebraic Morse functions., Comment: 18 pages, 6 figures

A polynomial lemniscate is a curve in the complex plane defined by $\{z \in \mathbb{C}:|p(z)|=t\}$. Erd\"os, Herzog, and Piranian posed the extremal problem of determining the maximum length of a lemniscate $\Lambda=\{ z \in \mathbb{C}:|p(z)|=1\}$ when $p$ is a monic polynomial of degree $n$. In this paper, we study the length and topology of a random lemniscate whose defining polynomial has independent Gaussian coefficients. In the special case of the Kac ensemble we show that the length approaches a nonzero constant as $n \rightarrow \infty$. We also show that the average number of connected components is asymptotically $n$, and we observe a positive probability (independent of $n$) of a giant component occurring., Comment: 19 pages, 7 figures. This version includes results on the connected components of the lemniscate

We derive a formula expressing the average number $E_n$ of real lines on a random hypersurface of degree $2n-3$ in $\mathbb{R}\textrm{P}^n$ in terms of the expected modulus of the determinant of a special random matrix. In the case $n=3$ we prove that the average number of real lines on a random cubic surface in $\mathbb{R}\textrm{P}^3$ equals: $$E_3=6\sqrt{2}-3.$$ Our technique can also be used to express the number $C_n$ of complex lines on a generic hypersurface of degree $2n-3$ in $\mathbb{C}\textrm{P}^n$ in terms of the determinant of a random Hermitian matrix. As a special case we obtain a new proof of the classical statement $C_3=27.$ We determine, at the logarithmic scale, the asymptotic of the quantity $E_n$, by relating it to $C_n$ (whose asymptotic has been recently computed D. Zagier). Specifically we prove that: $$\lim_{n\to \infty}\frac{\log E_n}{\log C_n}=\frac{1}{2}.$$ Finally we show that this approach can be used to compute the number $R_n=(2n-3)!!$ of real lines, counted with their intrinsic signs, on a generic real hypersurface of degree $2n-3$ in $\mathbb{R}\textrm{P}^n$., Comment: 24 pages. This version replaces an earlier version by the same authors entitled "The average number of real lines on a random cubic". The title and abstract have changed to reflect substantial additions to the paper

What is the shape of a uniformly massive object that generates a gravitational potential equivalent to that of two equal point-masses? If the weight of each point-mass is sufficiently small compared to the distance between the points then the answer is a pair of balls of equal radius, one centered at each of the two points, but otherwise it is a certain domain of revolution about the axis passing through the two points. The existence and uniqueness of such a domain is known, but an explicit parameterization is known only in the plane where the region is referred to as a Neumann oval. We construct a four-dimensional "Neumann ovaloid", solving explicitly this inverse potential problem., Comment: 14 pages, 1 figure

Given a planar domain $\Omega$, the Bergman analytic content measures the $L^{2}(\Omega)$-distance between $\bar{z}$ and the Bergman space $A^{2}(\Omega)$. We compute the Bergman analytic content of simply-connected quadrature domains with quadrature formula supported at one point, and we also determine the function $f \in A^2(\Omega)$ that best approximates $\bar{z}$. We show that, for simply-connected domains, the square of Bergman analytic content is equivalent to torsional rigidity from classical elasticity theory, while for multiply-connected domains these two domain constants are not equivalent in general., Comment: 10 pages, 3 figures

We consider the Dirichlet problem in an ellipsoidal cylinder when the data function is entire. Under an additional assumption that the order of the data function is less than one, we show that there is a solution that extends as an entire harmonic function., Comment: 7 pages

It is shown that the Dirichlet problem for the slab $(a,b) \times \mathbb{R}^{d}$ with entire boundary data has an entire solution. The proof is based on a generalized Schwarz reflection principle. Moreover, it is shown that for a given entire harmonic function $g$ the inhomogeneous difference equation $h\left( t+1,y\right) -h\left(t,y\right) =g\left(t,y\right)$ has an entire harmonic solution $h$., Comment: 8 pages

We investigate the geometry of a random rational lemniscate $\Gamma$, the level set $\{|r(z)|=1\}$ on the Riemann sphere of the modulus of a random rational function $r$. We assign a probability distribution to the space of rational functions $r=p/q$ of degree $n$ by sampling $p$ and $q$ independently from the complex Kostlan ensemble of random polynomials of degree $n$. We prove that the average \emph{spherical length} of $\Gamma$ is $\frac{\pi^2}{2} \sqrt{n},$ which is proportional to the square root of the maximal spherical length. We also provide an asymptotic for the average number of points on the curve that are tangent to one of the meridians on the Riemann sphere (i.e. tangent to one of the radial directions in the plane). Concerning the topology of $\Gamma$, on a local scale, we prove that for every disk $D$ of radius $O(n^{-1/2})$ in the Riemann sphere and any \emph{arrangement} (i.e. embedding) of finitely many circles $A\subset D$ there is a positive probability (independent of $n$) that $(D,\Gamma\cap D)$ is isotopic to $( D,A)$. (A local random version of Hilbert's Sixteenth Problem restricted to lemniscates.) Corollary: the average number of connected components of $\Gamma$ increases linearly (the maximum rate possible according to a deterministic upper bound)., Comment: 27 pages, 3 figures

A probabilistic approach to the study of the number of zeros of complex harmonic polynomials was initiated by W. Li and A. Wei (2009), who derived a Kac-Rice type formula for the expected number of zeros of random harmonic polynomials with independent Gaussian coefficients. They also provided asymptotics for a complex version of the Kostlan ensemble. Here we determine asymptotics for the alternative truncated model that was recently proposed by J. Hauenstein, D. Mehta, and the authors. Our results confirm (and sharpen) their (3/2)-powerlaw conjecture that had been formulated on the basis of computer experiments., Comment: 15 pages, 1 figure. Minor changes in this version include a more detailed proof of Theorem 3

Motivated by Wilmshurst's conjecture, we investigate the zeros of harmonic polynomials. We utilize a certified counting approach which is a combination of two methods from numerical algebraic geometry: numerical polynomial homotopy continuation to compute a numerical approximation of each zero and Smale's alpha-theory to certify the results. Using this approach, we provide new examples of harmonic polynomials having the most extreme number of zeros known so far; we also study the mean and variance of the number of zeros of random harmonic polynomials.

Exceptional domains are domains on which there exists a positive harmonic function, zero on the boundary and such that the normal derivative on the boundary is constant. Recent results classify exceptional domains as belonging to either a certain one-parameter family of simply periodic domains or one of its scaling limits. We introduce quasi-exceptional domains by allowing the boundary values to be different constants on each boundary component. This relaxed definition retains the interesting property of being an \emph{arclength quadrature domain}, and also preserves the connection to the hollow vortex problem in fluid dynamics. We give a partial classification of such domains in terms of certain Abelian differentials. We also provide a new two-parameter family of periodic quasi-exceptional domains. These examples generalize the hollow vortex array found by Baker, Saffman, and Sheffield (1976). A degeneration of regions of this family provide doubly-connected examples., Comment: 19 pages, 3 figures

We study the expectation of the number of components $b_0(X)$ of a random algebraic hypersurface $X$ defined by the zero set in projective space $\mathbb{R}P^n$ of a random homogeneous polynomial $f$ of degree $d$. Specifically, we consider "invariant ensembles", that is Gaussian ensembles of polynomials that are invariant under an orthogonal change of variables. The classification due to E. Kostlan shows that specifying an invariant ensemble is equivalent to assigning a weight to each eigenspace of the spherical Laplacian. Fixing $n$, we consider a family of invariant ensembles (choice of eigenspace weights) depending on the degree $d$. Under a rescaling assumption on the eigenspace weights (as $d \rightarrow \infty$), we prove that the order of growth of $\mathbb{E} b_0(X)$ satisfies: $$\mathbb{E} b_{0}(X)=\Theta\left(\left[ \mathbb{E} b_0(X\cap \mathbb{R}P^1) \right]^{n} \right). $$ This relates the average number of components of $X$ to the classical problem of M. Kac (1943) on the number of zeros of the random univariate polynomial $f|_{\mathbb{R}P^1}.$ The proof requires an upper bound for $\mathbb{E} b_0(X)$, which we obtain by counting extrema using Random Matrix Theory methods from recent work of the first author, and it also requires a lower bound, which we obtain by a modification of the barrier method. We also provide a quantitative upper bound for the implied constant in the above asymptotic; for the real Fubini-Study model these estimates reveal super-exponential decay of the leading coefficient (in $d$) of $\mathbb{E} b_0(X)$ (as $n \rightarrow \infty$)., Comment: 24 pages, 1 figure. Now published in the Journal of Geometry and Physics

Answering a question of Clark and Ehrenborg (2010), we determine asymptotics for the number of permutations of size n that admit the most common excedance set. In fact, we provide a more general bivariate asymptotic using the multivariate asymptotic methods of R. Pemantle and M. C. Wilson. We also consider two applications of our main result. First, we determine asymptotics on the number of permutations of size n which simultaneously avoid the generalized patterns 21-34 and 34-21. Second, we determine asymptotics on the number of n-cycles that admit no stretching pairs., Comment: 13 pages, 1 figure. Now published in the European Journal of Combinatorics

We consider minimal graphs u(x,y)>0 over unbounded domains D (with u vanishing on the boundary of D). Assuming D contains a sector properly containing a halfplane, we obtain estimates on growth and provide examples illustrating a range of growth., Comment: 11 pages, one figure