Edward A. Bender
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Edward A. Bender has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- E. Rodney Canfield
Department of Computer Science University of Georgia 30602 Athens GA USA
8 shared publications - L. Bruce Richmond
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada N2L 3G1
5 shared publications - Zhicheng Gao
School of Mathematics and Statistics Carleton University K1S5B6 Ottawa Ontario Canada
5 shared publications - Herbert S. Wilf
University of Pennsylvania
2 shared publications - Adri B. Olde Daalhuis
University of Edinburgh
1 shared publication - Atefeh Mashatan
University of Waterloo
1 shared publication
Latest Publications
- 9 July 2014
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 23 (5) , 686-716
Part Sizes of Smooth Supercritical Compositional Structures
We define the notion of smooth supercritical compositional structures. Two well-known examples are compositions and graphs of given genus. The ‘parts’ of a graph are the subgraphs that are maximal trees. We show that large part sizes have asymptotically geometric distributions. This leads to asymptotically independent Poisson variables for numbers of various large parts. In many cases this leads to asymptotic formulas for the probability of being gap-free and for the expected values of the largest part sizes, number of distinct parts and number of parts of multiplicityk.
- 9 July 2014
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 23 (5) , 686-716
Part Sizes of Smooth Supercritical Compositional Structures
We define the notion of smooth supercritical compositional structures. Two well-known examples are compositions and graphs of given genus. The ‘parts’ of a graph are the subgraphs that are maximal trees. We show that large part sizes have asymptotically geometric distributions. This leads to asymptotically independent Poisson variables for numbers of various large parts. In many cases this leads to asymptotic formulas for the probability of being gap-free and for the expected values of the largest part sizes, number of distinct parts and number of parts of multiplicityk.
- Open Access
- 18 October 2012
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 19 (4) , P14
Locally Restricted Compositions IV. Nearly Free Large Parts and Gap-Freeness
We define the notion of asymptotically free for locally restricted compositions, which means roughly that large parts can often be replaced by any larger parts. Two well-known examples are Carlitz and alternating compositions. We show that large parts have asymptotically geometric distributions. This leads to asymptotically independent Poisson variables for numbers of various large parts. Based on this we obtain asymptotic formulas for the probability of being gap free and for the expected values of the largest part, number of distinct parts and number of parts of multiplicity $k$, all accurate to $o(1)$.- 18 October 2012
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 19 (4) , P14
Open AccessLocally Restricted Compositions IV. Nearly Free Large Parts and Gap-Freeness
We define the notion of asymptotically free for locally restricted compositions, which means roughly that large parts can often be replaced by any larger parts. Two well-known examples are Carlitz and alternating compositions. We show that large parts have asymptotically geometric distributions. This leads to asymptotically independent Poisson variables for numbers of various large parts. Based on this we obtain asymptotic formulas for the probability of being gap free and for the expected values of the largest part, number of distinct parts and number of parts of multiplicity $k$, all accurate to $o(1)$. - Open Access
Locally Restricted Compositions IV. Nearly Free Large Parts and Gap-Freeness
We define the notion of asymptotically free for locally restricted compositions, which means roughly that large parts can often be replaced by any larger parts. Two well-known examples are Carlitz and alternating compositions. We show that large parts have asymptotically geometric distributions. This leads to asymptotically independent Poisson variables for numbers of various large parts. Based on this we obtain asymptotic formulas for the probability of being gap free and for the expected values of the largest part, number of distinct parts and number of parts of multiplicity k, all accurate to o(1).
Open AccessLocally Restricted Compositions IV. Nearly Free Large Parts and Gap-Freeness
We define the notion of asymptotically free for locally restricted compositions, which means roughly that large parts can often be replaced by any larger parts. Two well-known examples are Carlitz and alternating compositions. We show that large parts have asymptotically geometric distributions. This leads to asymptotically independent Poisson variables for numbers of various large parts. Based on this we obtain asymptotic formulas for the probability of being gap free and for the expected values of the largest part, number of distinct parts and number of parts of multiplicity k, all accurate to o(1).
- Open Access
- 5 January 2011
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 18 (1) , P13
Asymptotic Enumeration of Labelled Graphs by Genus
We obtain asymptotic formulas for the number of rooted 2-connected and 3-connected surface maps on an orientable surface of genus $g$ with respect to vertices and edges simultaneously. We also derive the bivariate version of the large face-width result for random 3-connected maps. These results are then used to derive asymptotic formulas for the number of labelled $k$-connected graphs of orientable genus $g$ for $k\le3$.- 5 January 2011
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 18 (1) , P13
Open AccessAsymptotic Enumeration of Labelled Graphs by Genus
We obtain asymptotic formulas for the number of rooted 2-connected and 3-connected surface maps on an orientable surface of genus $g$ with respect to vertices and edges simultaneously. We also derive the bivariate version of the large face-width result for random 3-connected maps. These results are then used to derive asymptotic formulas for the number of labelled $k$-connected graphs of orientable genus $g$ for $k\le3$. - Open Access
- 5 January 2010
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 17 (1) , R145
Locally Restricted Compositions III. Adjacent-Part Periodic Inequalities
We study compositions $c_1,\dots,c_k$ of the integer $n$ in which adjacent parts may be constrained to satisfy some periodic inequalities, for example $$ c_{2i}>c_{2i+1} < c_{2i+2} \mbox{(alternating compositions).} $$ The types of inequalities considered are $ < $, $\le$, $>$, $\ge$ and $\ne$. We show how to obtain generating functions from which various pieces of asymptotic information can be computed. There are asymptotically $Ar^{-n}$ compositions of $n$. In a random uniformly selected composition of $n$, the largest part and number of distinct parts are almost surely asymptotic to $\log_{1/r}(n)$. The length of the longest run is almost surely asymptotic to $C\log_{1/r}(n)$ where C is an easily determined rational number. Many other counts are asymptotically normally distributed. We present some numerical results for the various types of alternating compositions.- 5 January 2010
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 17 (1) , R145
Open AccessLocally Restricted Compositions III. Adjacent-Part Periodic Inequalities
We study compositions $c_1,\dots,c_k$ of the integer $n$ in which adjacent parts may be constrained to satisfy some periodic inequalities, for example $$ c_{2i}>c_{2i+1} < c_{2i+2} \mbox{(alternating compositions).} $$ The types of inequalities considered are $ < $, $\le$, $>$, $\ge$ and $\ne$. We show how to obtain generating functions from which various pieces of asymptotic information can be computed. There are asymptotically $Ar^{-n}$ compositions of $n$. In a random uniformly selected composition of $n$, the largest part and number of distinct parts are almost surely asymptotic to $\log_{1/r}(n)$. The length of the longest run is almost surely asymptotic to $C\log_{1/r}(n)$ where C is an easily determined rational number. Many other counts are asymptotically normally distributed. We present some numerical results for the various types of alternating compositions. - Open Access
- 5 January 2010
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 17 (1) , R1
Asymptotics of Some Convolutional Recurrences
We study the asymptotic behavior of the terms in sequences satisfying recurrences of the form $a_n = a_{n-1} + \sum_{k=d}^{n-d} f(n,k) a_k a_{n-k}$ where, very roughly speaking, $f(n,k)$ behaves like a product of reciprocals of binomial coefficients. Some examples of such sequences from map enumerations, Airy constants, and Painlevé I equations are discussed in detail.- 5 January 2010
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 17 (1) , R1
Open AccessAsymptotics of Some Convolutional Recurrences
We study the asymptotic behavior of the terms in sequences satisfying recurrences of the form $a_n = a_{n-1} + \sum_{k=d}^{n-d} f(n,k) a_k a_{n-k}$ where, very roughly speaking, $f(n,k)$ behaves like a product of reciprocals of binomial coefficients. Some examples of such sequences from map enumerations, Airy constants, and Painlevé I equations are discussed in detail. - Open Access
- 7 January 2009
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 16 (1) , R108
Locally Restricted Compositions II. General Restrictions and Infinite Matrices
We study compositions $\vec{\bf c}=(c_1,\dots,c_k)$ of the integer $n$ in which the value $c_i$ of the $i$th part is constrained based on previous parts within a fixed distance of $c_i$. The constraints may depend on $i$ modulo some fixed integer $m$. Periodic constraints arise naturally when $m$-rowed compositions are written in a single row. We show that the number of compositions of $n$ is asymptotic to $Ar^{-n}$ for some $A$ and $r$ and that many counts can be expected to have a joint normal distribution with means vector and covariance matrix asymptotically proportional to $n$. Our method of proof relies on infinite matrices and does not readily lead to methods for accurate estimation of the various parameters. We obtain information about the longest run. In many cases, we obtain almost sure asymptotic estimates for the maximum part and number of distinct parts.- 7 January 2009
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 16 (1) , R108
Open AccessLocally Restricted Compositions II. General Restrictions and Infinite Matrices
We study compositions $\vec{\bf c}=(c_1,\dots,c_k)$ of the integer $n$ in which the value $c_i$ of the $i$th part is constrained based on previous parts within a fixed distance of $c_i$. The constraints may depend on $i$ modulo some fixed integer $m$. Periodic constraints arise naturally when $m$-rowed compositions are written in a single row. We show that the number of compositions of $n$ is asymptotic to $Ar^{-n}$ for some $A$ and $r$ and that many counts can be expected to have a joint normal distribution with means vector and covariance matrix asymptotically proportional to $n$. Our method of proof relies on infinite matrices and does not readily lead to methods for accurate estimation of the various parameters. We obtain information about the longest run. In many cases, we obtain almost sure asymptotic estimates for the maximum part and number of distinct parts. - Open Access
- 1 January 2008
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 15 (1) , R21
Coefficients of Functional Compositions Often Grow Smoothly
The coefficients of a power series $A(x)$ are smooth if $a_{n-1}/a_n$ approaches a limit. If $A(x)=F(G(x))$ and $f_n^{1/n}$ approaches a limit, then the coefficients of $A(x)$ are often smooth. We use this to show that the coefficients of the exponential generating function for graphs embeddable on a given surface are smooth, settling a problem of McDiarmid.- 1 January 2008
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 15 (1) , R21
Open AccessCoefficients of Functional Compositions Often Grow Smoothly
The coefficients of a power series $A(x)$ are smooth if $a_{n-1}/a_n$ approaches a limit. If $A(x)=F(G(x))$ and $f_n^{1/n}$ approaches a limit, then the coefficients of $A(x)$ are often smooth. We use this to show that the coefficients of the exponential generating function for graphs embeddable on a given surface are smooth, settling a problem of McDiarmid. - Open Access
- 7 January 2005
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 12 (1) , R57
Locally Restricted Compositions I. Restricted Adjacent Differences
We study compositions of the integer $n$ in which the first part, successive differences, and the last part are constrained to lie in prescribed sets ${\cal L,D,R}$, respectively. A simple condition on ${\cal D}$ guarantees that the generating function $f(x,{\cal L,D,R})$ has only a simple pole on its circle of convergence and this at $r({\cal D})$, a function independent of ${\cal L}$ and ${\cal R}$. Thus the number of compositions is asymptotic to $Ar({\cal D})^{-n}$ for a suitable constant $A=A({\cal L,D,R})$. We prove a multivariate central and local limit theorem and apply it to various statistics of random locally restricted compositions of $n$, such as number of parts, numbers of parts of given sizes, and number of rises. The first and last parts are shown to have limiting distributions and to be asymptotically independent. If ${\cal D}$ has only finitely many positive elements ${\cal D}^+$, or finitely many negative elements ${\cal D}^-$, then the largest part and number of distinct part sizes are almost surely $\Theta((\log n)^{1/2})$. On the other hand, when both ${\cal D}^+$ and ${\cal D}^-$ have a positive asymptotic lower "local log-density", we prove that the largest part and number of distinct part sizes are almost surely $\Theta(\log n)$, and we give sufficient conditions for the largest part to be almost surely asymptotic to $\log_{1/r({\cal D})}n$.- 7 January 2005
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 12 (1) , R57
Open AccessLocally Restricted Compositions I. Restricted Adjacent Differences
We study compositions of the integer $n$ in which the first part, successive differences, and the last part are constrained to lie in prescribed sets ${\cal L,D,R}$, respectively. A simple condition on ${\cal D}$ guarantees that the generating function $f(x,{\cal L,D,R})$ has only a simple pole on its circle of convergence and this at $r({\cal D})$, a function independent of ${\cal L}$ and ${\cal R}$. Thus the number of compositions is asymptotic to $Ar({\cal D})^{-n}$ for a suitable constant $A=A({\cal L,D,R})$. We prove a multivariate central and local limit theorem and apply it to various statistics of random locally restricted compositions of $n$, such as number of parts, numbers of parts of given sizes, and number of rises. The first and last parts are shown to have limiting distributions and to be asymptotically independent. If ${\cal D}$ has only finitely many positive elements ${\cal D}^+$, or finitely many negative elements ${\cal D}^-$, then the largest part and number of distinct part sizes are almost surely $\Theta((\log n)^{1/2})$. On the other hand, when both ${\cal D}^+$ and ${\cal D}^-$ have a positive asymptotic lower "local log-density", we prove that the largest part and number of distinct part sizes are almost surely $\Theta(\log n)$, and we give sufficient conditions for the largest part to be almost surely asymptotic to $\log_{1/r({\cal D})}n$.