Ascents of size less than <Emphasis Type="Italic">d</Emphasis> in compositions

A composition of a positive integer n is a finite sequence π₁π₂...π _m of positive integers such that π₁+...+π _m = n. Let d be a fixed number. We say that we have an ascent of size d or more (respectively, less than d) if π _i+1 ≥ π _i +d (respectively, π _i < π _i+1 < π _i + d). Recently, Brennan and Knopfmacher determined the mean, variance and limiting distribution of the number of ascents of size d or more in the set of compositions of n. In this paper, we find an explicit formula for the multi-variable generating function for the number of compositions of n according to the number of parts, ascents of size d or more, ascents of size less than d, descents and levels. Also, we extend the results of Brennan and Knopfmacher to the case of ascents of size less than d. More precisely, we determine the mean, variance and limiting distribution of the number of ascents of size less than d in the set of compositions of n.     

Compositions with distinct parts

The number of compositionsC(n) of a positive integern into distinct parts can be considered as a natural analogue of the numberq(n) of distinct partitions ofn. We obtain an asymptotic estimate forC(n) and in addition show that the sequence {C(n, k)} of distinct compositions ofn withk distinct parts is unimodal. Our analysis is more complicated than is usual for composition problems. The results imply however that the behaviour of these functions is of comparable complexity to partition problems.     

The expected value of some functions of the convex hull of a random set of points sampled inR d

This paper presents formulas and asymptotic expansions for the expected number of vertices and the expected volume of the convex hull of a sample ofn points taken from the uniform distribution on ad-dimensional ball. It is shown that the expected number of vertices is asymptotically proportional ton ^{(d−1)/(d+1)}, which generalizes Rényi and Sulanke’s asymptotic raten ^(1/3) ford=2 and agrees with Raynaud’s asymptotic raten ^{(d−1)/(d+1)} for the expected number of facets, as it should be, by Bárány’s result that the expected number ofs-dimensional faces has order of magnitude independent ofs. Our formulas agree with the ones Efron obtained ford=2 and 3 under more general distributions. An application is given to the estimation of the probability content of an unknown convex subset ofR ^d .     

On the number of partitions with distinct even parts

Let ped(n) be the number of partitions of n wherein even parts are distinct (and odd parts are unrestricted). We obtain many congruences for ped(n)mod2 and mod4 by the theory of Hecke eigenforms.     

Combinatorics of n-color cyclic compositions

Integer compositions and related enumeration problems have been of interest to combinatorialists and number theorists for a long time. The cyclic and colored analogues of this concept, although interesting, have not been extensively studied. In this paper we explore the combinatorics of $n$-color cyclic compositions, presenting generating functions, bijections, asymptotic formulas related to the number of such compositions, the number of parts, and the number of restricted parts.     

On the clustering of independent uniform random variables

We consider the number K_n of clusters at a distance level d_n ∈ (0, 1) of n independent random variables uniformly distributed in [0, 1], or the number K_n of connected components in the random interval graph generated by these variables and d_n, and, depending upon how fast d_n → 0 as n → ∞, determine the asymptotic distribution of K_n, with rates of convergence, and of related random variables that describe the cluster sizes. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Distribution of subgraphs of random regular graphs

We obtain the asymptotic distribution of the number of copies of a fixed subgraph H in a random d‐regular graph, provided H is strictly balanced and d = d(n) is chosen so that the expected number of copies of H tends to infinity (but not too quickly), and the expected number of copies sharing edges with two other copies is bounded. The proof of asymptotic normality of the distribution uses a method of factorial moments for variables with unbounded means that was recently derived by the authors. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Asymptotic properties of combinatorial optimization problems in <Emphasis Type="Italic">p</Emphasis>-adic space

In this article we consider two well known combinatorial optimization problems (travel-ling salesman and minimum spanning tree), when n points are randomly distributed in a unit p-adic ball of dimension d. We investigate an asymptotic behavior of their solutions at large number of n. It was earlier found that the average lengths of the optimal solutions in both problems are of order n ^1−1/d . Here we show that standard deviations of the optimal lengths are of order n ^1/2−1/d if d > 1, and prove that large number laws are valid only for special subsequences of n.     

Counting 5‐connected planar triangulations

Let t_n be the number of rooted 5‐connected planar triangulations with 2n faces. We find t_n exactly for small n, as well as an asymptotic formula for n → ∞. Our results are found by compositions of lower connectivity maps whose faces are triangles or quadrangles. We also find the asymptotic number of cyclically 5‐edge connected cubic planar graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 18–35, 2001     

On the connectivity of graphs generated by a sum of random mappings

We consider four models of random directed multigraphs with n labeled vertices of out-degree d. First we establish formal relationships between our models with respect to exact and asymptotic (as n → ∞) probabilities of possessing a graph monotone property. We also study the asymptotic behavior of the strength of connectivity of the underlying simple graphs when d = o(n). © 1993 John Wiley & Sons, Inc.     

Counting partitions on the abacus

In 2003, Maróti showed that one could use the machinery of ℓ-cores and ℓ-quotients of partitions to establish lower bounds for p(n), the number of partitions of n. In this paper we explore these ideas in the case ℓ=2, using them to give a largely combinatorial proof of an effective upper bound on p(n), and to prove asymptotic formulae for the number of self-conjugate partitions, and the number of partitions with distinct parts. In a further application we give a combinatorial proof of an identity originally due to Gauss. Dedicated to the memory of Dr. Manfred Schocker (1970–2006)     

Higher-dimensional voronoi diagrams in linear expected time

A general method is presented for determining the mathematical expectation of the combinatorial complexity and other properties of the Voronoi diagram ofn independent and identically distributed points. The method is applied to derive exact asymptotic bounds on the expected number of vertices of the Voronoi diagram of points chosen from the uniform distribution on the interior of ad-dimensional ball; it is shown that in this case, the complexity of the diagram is ∵(n) for fixedd. An algorithm for constructing the Voronoid diagram is presented and analyzed. The algorithm is shown to require only ∵(n) time on average for random points from ad-ball assuming a real-RAM model of computation with a constant-time floor function. This algorithm is asymptotically faster than any previously known and optimal in the average-case sense. Based upon work supported by the National Science Foundation under Grant No. CCR-8658139 while the author was a student at Carnegie-Mellon University.     

Equidistribution of Heegner points and the partition function

Let p(n) denote the number of partitions of a positive integer n. In this paper we study the asymptotic growth of p(n) using the equidistribution of Galois orbits of Heegner points on the modular curve X ₀(6). We obtain a new asymptotic formula for p(n) with an effective error term which is O(n^-(\frac12+d)){O(n^{-(\frac{1}{2}+\delta)})} for some δ > 0. We then use this asymptotic formula to sharpen the classical bounds of Hardy and Ramanujan, Rademacher, and Lehmer on the error term in Rademacher’s exact formula for p(n).     

On the Borsuk and Erdös—Hadwiger numbers

Two classical problems of combinatorial geometry, the Borsuk problem about splitting sets into parts of smaller diameter and the Erdös—Hadwiger problem about coloring Euclidean space, are studied. New asymptotic estimates are obtained for the quantities f(d) (the minimal number of parts of smaller diameter into which any bounded set in ?^d can be decomposed) and χ(?^d) (the minimal number of colors required to color all points ?^d so that any points at distance 1 from each other have different colors), which are the main objects of study in these problems.     

The number of graphs and a random graph with a given degree sequence

We consider the set of all graphs on n labeled vertices with prescribed degrees D = (d₁,…,d_n). For a wide class of tame degree sequences D we obtain a computationally efficient asymptotic formula approximating the number of graphs within a relative error which approaches 0 as n grows. As a corollary, we prove that the structure of a random graph with a given tame degree sequence D is well described by a certain maximum entropy matrix computed from D. We also establish an asymptotic formula for the number of bipartite graphs with prescribed degrees of vertices, or, equivalently, for the number of 0‐1 matrices with prescribed row and column sums. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

On the Discrepancy for Boxes and Polytopes

 We consider so-called Tusnády’s problem in dimension d: Given an n-point set P in R ^d , color the points of P red or blue in such a way that for any d-dimensional interval B, the number of red points in differs from the number of blue points in by at most Δ, where should be as small as possible. We slightly improve previous results of Beck, Bohus, and Srinivasan by showing that , with a simple proof. The same asymptotic bound is shown for an analogous problem where B is allowed to be any translated and scaled copy of a fixed convex polytope A in R ^d . Here the constant of proportionality depends on A and we give an explicit estimate. The same asymptotic bounds also follow for the Lebesgue-measure discrepancy, which improves and simplifies results of Beck and of Károlyi.     

On the Discrepancy for Boxes and Polytopes

 We consider so-called Tusnády’s problem in dimension d: Given an n-point set P in R ^d , color the points of P red or blue in such a way that for any d-dimensional interval B, the number of red points in differs from the number of blue points in by at most Δ, where should be as small as possible. We slightly improve previous results of Beck, Bohus, and Srinivasan by showing that , with a simple proof. The same asymptotic bound is shown for an analogous problem where B is allowed to be any translated and scaled copy of a fixed convex polytope A in R ^d . Here the constant of proportionality depends on A and we give an explicit estimate. The same asymptotic bounds also follow for the Lebesgue-measure discrepancy, which improves and simplifies results of Beck and of Károlyi. Received 17 November 1997; in revised form 30 July 1998     

How Many Ways Can One Draw A Graph?

Using results from extremal graph theory, we determine the asymptotic number of string graphs with n vertices, i.e., graphs that can be obtained as the intersection graph of a system of continuous arcs in the plane. The number becomes much smaller, for any fixed d, if we restrict our attention to systems of arcs, any two of which cross at most d times. As an application, we estimate the number of different drawings of the complete graph K_n with n vertices under various side conditions. Dedicated to Miklós Simonovits on his sixtieth birthday * Supported by NSF grant CR-00-98246, PSC-CUNY Research Award 62450-0031 and OTKA-T-032452. † Supported by OTKA-T-032452 and OTKA-T-038397.     

Compositions of n as alternating sequences of weakly increasing and strictly decreasing partitions

Compositions and partitions of positive integers are often studied in separate frameworks where partitions are given by q-series generating functions and compositions exhibiting specific patterns are designated by generating functions for these patterns. Here, we view compositions as alternating sequences of weakly increasing and strictly decreasing partitions (i.e. alternating blocks). We obtain generating functions for the number of such partitions in terms of the size of the composition, the number of parts and the total number of “valleys” and “peaks”. From this, we find the total number of “peaks” and “valleys” in the composition of n which have the mentioned pattern. We also obtain the generating function for compositions which split into just two partition blocks. Finally, we obtain the two generating functions for compositions of n that start either with a weakly increasing partition or a strictly decreasing partition.     

Arithmetic Properties of Summands of Partitions II

Let d∈ℕ, d ≥ 2. We prove that a positive proportion of partitions of an integer n satisfies the following : for all 1≤ a < b≤ d, the number of the parts congruent to a (mod d) is greater than the number of the parts congruent to b (mod d). We also show that for almost all partitions the rate of the number of square free parts is . 2000 Mathematics Subject Classification: Primary—11P82