CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
  location:  Publicationsjournals
Publications        
Search results

Search: MSC category 05 ( Combinatorics )

  Expand all        Collapse all Results 1 - 25 of 73

1. CJM Online first

Bernardi, Olivier; Curien, Nicolas; Miermont, Grégory
A Boltzmann approach to percolation on random triangulations
We study the percolation model on Boltzmann triangulations using a generating function approach. More precisely, we consider a Boltzmann model on the set of finite planar triangulations, together with a percolation configuration (either site-percolation or bond-percolation) on this triangulation. By enumerating triangulations with boundaries according to both the boundary length and the number of vertices/edges on the boundary, we are able to identify a phase transition for the geometry of the origin cluster. For instance, we show that the probability that a percolation interface has length $n$ decays exponentially with $n$ except at a particular value $p_c$ of the percolation parameter $p$ for which the decay is polynomial (of order $n^{-10/3}$). Moreover, the probability that the origin cluster has size $n$ decays exponentially if $p\lt p_c$ and polynomially if $p\geq p_c$. The critical percolation value is $p_c=1/2$ for site percolation, and $p_c=\frac{2\sqrt{3}-1}{11}$ for bond percolation. These values coincide with critical percolation thresholds for infinite triangulations identified by Angel for site-percolation, and by Angel and Curien for bond-percolation, and we give an independent derivation of these percolation thresholds. Lastly, we revisit the criticality conditions for random Boltzmann maps, and argue that at $p_c$, the percolation clusters conditioned to have size $n$ should converge toward the stable map of parameter $ \frac{7}{6}$ introduced by Le Gall and Miermont. This enables us to derive heuristically some new critical exponents.

Keywords:random map, stable map, critical percolation, gasket
Categories:60K35, 60D05, 05A16

2. CJM Online first

Cushing, David; Liu, Shiping; Peyerimhoff, Norbert
Bakry-Émery Curvature Functions on Graphs
We study local properties of the Bakry-Émery curvature function $\mathcal{K}_{G,x}:(0,\infty]\to \mathbb{R}$ at a vertex $x$ of a graph $G$ systematically. Here $\mathcal{K}_{G,x}(\mathcal{N})$ is defined as the optimal curvature lower bound $\mathcal{K}$ in the Bakry-Émery curvature-dimension inequality $CD(\mathcal{K},\mathcal{N})$ that $x$ satisfies. We provide upper and lower bounds for the curvature functions, introduce fundamental concepts like curvature sharpness and $S^1$-out regularity, and relate the curvature functions of $G$ with various spectral properties of (weighted) graphs constructed from local structures of $G$. We prove that the curvature functions of the Cartesian product of two graphs $G_1,G_2$ are equal to an abstract product of curvature functions of $G_1,G_2$. We explore the curvature functions of Cayley graphs and many particular (families of) examples. We present various conjectures and construct an infinite increasing family of $6$-regular graphs which satisfy $CD(0,\infty)$ but are not Cayley graphs.

Keywords:Bakry-Émery curvature, curvature-dimension inequality, Cayley graph, Cartesian product
Categories:05C50, 52C99, 53A40

3. CJM 2018 (vol 70 pp. 1416)

Yeats, Karen
A Special Case of Completion Invariance for the $c_2$ Invariant of a Graph
The $c_2$ invariant is an arithmetic graph invariant defined by Schnetz. It is useful for understanding Feynman periods. Brown and Schnetz conjectured that the $c_2$ invariant has a particular symmetry known as completion invariance. This paper will prove completion invariance of the $c_2$ invariant in the case that we are over the field with 2 elements and the completed graph has an odd number of vertices. The methods involve enumerating certain edge bipartitions of graphs; two different constructions are needed.

Keywords:$c_2$ invariant, Feynman graph, edge partition, spanning forest, completion conjecture
Categories:05C31, 05C30, 81T18

4. CJM Online first

Liu, Ricky Ini; Morales, Alejandro H.; Mészáros, Karola
Flow polytopes and the space of diagonal harmonics
A result of Haglund implies that the $(q,t)$-bigraded Hilbert series of the space of diagonal harmonics is a $(q,t)$-Ehrhart function of the flow polytope of a complete graph with netflow vector $(-n, 1, \dots, 1).$ We study the $(q,t)$-Ehrhart functions of flow polytopes of threshold graphs with arbitrary netflow vectors. Our results generalize previously known specializations of the mentioned bigraded Hilbert series at $t=1$, $0$, and $q^{-1}$. As a corollary to our results, we obtain a proof of a conjecture of Armstrong, Garsia, Haglund, Rhoades and Sagan about the $(q, q^{-1})$-Ehrhart function of the flow polytope of a complete graph with an arbitrary netflow vector.

Keywords:flow polytope, threshold graph, diagonal harmonic, Tesler matrix
Categories:05E10, 05C21, 52B20

5. CJM Online first

Green, Ben Joseph; Lindqvist, Sofia
Monochromatic solutions to $x + y = z^2$
Suppose that $\mathbb{N}$ is $2$-coloured. Then there are infinitely many monochromatic solutions to $x + y = z^2$. On the other hand, there is a $3$-colouring of $\mathbb{N}$ with only finitely many monochromatic solutions to this equation.

Keywords:additive combinatorics, Ramsey theory
Categories:11B75, 05D10

6. CJM Online first

de Joannis de Verclos, Rémi; Kang, Ross J.; Pastor, Lucas
Colouring squares of claw-free graphs
Is there some absolute $\varepsilon > 0$ such that for any claw-free graph $G$, the chromatic number of the square of $G$ satisfies $\chi(G^2) \le (2-\varepsilon) \omega(G)^2$, where $\omega(G)$ is the clique number of $G$? Erdős and Nešetřil asked this question for the specific case of $G$ the line graph of a simple graph and this was answered in the affirmative by Molloy and Reed. We show that the answer to the more general question is also yes, and moreover that it essentially reduces to the original question of Erdős and Nešetřil.

Keywords:graph colouring, Erdős--Nešetřil conjecture, claw-free graphs
Categories:05C15, 05C35, 05C70

7. CJM Online first

Barlow, Martin T.; Járai, Antal A.
Geometry of uniform spanning forest components in high dimensions
We study the geometry of the component of the origin in the uniform spanning forest of $\mathbb{Z}^d$ and give bounds on the size of balls in the intrinsic metric.

Keywords:uniform spanning forest, loop-erased random walk
Categories:60D05, 05C05, 31C20

8. CJM 2017 (vol 70 pp. 925)

McDiarmid, Colin; Wood, David R.
Edge-Maximal Graphs on Surfaces
We prove that for every surface $\Sigma$ of Euler genus $g$, every edge-maximal embedding of a graph in $\Sigma$ is at most $O(g)$ edges short of a triangulation of $\Sigma$. This provides the first answer to an open problem of Kainen (1974).

Keywords:graph, surface, embedding
Category:05C10

9. CJM 2016 (vol 69 pp. 143)

Levinson, Jake
One-dimensional Schubert Problems with Respect to Osculating Flags
We consider Schubert problems with respect to flags osculating the rational normal curve. These problems are of special interest when the osculation points are all real -- in this case, for zero-dimensional Schubert problems, the solutions are "as real as possible". Recent work by Speyer has extended the theory to the moduli space $ \overline{\mathcal{M}_{0,r}} $, allowing the points to collide. These give rise to smooth covers of $ \overline{\mathcal{M}_{0,r}} (\mathbb{R}) $, with structure and monodromy described by Young tableaux and jeu de taquin. In this paper, we give analogous results on one-dimensional Schubert problems over $ \overline{\mathcal{M}_{0,r}} $. Their (real) geometry turns out to be described by orbits of Schützenberger promotion and a related operation involving tableau evacuation. Over $\mathcal{M}_{0,r}$, our results show that the real points of the solution curves are smooth. We also find a new identity involving "first-order" K-theoretic Littlewood-Richardson coefficients, for which there does not appear to be a known combinatorial proof.

Keywords:Schubert calculus, stable curves, Shapiro-Shapiro Conjecture, jeu de taquin, growth diagram, promotion
Categories:14N15, 05E99

10. CJM 2016 (vol 69 pp. 21)

Grinberg, Darij
Dual Creation Operators and a Dendriform Algebra Structure on the Quasisymmetric Functions
The dual immaculate functions are a basis of the ring $\operatorname*{QSym}$ of quasisymmetric functions, and form one of the most natural analogues of the Schur functions. The dual immaculate function corresponding to a composition is a weighted generating function for immaculate tableaux in the same way as a Schur function is for semistandard Young tableaux; an " immaculate tableau" is defined similarly to be a semistandard Young tableau, but the shape is a composition rather than a partition, and only the first column is required to strictly increase (whereas the other columns can be arbitrary; but each row has to weakly increase). Dual immaculate functions have been introduced by Berg, Bergeron, Saliola, Serrano and Zabrocki in arXiv:1208.5191, and have since been found to possess numerous nontrivial properties. In this note, we prove a conjecture of Mike Zabrocki which provides an alternative construction for the dual immaculate functions in terms of certain "vertex operators". The proof uses a dendriform structure on the ring $\operatorname*{QSym}$; we discuss the relation of this structure to known dendriform structures on the combinatorial Hopf algebras $\operatorname*{FQSym}$ and $\operatorname*{WQSym}$.

Keywords:combinatorial Hopf algebras, quasisymmetric functions, dendriform algebras, immaculate functions, Young tableaux
Category:05E05

11. CJM 2016 (vol 68 pp. 876)

Ostrovskii, Mikhail; Randrianantoanina, Beata
Metric Spaces Admitting Low-distortion Embeddings into All $n$-dimensional Banach Spaces
For a fixed $K\gg 1$ and $n\in\mathbb{N}$, $n\gg 1$, we study metric spaces which admit embeddings with distortion $\le K$ into each $n$-dimensional Banach space. Classical examples include spaces embeddable into $\log n$-dimensional Euclidean spaces, and equilateral spaces. We prove that good embeddability properties are preserved under the operation of metric composition of metric spaces. In particular, we prove that $n$-point ultrametrics can be embedded with uniformly bounded distortions into arbitrary Banach spaces of dimension $\log n$. The main result of the paper is a new example of a family of finite metric spaces which are not metric compositions of classical examples and which do embed with uniformly bounded distortion into any Banach space of dimension $n$. This partially answers a question of G. Schechtman.

Keywords:basis constant, bilipschitz embedding, diamond graph, distortion, equilateral set, ultrametric
Categories:46B85, 05C12, 30L05, 46B15, 52A21

12. CJM 2016 (vol 68 pp. 481)

Bacher, Roland; Reutenauer, Christophe
Number of Right Ideals and a $q$-analogue of Indecomposable Permutations
We prove that the number of right ideals of codimension $n$ in the algebra of noncommutative Laurent polynomials in two variables over the finite field $\mathbb F_q$ is equal to $(q-1)^{n+1} q^{\frac{(n+1)(n-2)}{2}}\sum_\theta q^{inv(\theta)}$, where the sum is over all indecomposable permutations in $S_{n+1}$ and where $inv(\theta)$ stands for the number of inversions of $\theta$.

Keywords:permutation, indecomposable permutation, subgroups of free groups
Categories:05A15, 05A19

13. CJM 2015 (vol 68 pp. 44)

Fernández Bretón, David J.
Strongly Summable Ultrafilters, Union Ultrafilters, and the Trivial Sums Property
We answer two questions of Hindman, Steprāns and Strauss, namely we prove that every strongly summable ultrafilter on an abelian group is sparse and has the trivial sums property. Moreover we show that in most cases the sparseness of the given ultrafilter is a consequence of its being isomorphic to a union ultrafilter. However, this does not happen in all cases: we also construct (assuming Martin's Axiom for countable partial orders, i.e. $\operatorname{cov}(\mathcal{M})=\mathfrak c$), on the Boolean group, a strongly summable ultrafilter that is not additively isomorphic to any union ultrafilter.

Keywords:ultrafilter, Stone-Cech compactification, sparse ultrafilter, strongly summable ultrafilter, union ultrafilter, finite sum, additive isomorphism, trivial sums property, Boolean group, abelian group
Categories:03E75, 54D35, 54D80, 05D10, 05A18, 20K99

14. CJM 2014 (vol 67 pp. 721)

Allen, Peter; Böttcher, Julia; Hladký, Jan; Piguet, Diana
A Density Corrádi-Hajnal Theorem
We find, for all sufficiently large $n$ and each $k$, the maximum number of edges in an $n$-vertex graph which does not contain $k+1$ vertex-disjoint triangles. This extends a result of Moon [Canad. J. Math. 20 (1968), 96-102] which is in turn an extension of Mantel's Theorem. Our result can also be viewed as a density version of the Corrádi-Hajnal Theorem.

Keywords:graph theory, Turan's Theorem, Mantel's Theorem, Corrádi-Hajnal Theorem, triangle
Category:05C35

15. CJM 2014 (vol 66 pp. 1327)

Mohar, Bojan; Skoda, Petr
Obstructions of Connectivity Two for Embedding Graphs into the Torus
The complete set of minimal obstructions for embedding graphs into the torus is still not determined. In this paper, we present all obstructions for the torus of connectivity 2. Furthermore, we describe the building blocks of obstructions of connectivity 2 for any orientable surface.

Keywords:torus, obstruction, minor, connectivity 2
Categories:05C10, 05C83

16. CJM 2013 (vol 65 pp. 1287)

Reihani, Kamran
$K$-theory of Furstenberg Transformation Group $C^*$-algebras
The paper studies the $K$-theoretic invariants of the crossed product $C^{*}$-algebras associated with an important family of homeomorphisms of the tori $\mathbb{T}^{n}$ called Furstenberg transformations. Using the Pimsner-Voiculescu theorem, we prove that given $n$, the $K$-groups of those crossed products, whose corresponding $n\times n$ integer matrices are unipotent of maximal degree, always have the same rank $a_{n}$. We show using the theory developed here that a claim made in the literature about the torsion subgroups of these $K$-groups is false. Using the representation theory of the simple Lie algebra $\frak{sl}(2,\mathbb{C})$, we show that, remarkably, $a_{n}$ has a combinatorial significance. For example, every $a_{2n+1}$ is just the number of ways that $0$ can be represented as a sum of integers between $-n$ and $n$ (with no repetitions). By adapting an argument of van Lint (in which he answered a question of Erdős), a simple, explicit formula for the asymptotic behavior of the sequence $\{a_{n}\}$ is given. Finally, we describe the order structure of the $K_{0}$-groups of an important class of Furstenberg crossed products, obtaining their complete Elliott invariant using classification results of H. Lin and N. C. Phillips.

Keywords:$K$-theory, transformation group $C^*$-algebra, Furstenberg transformation, Anzai transformation, minimal homeomorphism, positive cone, minimal homeomorphism
Categories:19K14, 19K99, 46L35, 46L80, , 05A15, 05A16, 05A17, 15A36, 17B10, 17B20, 37B05, 54H20

17. CJM 2013 (vol 66 pp. 525)

Berg, Chris; Bergeron, Nantel; Saliola, Franco; Serrano, Luis; Zabrocki, Mike
A Lift of the Schur and Hall-Littlewood Bases to Non-commutative Symmetric Functions
We introduce a new basis of the algebra of non-commutative symmetric functions whose images under the forgetful map are Schur functions when indexed by a partition. Dually, we build a basis of the quasi-symmetric functions which expand positively in the fundamental quasi-symmetric functions. We then use the basis to construct a non-commutative lift of the Hall-Littlewood symmetric functions with similar properties to their commutative counterparts.

Keywords:Hall-Littlewood polynomial, symmetric function, quasisymmetric function, tableau
Category:05E05

18. CJM 2013 (vol 65 pp. 843)

Jonsson, Jakob
3-torsion in the Homology of Complexes of Graphs of Bounded Degree
For $\delta \ge 1$ and $n \ge 1$, consider the simplicial complex of graphs on $n$ vertices in which each vertex has degree at most $\delta$; we identify a given graph with its edge set and admit one loop at each vertex. This complex is of some importance in the theory of semigroup algebras. When $\delta = 1$, we obtain the matching complex, for which it is known that there is $3$-torsion in degree $d$ of the homology whenever $\frac{n-4}{3} \le d \le \frac{n-6}{2}$. This paper establishes similar bounds for $\delta \ge 2$. Specifically, there is $3$-torsion in degree $d$ whenever $\frac{(3\delta-1)n-8}{6} \le d \le \frac{\delta (n-1) - 4}{2}$. The procedure for detecting torsion is to construct an explicit cycle $z$ that is easily seen to have the property that $3z$ is a boundary. Defining a homomorphism that sends $z$ to a non-boundary element in the chain complex of a certain matching complex, we obtain that $z$ itself is a non-boundary. In particular, the homology class of $z$ has order $3$.

Keywords:simplicial complex, simplicial homology, torsion group, vertex degree
Categories:05E45, 55U10, 05C07, 20K10

19. CJM 2013 (vol 66 pp. 205)

Iovanov, Miodrag Cristian
Generalized Frobenius Algebras and Hopf Algebras
"Co-Frobenius" coalgebras were introduced as dualizations of Frobenius algebras. We previously showed that they admit left-right symmetric characterizations analogue to those of Frobenius algebras. We consider the more general quasi-co-Frobenius (QcF) coalgebras; the first main result in this paper is that these also admit symmetric characterizations: a coalgebra is QcF if it is weakly isomorphic to its (left, or right) rational dual $Rat(C^*)$, in the sense that certain coproduct or product powers of these objects are isomorphic. Fundamental results of Hopf algebras, such as the equivalent characterizations of Hopf algebras with nonzero integrals as left (or right) co-Frobenius, QcF, semiperfect or with nonzero rational dual, as well as the uniqueness of integrals and a short proof of the bijectivity of the antipode for such Hopf algebras all follow as a consequence of these results. This gives a purely representation theoretic approach to many of the basic fundamental results in the theory of Hopf algebras. Furthermore, we introduce a general concept of Frobenius algebra, which makes sense for infinite dimensional and for topological algebras, and specializes to the classical notion in the finite case. This will be a topological algebra $A$ that is isomorphic to its complete topological dual $A^\vee$. We show that $A$ is a (quasi)Frobenius algebra if and only if $A$ is the dual $C^*$ of a (quasi)co-Frobenius coalgebra $C$. We give many examples of co-Frobenius coalgebras and Hopf algebras connected to category theory, homological algebra and the newer q-homological algebra, topology or graph theory, showing the importance of the concept.

Keywords:coalgebra, Hopf algebra, integral, Frobenius, QcF, co-Frobenius
Categories:16T15, 18G35, 16T05, 20N99, 18D10, 05E10

20. CJM 2012 (vol 65 pp. 863)

Josuat-Vergès, Matthieu
Cumulants of the $q$-semicircular Law, Tutte Polynomials, and Heaps
The $q$-semicircular distribution is a probability law that interpolates between the Gaussian law and the semicircular law. There is a combinatorial interpretation of its moments in terms of matchings where $q$ follows the number of crossings, whereas for the free cumulants one has to restrict the enumeration to connected matchings. The purpose of this article is to describe combinatorial properties of the classical cumulants. We show that like the free cumulants, they are obtained by an enumeration of connected matchings, the weight being now an evaluation of the Tutte polynomial of a so-called crossing graph. The case $q=0$ of these cumulants was studied by Lassalle using symmetric functions and hypergeometric series. We show that the underlying combinatorics is explained through the theory of heaps, which is Viennot's geometric interpretation of the Cartier-Foata monoid. This method also gives a general formula for the cumulants in terms of free cumulants.

Keywords:moments, cumulants, matchings, Tutte polynomials, heaps
Categories:05A18, 05C31, 46L54

21. CJM 2012 (vol 65 pp. 1020)

Goulden, I. P.; Guay-Paquet, Mathieu; Novak, Jonathan
Monotone Hurwitz Numbers in Genus Zero
Hurwitz numbers count branched covers of the Riemann sphere with specified ramification data, or equivalently, transitive permutation factorizations in the symmetric group with specified cycle types. Monotone Hurwitz numbers count a restricted subset of these branched covers related to the expansion of complete symmetric functions in the Jucys-Murphy elements, and have arisen in recent work on the the asymptotic expansion of the Harish-Chandra-Itzykson-Zuber integral. In this paper we begin a detailed study of monotone Hurwitz numbers. We prove two results that are reminiscent of those for classical Hurwitz numbers. The first is the monotone join-cut equation, a partial differential equation with initial conditions that characterizes the generating function for monotone Hurwitz numbers in arbitrary genus. The second is our main result, in which we give an explicit formula for monotone Hurwitz numbers in genus zero.

Keywords:Hurwitz numbers, matrix models, enumerative geometry
Categories:05A15, 14E20, 15B52

22. CJM 2012 (vol 65 pp. 222)

Sauer, N. W.
Distance Sets of Urysohn Metric Spaces
A metric space $\mathrm{M}=(M;\operatorname{d})$ is {\em homogeneous} if for every isometry $f$ of a finite subspace of $\mathrm{M}$ to a subspace of $\mathrm{M}$ there exists an isometry of $\mathrm{M}$ onto $\mathrm{M}$ extending $f$. The space $\mathrm{M}$ is {\em universal} if it isometrically embeds every finite metric space $\mathrm{F}$ with $\operatorname{dist}(\mathrm{F})\subseteq \operatorname{dist}(\mathrm{M})$. (With $\operatorname{dist}(\mathrm{M})$ being the set of distances between points in $\mathrm{M}$.) A metric space $\boldsymbol{U}$ is an {\em Urysohn} metric space if it is homogeneous, universal, separable and complete. (It is not difficult to deduce that an Urysohn metric space $\boldsymbol{U}$ isometrically embeds every separable metric space $\mathrm{M}$ with $\operatorname{dist}(\mathrm{M})\subseteq \operatorname{dist}(\boldsymbol{U})$.) The main results are: (1) A characterization of the sets $\operatorname{dist}(\boldsymbol{U})$ for Urysohn metric spaces $\boldsymbol{U}$. (2) If $R$ is the distance set of an Urysohn metric space and $\mathrm{M}$ and $\mathrm{N}$ are two metric spaces, of any cardinality with distances in $R$, then they amalgamate disjointly to a metric space with distances in $R$. (3) The completion of every homogeneous, universal, separable metric space $\mathrm{M}$ is homogeneous.

Keywords:partitions of metric spaces, Ramsey theory, metric geometry, Urysohn metric space, oscillation stability
Categories:03E02, 22F05, 05C55, 05D10, 22A05, 51F99

23. CJM 2012 (vol 65 pp. 241)

Aguiar, Marcelo; Lauve, Aaron
Lagrange's Theorem for Hopf Monoids in Species
Following Radford's proof of Lagrange's theorem for pointed Hopf algebras, we prove Lagrange's theorem for Hopf monoids in the category of connected species. As a corollary, we obtain necessary conditions for a given subspecies $\mathbf k$ of a Hopf monoid $\mathbf h$ to be a Hopf submonoid: the quotient of any one of the generating series of $\mathbf h$ by the corresponding generating series of $\mathbf k$ must have nonnegative coefficients. Other corollaries include a necessary condition for a sequence of nonnegative integers to be the dimension sequence of a Hopf monoid in the form of certain polynomial inequalities, and of a set-theoretic Hopf monoid in the form of certain linear inequalities. The latter express that the binomial transform of the sequence must be nonnegative.

Keywords:Hopf monoids, species, graded Hopf algebras, Lagrange's theorem, generating series, Poincaré-Birkhoff-Witt theorem, Hopf kernel, Lie kernel, primitive element, partition, composition, linear order, cyclic order, derangement
Categories:05A15, 05A20, 05E99, 16T05, 16T30, 18D10, 18D35

24. CJM 2011 (vol 64 pp. 1090)

Rosso, Daniele
Classic and Mirabolic Robinson-Schensted-Knuth Correspondence for Partial Flags
In this paper we first generalize to the case of partial flags a result proved both by Spaltenstein and by Steinberg that relates the relative position of two complete flags and the irreducible components of the flag variety in which they lie, using the Robinson-Schensted-Knuth correspondence. Then we use this result to generalize the mirabolic Robinson-Schensted-Knuth correspondence defined by Travkin, to the case of two partial flags and a line.

Keywords:partial flag varieties, RSK correspondence
Categories:14M15, 05A05

25. CJM 2011 (vol 64 pp. 1201)

Aistleitner, Christoph; Elsholtz, Christian
The Central Limit Theorem for Subsequences in Probabilistic Number Theory
Let $(n_k)_{k \geq 1}$ be an increasing sequence of positive integers, and let $f(x)$ be a real function satisfying \begin{equation} \tag{1} f(x+1)=f(x), \qquad \int_0^1 f(x) ~dx=0,\qquad \operatorname{Var_{[0,1]}} f \lt \infty. \end{equation} If $\lim_{k \to \infty} \frac{n_{k+1}}{n_k} = \infty$ the distribution of \begin{equation} \tag{2} \frac{\sum_{k=1}^N f(n_k x)}{\sqrt{N}} \end{equation} converges to a Gaussian distribution. In the case $$ 1 \lt \liminf_{k \to \infty} \frac{n_{k+1}}{n_k}, \qquad \limsup_{k \to \infty} \frac{n_{k+1}}{n_k} \lt \infty $$ there is a complex interplay between the analytic properties of the function $f$, the number-theoretic properties of $(n_k)_{k \geq 1}$, and the limit distribution of (2). In this paper we prove that any sequence $(n_k)_{k \geq 1}$ satisfying $\limsup_{k \to \infty} \frac{n_{k+1}}{n_k} = 1$ contains a nontrivial subsequence $(m_k)_{k \geq 1}$ such that for any function satisfying (1) the distribution of $$ \frac{\sum_{k=1}^N f(m_k x)}{\sqrt{N}} $$ converges to a Gaussian distribution. This result is best possible: for any $\varepsilon\gt 0$ there exists a sequence $(n_k)_{k \geq 1}$ satisfying $\limsup_{k \to \infty} \frac{n_{k+1}}{n_k} \leq 1 + \varepsilon$ such that for every nontrivial subsequence $(m_k)_{k \geq 1}$ of $(n_k)_{k \geq 1}$ the distribution of (2) does not converge to a Gaussian distribution for some $f$. Our result can be viewed as a Ramsey type result: a sufficiently dense increasing integer sequence contains a subsequence having a certain requested number-theoretic property.

Keywords:central limit theorem, lacunary sequences, linear Diophantine equations, Ramsey type theorem
Categories:60F05, 42A55, 11D04, 05C55, 11K06
Page
   1 2 3    

© Canadian Mathematical Society, 2018 : https://cms.math.ca/