Search

Suppose \(M\) and \(N\) are positive integers and let \(k = \gcd(M, N)\), \(m = M/k\), and \(n=N/k\). We define a symmetric function \(L_{M,N}\) as a weighted sum over certain tuples of lattice paths. We show that \(L_{M,N}\) satisfies a generalization of Hogancamp and Mellit's recursion for the triply-graded Khovanov-Rozansky homology of the \(M,N\)-torus link. As a corollary, we obtain the triply-graded Khovanov-Rozansky homology of the \(M,N\)-torus link as a specialization of \(L_{M,N}\). We conjecture that \(L_{M,N}\) is equal (up to a constant) to the elliptic Hall algebra operator \(\mathbf{Q}_{m,n}\) composed \(k\) times and applied to 1.Mathematics Subject Classifications: 05E05, 57M27Keywords: Lattice paths, Dyck paths, link homology, torus links, elliptic Hall algebra, LLT polynomials

The Kahn-Saks inequality is a classical result on the number of linear extensions of finite posets. We give a new proof of this inequality for posets of width two and both elements in the same chain using explicit injections of lattice paths. As a consequence we obtain a \(q\)-analogue, a multivariate generalization and an equality condition in this case. We also discuss the equality conditions of the Kahn-Saks inequality for general posets and prove several implications between conditions conjectured to be equivalent.Mathematics Subject Classifications: 05A15, 05A19, 05A20, 05A30, 06A07Keywords: Poset inequality, Stanley's inequality, Kahn-Saks inequality, log-concavity, q-analogues, equality conditions, lattice paths

In this paper, we propose a q-analogue of the number of permutations i(n, k) of length n having k inversions known by Mahonian numbers. We investigate useful properties and some combinatorial interpretations by lattice paths/partitions and tilings. Furthermore, we give two constructive proofs of the strong q-log-concavity of the q-Mahonian numbers in k and n, respectively. In particular for q = 1 , we obtain two constructive proofs of the log-concavity of the Mahonian numbers in k and n, respectively. [ABSTRACT FROM AUTHOR]

A combinatorial theory for type R I orthogonal polynomials is given. The ingredients include weighted generalized Motzkin paths, moments, continued fractions, determinants, and histories. Several explicit examples in the Askey scheme are given. [ABSTRACT FROM AUTHOR]

This work presents a combinatorial bijection between the set of lattice paths and the set of ordered trees, both counted by the central coefficients of the expansion of the trinomial (1+x+x^2)^n. Moreover, using a combinatorial interpretation of Catalan numbers, we establish a new set of ordered trees counted by a new sequence.

Using Flajolet's combinatorial theory of continued fractions and axial symmetry of lattice paths, we show that the enumeration of certain lattice paths modulo two yields the ubiquitous Prouhet-Thue-Morse sequence. This answers an open problem of Berstel et al. [ABSTRACT FROM AUTHOR]

It is well known that for all n ≥ 1 the number n + 1 is a divisor of the central binomial coefficient 2 n n . Since the nth central binomial coefficient equals the number of lattice paths from (0, 0) to (n, n) by unit steps north or east, a natural question is whether there is a way to partition these paths into sets of n + 1 paths or n + 1 equinumerous sets of paths. The Chung–Feller theorem gives an elegant answer to this question. We pose and deliver an answer to the analogous question for 2 n - 1 , another divisor of 2 n n . We then show our main result follows from a more general observation regarding binomial coefficients n k with n and k relatively prime. A discussion of the case where n and k are not relatively prime is also given, highlighting the limitations of our methods. Finally, we come full circle and give a novel interpretation of the Catalan numbers. [ABSTRACT FROM AUTHOR]

We use results on Dyck words and lattice paths to derive a formula for the exact number of binary words of a given length with a given minimal abelian border length, tightening a bound on that number from Christodoulakis et al. (Discrete Applied Mathematics, 2014). We extend to any number of distinct abelian borders a result of Rampersad et al. (Developments in Language Theory, 2013) on the exact number of binary words of a given length with no abelian borders. We also generalize these results to partial words. [ABSTRACT FROM AUTHOR]

The number of down-steps between pairs of up-steps in kt-Dyck paths, a generalization of Dyck paths consisting of steps f(1; k); (1;-1)g such that the path stays (weakly) above the line y = -t, is studied. Results are proved bijectively and by means of generating functions, and lead to several interesting identities as well as links to other combinatorial structures. In particular, there is a connection between kt-Dyck paths and perforation patterns for punctured convolutional codes (binary matrices) used in coding theory. Surprisingly, upon restriction to usual Dyck paths this yields a new combinatorial interpretation of Catalan numbers. [ABSTRACT FROM AUTHOR]

We study a number of combinatorial and algebraic structures arising from walks on the two-dimensional integer lattice. To a given step set X ⊆ Z 2 , there are two naturally associated monoids: F X , the monoid of all X-walks/paths; and A X , the monoid of all endpoints of X-walks starting from the origin O. For each A ∈ A X , write π X (A) for the number of X-walks from O to A. Calculating the numbers π X (A) is a classical problem, leading to Fibonacci, Catalan, Motzkin, Delannoy and Schröder numbers, among many other well-studied sequences and arrays. Our main results give relationships between finiteness properties of the numbers π X (A) , geometrical properties of the step set X, algebraic properties of the monoid A X , and combinatorial properties of a certain bi-labelled digraph naturally associated to X. There is an intriguing divergence between the cases of finite and infinite step sets, and some constructions rely on highly non-trivial properties of real numbers. We also consider the case of walks constrained to stay within a given region of the plane. Several examples are considered throughout to highlight the sometimes-subtle nature of the theoretical results. [ABSTRACT FROM AUTHOR]

We consider two related models for the propagation of a curvature sensitive interface in a time independent random medium. In both cases we suppose that the medium contains obstacles that act on the propagation of the interface with an inhibitory or an acceleratory force. We show that the interface remains bounded for all times even when a small constant external driving force is applied. This phenomenon has already been known when only inhibitory obstacles are present. In this work we extend this result to the case of - for example - a random medium of random zero mean forcing. The first model we study is discrete with a random forcing on each lattice site. In this case we construct a supersolution employing a local path optimization procedure. In the second, continuous, model we consider a random heterogenous medium consisting of localized small obstacles of random sign. To construct a stationary supersolution here, we need to pass through sufficiently many blocking obstacles while avoiding any obstacles of the other sign. This is done by employing a custom percolation argument. [ABSTRACT FROM AUTHOR]

In the past twenty years, the enumeration of lattice walks with steps taken in a prescribed set S and confined to a given cone, especially the first quadrant of the plane, has been intensely studied. As a result, the generating functions of quadrant walks are now well-understood, provided the allowed steps are small, that is, S = {-1; 0; 1}². In particular, having small steps is crucial for the definition of a certain group of bi-rational transformations of the plane. It has been proved that this group is finite if and only if the corresponding generating function is D-finite (that is, it satisfies a linear differential equation with polynomial coefficients). This group is also the key to the uniform solution of 19 of the 23 small step models possessing a finite group. In contrast, almost nothing is known for walks with arbitrary steps. In this paper, we extend the definition of the group, or rather of the associated orbit, to this general case, and generalize the above uniform solution of small step models. When this approach works, it invariably yields a D-finite generating function. We apply it to many quadrant problems, including some infinite families. After developing the general theory, we consider the 13 110 two-dimensional models with steps in f􀀀2;􀀀1; 0; 1g2 having at least one 􀀀2 coordinate. We prove that only 240 of them have a finite orbit, and solve 231 of them with our method. The nine remaining models are the counterparts of the four models of the small step case that resist the uniform solution method (and which are known to have an algebraic generating function). We conjecture D-finiteness for their generating functions, but only two of them are likely to be algebraic. We also prove non-D-finiteness for the 12 870 models with an infinite orbit, except for 16 of them. [ABSTRACT FROM AUTHOR]

In the present work, lattice paths of Agarwal and Bressoud are modified by introducing backward horizontal step. These paths starting at (0, 0) with the modified terminology correspond to n–color compositions. Recurrence relations for a number of restricted n–color composition functions are proved using the lattice paths with these modifications. [ABSTRACT FROM AUTHOR]

The kinetics of molecular hydrogen reactions at the Si (100) surface has been studied by simulation to extract the physics underlying two unexpected experimental observations: apparently first-order desorption kinetics and an increase in sticking probability with hydrogen coverage. At a partially H-terminated Si(100) surface, each Si dimer assumes an unoccupied dimer (UOD), singly occupied dimer (SOD), or doubly occupied dimer (DOD) structure. In our hydrogen reaction model based on an inter-dimer mechanism, a site consisting of an adjacent pair of a DOD and a UOD (DOD/UOD) is a key component for the desorption and adsorption kinetics of hydrogen at the Si(100) surface. To simulate reaction kinetics of both reactions, DU (D: DOD, U: UOD) and SS (S: SOD) pathways are proposed: DU pathway claims that the adsorption as well as desorption of hydrogen takes place at common sites having a cis-configured SOD/SOD pair that is transformed transiently from a DOD/UOD pair by H(D) diffusion. Thus the adsorption obeys the so-called 4H mechanism, but the desorption obeys the 2H mechanism. SS pathway claims that the adsorption occurs at sites having a UOD/UOD pair, and the desorption occurs at sites having a cis-configured SOD/SOD pair that is generated by diffusion of isolated SODs. To simulate temperature-programmed-desorption spectra and sticking probability vs coverage curves, thermo-statistics for a lattice-gas system characterized with parameters for hydrogen pairing and dimer clustering is used to evaluate equilibrium populations of DOD/UOD pairs and isolated SODs. The model simulation based on the above reaction model successfully reproduces all of the complicated, coverage dependent adsorption and desorption reactions of hydrogen at Si(100) surfaces. Specifically, at high coverage above 0.1 ML majority of the adsorption and desorption proceed along the DU pathway. Hence, it is suggested that the adsorption and desorption in the high coverage regime are not microscopically reversible. On the other hand, at low coverages below 0.1 ML, the simulation shows up that the majority of adsorption proceeds along the SS pathway, and the desorption by the DU pathway. Since both reactions obey the 2H mechanism, it is suggested that the desorption and adsorption in the low coverage regime are microscopically reversible. [ABSTRACT FROM AUTHOR]

Let λ be a partition with no more than n parts. Let β be a weakly increasing n-tuple with entries from f1; :::; ng. The flagged Schur function in the variables x1; :::; xn that is indexed by λ and β has been defined to be the sum of the content weight monomials for the semistandard Young tableaux of shape λ whose values are row-wise bounded by the entries of β. Gessel and Viennot gave a determinant expression for the flagged Schur function indexed by λ and β; this could be done since the pair (λ; β) satisfied their "nonpermutable" condition for the sequence of terminals of an n-tuple of lattice paths that they used to model the tableaux. We generalize flagged Schur functions by dropping the requirement that β be weakly increasing. Then for each λ we give a condition on the entries of β for the pair (λ; β) to be nonpermutable that is both necessary and sufficient. When the parts of λ are not distinct there will be multiple row bound n-tuples β that will produce the same set of tableaux. We accordingly group the bounding β into equivalence classes and identify the most efficient β in each class for the determinant computation. We recently showed that many other sets of objects that are indexed by n and λ are enumerated by the number of these efficient n-tuples. We called these counts "parabolic Catalan numbers". It is noted that the GL(n) Demazure characters (key polynomials) indexed by 312-avoiding permutations can also be expressed with these determinants. [ABSTRACT FROM AUTHOR]

A conjecture of Khang Tran [6] claims that for an arbitrary pair of polynomials A(z) and B(z), every zero of every polynomial in the sequence {Pn (z)}n=1∞ satisfying the three-term recurrence relation of length k Pn(z) + B(z)Pn-1(z)+ A(z)Pn-k (z) =0 with the standard initial conditions P0(z) = 1, P-1(z) = ... = P-k+1(z) = 0 which is not a zero of A(z) lies on the real (semi)-algebraic curve C ⊂ ℂ given by ... In this short note, we show that for the recurrence relation (generalizing the latter recurrence of Tran) given by Pn(z) + B(z)Pn-l(z) + A(z)Pn-k(z) = 0, with coprime k and l and the same standard initial conditions as above, every root of Pn(z) which is not a zero of A(z)B(z) belongs to the real algebraic curve Cl, k given by .... [ABSTRACT FROM AUTHOR]

Although the hammock networks were introduced more than sixty years ago, there is no general formula of the associated reliability polynomial. Using the full Hermite interpolation polynomial, we propose an approximation for the reliability polynomial of a hammock network of arbitrary size. In the second part of the paper, we provide combinatorial formulas for the first two non-zero coefficients of the reliability polynomial. [ABSTRACT FROM AUTHOR]

We use the tangent method to compute the arctic curve of the Twenty-Vertex (20V) model with particular domain wall boundary conditions for a wide set of integrable weights. To this end, we extend to the finite geometry of domain wall boundary conditions the standard connection between the bulk 20V and 6V models via the Kagome lattice ice model. This allows to express refined partition functions of the 20V model in terms of their 6V counterparts, leading to explicit parametric expressions for the various portions of its arctic curve. The latter displays a large variety of shapes depending on the weights and separates a central liquid phase from up to six different frozen phases. A number of numerical simulations are also presented, which highlight the arctic curve phenomenon and corroborate perfectly the analytic predictions of the tangent method. We finally compute the arctic curve of the Quarter Turn symmetric Holey Aztec Domino Tiling (QTHADT) model, a problem closely related to the 20V model and whose asymptotics may be analyzed via a similar tangent method approach. Again results for the QTHADT model are found to be in perfect agreement with our numerical simulations. [ABSTRACT FROM AUTHOR]

In this article we develop a vectorial kernel method—a powerful method which solves in a unified framework all the problems related to the enumeration of words generated by a pushdown automaton. We apply it for the enumeration of lattice paths that avoid a fixed word (a pattern), or for counting the occurrences of a given pattern. We unify results from numerous articles concerning patterns like peaks, valleys, humps, etc., in Dyck and Motzkin paths. This refines the study by Banderier and Flajolet from 2002 on enumeration and asymptotics of lattice paths: we extend here their results to pattern-avoiding walks/bridges/meanders/excursions. We show that the autocorrelation polynomial of this forbidden pattern, as introduced by Guibas and Odlyzko in 1981 in the context of rational languages, still plays a crucial role for our algebraic languages. En passant, our results give the enumeration of some classes of self-avoiding walks, and prove several conjectures from the On-Line Encyclopedia of Integer Sequences. Finally, we also give the trivariate generating function (length, final altitude, number of occurrences of the pattern p), and we prove that the number of occurrences is normally distributed and linear with respect to the length of the walk: this is what Flajolet and Sedgewick call an instance of Borges's theorem. [ABSTRACT FROM AUTHOR]

One of the most prominent problems in computational biology is to predict the natural conformation of a protein from its amino acid sequence. This paper focuses on the three-dimensional hydrophobic-polar (HP) lattice model of this problem. The modified elastic net (EN) algorithm is applied to solve this nonlinear programming hard problem. The lattice partition strategy and two local search methods (LS1 and LS2) are proposed to improve the performance of the modified EN algorithm. The computation and analysis of 12 HP standard benchmark instances are also involved in this paper. The results indicate that the hybrid of modified EN algorithm, lattice partition strategy, and local search methods has a greater tendency to form a globular state than genetic algorithm does. The results of noncompact model are more natural in comparison with that of compact model. [ABSTRACT FROM AUTHOR]

We introduce the use of Fourier analysis on lattices as an integral part of a lattice-based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two cryptographic constructions that are based on the worst-case hardness of the unique shortest vector problem. The main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results (O(n1.5) instead of O(n7)). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a family of collision resistant hash functions with an improved security guarantee in terms of the unique shortest vector problem. Surprisingly, both results are derived from one theorem that presents two indistinguishable distributions on the segment [0 1). It seems that this theorem can have further applications; as an example, we use it to solve an open problem in quantum computation related to the dihedral hidden subgroup problem. [ABSTRACT FROM AUTHOR]

This article analyzes and explains the observed temperature dependence of the forward dark current of lattice matched In[sub 0.53]Ga[sub 0.47]As on InP diodes as a function of voltage. The experimental results show, at high temperatures, the characteristic current-voltage (I–V) curve corresponding to leakage, recombination, and diffusion currents, but at low temperatures an additional region is seen at high fields. We show that the onset of this region commences with high injection into the lower-doped base region. The high injection is shown by using simulation software to substantially alter the minority carrier concentration profile in the base, emitter and consequently the quasi-Fermi levels (QFL) at the base/window and the window/cap heterojunctions. We show that this QFL splitting and the associated electron “pile-up” (accumulation) at the window/emitter heterojunction leads to the observed pseudo-n=2 region of the current-voltage curve. We confirm this phenomenon by investigating the I–V–T characteristics of diodes with an InGaAsP quaternary layer (E[sub g]=1 eV) inserted between the InP window (E[sub g]=1.35 eV) and the InGaAs emitter (E[sub g]=0.72 eV) where it serves to reduce the barrier to injected electrons, thereby reducing the “pile-up.” We show, in this case that the high injection occurs at a higher voltage and lower temperature than for the ternary device, thereby confirming the role of the “accumulation” in the change of the I–V characteristics from n=1 to pseudo-n=2 in the ternary latticed matched device. This is an important phenomenon for consideration in thermophotovoltaic applications. We, also show that the activation energy at medium and high voltages corresponds to the InP/InGaAs conduction band offset at the window/emitter heterointerface. © 2004 American Institute of Physics. [ABSTRACT FROM AUTHOR]

Using techniques from the theories of convex polytopes, lattice paths, and indirect influences on directed manifolds, we construct continuous analogues for the binomial coefficients and the Catalan numbers. Our approach for constructing these analogues can be applied to a wide variety of combinatorial sequences. As an application we develop a continuous analogue for the binomial distribution. [ABSTRACT FROM AUTHOR]

Irving and Rattan gave a formula for counting lattice paths dominated by a cyclically shifting piecewise linear boundary of varying slope. Their main result may be considered as a deep extension of well-known enumerative formulas concerning lattice paths from (0, 0) to (kn, n) lying under the line x = k y (e.g., the Dyck paths when k = 1 ). On the other hand, the classical Chung–Feller theorem tells us that the number of lattice paths from (0, 0) to (n, n) with exactly 2k steps above the line x = y is independent of k and is therefore the Catalan number 1 n + 1 2 n n . In this paper, we study the number of lattice path boundary pairs (P , a) with k flaws, where P is a lattice path from (0, 0) to (n, m), a is a weak m-part composition of n, and a flaw is a horizontal step of P above the boundary ∂ a . We prove bijectively, for a given a , that summing these numbers over all cyclic shifts of the boundary ∂ a is equal to n + m m - 1 . That is, we generalize the Irving–Rattan formula to a Chung–Feller-type theorem. We also give a refinement of this result by taking the number of double ascents of lattice paths into account. [ABSTRACT FROM AUTHOR]

We are applying a new approach to interpret the generalized version of order 8 mock theta functions V 0 (q) and V 1 (q) in terms of n -color partitions. In literature, we find the interpretations of these functions in terms of split n -color partitions and signed partitions. In addition, we are interpreting the generalized versions of two mock theta functions of order 6 and two of order 5 in terms of n -color partitions. A mock theta function of order 3 is interpreted in terms of (n + 2) -color partitions. We further extend our results using lattice paths. [ABSTRACT FROM AUTHOR]

The transfer distance (TD) was introduced in the classification framework and studied in the context of phylogenetic tree matching. Recently, Lemoine et al. (Nature 556(7702):452–456, 2018. 10.1038/s41586-018-0043-0) showed that TD can be a powerful tool to assess the branch support on large phylogenies, thus providing a relevant alternative to Felsenstein's bootstrap. This distance allows a reference branch β in a reference tree T to be compared to a branch b from another tree T (typically a bootstrap tree), both on the same set of n taxa. The TD between these branches is the number of taxa that must be transferred from one side of b to the other in order to obtain β . By taking the minimum TD from β to all branches in T we define the transfer index, denoted by ϕ (β , T) , measuring the degree of agreement of T with β . Let us consider a reference branch β having p tips on its light side and define the transfer support (TS) as 1 - ϕ (β , T) / (p - 1) . Lemoine et al. (2018) used computer simulations to show that the TS defined in this manner is close to 0 for random "bootstrap" trees. In this paper, we demonstrate that result mathematically: when T is randomly drawn, TS converges in probability to 0 when n tends to ∞ . Moreover, we fully characterize the distribution of ϕ (β , T) on caterpillar trees, indicating that the convergence is fast, and that even when n is small, moderate levels of branch support cannot appear by chance. [ABSTRACT FROM AUTHOR]

Inversion sequences are in natural bijection with permutations and have surprising connections with lecture hall polytopes and partitions. Recently, Martinez and Savage carried out the systematic study of inversion sequences avoiding triples of relations. They established many connections with known integer sequences and highlighted several interesting conjectures, some of which have already been solved. In this paper, we address the remaining enumeration conjectures posed by them, leaving only those related to the OEIS sequence A098746 open. [ABSTRACT FROM AUTHOR]

Abstract Borel's triangle is an array of integers closely related to the classical Catalan numbers. In this paper we study combinatorial statistics counted by Borel's triangle. We present various combinatorial interpretations of Borel's triangle in terms of lattice paths, binary trees, and pattern avoiding permutations and matchings, and derive a functional equation that is useful in analyzing the involved structures. [ABSTRACT FROM AUTHOR]

Presents a study that measured superconducting temperatures and magnetic fields, lattice parameters and chemical compositions for bulk layers of pure and alloyed niobium[sub3] tin which were made by the bronze process. Values of temperature of pure niobium[sub3] tin layers; Effect of small additions of titanium on the value of temperature; Experimental results.

Studies the variations in the lattice parameters of commercially available undoped and Silicon-doped Gallium Arsenide (GaAs) substrates using high resolution photoluminescence (PL) spectroscopy. Bound excitons of biaxially strained GaAs; Methodology of the study; Background about the GaAs grown on Si-doped substrates.

Deals with a study which observed a flux-line lattice in a single crystal of Bi[sub2.15]Sr[sub1.95]CaCu[sub2]O[sub8+x] using small-angle neutron scattering methods. Background to the study; Experimental procedures; Results and discussion.

Studies the initial growth stages of the lattice-mismatched GaAs/InAs system by coaxial impact collision ion scattering spectroscopy. Background to the study; Results and discussion; Conclusion.