In this paper, we study corners in tree‐like and permutation tableaux. Tree‐like tableaux are in bijection with other combinatorial structures, including permutation tableaux, and have a connection to the partially asymmetric simple exclusion process (PASEP), an important model of an interacting particles system. In particular, in the context of tree‐like tableaux, a corner corresponds to a node occupied by a particle that could jump to the right while inner corners indicate a particle with an empty node to its left. Thus, the total number of corners represents the number of nodes at which PASEP can move, that is, the total current activity of the system. As the number of inner corners and regular corners is connected, we limit our discussion to just regular corners and show that asymptotically, the number of corners in a tableau of length
 NSFPAR ID:
 10260111
 Publisher / Repository:
 Wiley Blackwell (John Wiley & Sons)
 Date Published:
 Journal Name:
 Random Structures & Algorithms
 Volume:
 57
 Issue:
 4
 ISSN:
 10429832
 Page Range / eLocation ID:
 p. 12481271
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Waves of misery is a phenomenon where spikes of many node splits occur over short periods of time in tree indexes. Waves of misery negatively affect the performance of tree indexes in insertionheavy workloads. Waves of misery have been first observed in the context of the Btree, where these waves cause unpredictable index performance. In particular, the performance of search and indexupdate operations deteriorate when a wave of misery takes place, but is more predictable between the waves. This paper investigates the presence or lack of waves of misery in several Rtree variants, and studies the extent of which these waves impact the performance of each variant. Interestingly, although having poorer query performance, the Linear and Quadratic Rtrees are found to be more resilient to waves of misery than both the Hilbert and R*trees. This paper presents several techniques to reduce the impact in performance of the waves of misery for the Hilbert and R*trees. One way to eliminate waves of misery is to force node splits to take place at regular times before nodes become full to achieve deterministic performance. The other way is that upon splitting a node, do not split it evenly but rather at different node utilization factors. This allows leaf nodes not to fill at the same pace. We study the impact of two new techniques to mitigate waves of misery after the tree index has been constructed, namely Regular Elective Splits (RES, for short) and Unequal Random Splits (URS, for short). Our experimental investigation highlights the tradeoffs in performance of the introduced techniques and the pros and cons of each technique. 
The motion of a freely rotating prolate spheroid in a simple shear flow of a dilute polymeric solution is examined in the limit of large particle aspect ratio,
. A regular perturbation expansion in the polymer concentration,$\kappa$ , a generalized reciprocal theorem, and slender body theory to represent the velocity field of a Newtonian fluid around the spheroid are used to obtain the$c$ correction to the particle's orientational dynamics. The resulting dynamical system predicts a range of orientational behaviours qualitatively dependent upon$O(c)$ ($c\, De$ is the imposed shear rate times the polymer relaxation time) and$De$ and quantitatively on$\kappa$ . At a small but finite$c$ , the particle spirals towards a limit cycle near the vorticity axis for all initial conditions. Upon increasing$c\, De$ , the limit cycle becomes smaller. Thus, ultimately the particle undergoes a periodic motion around and at a small angle from the vorticity axis. At moderate$\kappa$ , a particle starting near the flow–gradient plane departs it monotonically instead of spirally, as this plane (a limit cycle at smaller$c\, De$ ) obtains a saddle and an unstable node. The former is close to the flow direction. Upon further increasing$c\, De$ , the saddle node changes to a stable node. Therefore, depending upon the initial condition, a particle may either approach a periodic orbit near the vorticity axis or obtain a stable orientation near the flow direction. Upon further increasing$c\, De$ , the limit cycle near the vorticity axis vanishes, and the particle aligns with the flow direction for all starting orientations.$c\, De$ 
Consider a system of homogeneous interacting diffusive particles labeled by the nodes of a unimodular Galton–Watson tree, where the state of each node evolves infinitesi mally like a ddimensional diffusion whose drift coefficient depends on (the histories of) its own state and the states of neighboring nodes, and whose diffusion coefficient depends only on (the history of) its own state. Under suitable regularity assumptions on the coefficients, an autonomous characterization is obtained for the marginal dis tribution of the dynamics of the neighborhood of a typical node in terms of a certain local equation, which is a new kind of stochastic differential equation that is nonlinear in the sense of McKean. This equation describes a finitedimensional nonMarkovian stochastic process whose infinitesimal evolution at any time depends not only on the structure and current state of the neighborhood, but also on the conditional law of the current state given the past of the states of neighborhing nodes until that time. Such marginal distributions are of interest because they arise as weak limits of both marginal distributions and empirical measures of interacting diffusions on many sequences of sparse random graphs, including the configuration model and Erdös–Rényi graphs whose average degrees converge to a finite nonzero limit. The results obtained complement classical results in the meanfield regime, which characterize the limiting dynamics of homogeneous interacting diffusions on complete graphs, as the num ber of nodes goes to infinity, in terms of a corresponding nonlinear Markov process. However, in the sparse graph setting, the topology of the graph strongly influences the dynamics, and the analysis requires a completely different approach. The proofs of existence and uniqueness of the local equation rely on delicate new conditional independence and symmetry properties of particle trajectories on unimodular Galton– Watson trees, as well as judicious use of changes of measure.more » « less

Abstract Consider a lattice of n sites arranged around a ring, with the $n$ sites occupied by particles of weights $\{1,2,\ldots ,n\}$; the possible arrangements of particles in sites thus correspond to the $n!$ permutations in $S_n$. The inhomogeneous totally asymmetric simple exclusion process (or TASEP) is a Markov chain on $S_n$, in which two adjacent particles of weights $i<j$ swap places at rate $x_i  y_{n+1j}$ if the particle of weight $j$ is to the right of the particle of weight $i$. (Otherwise, nothing happens.) When $y_i=0$ for all $i$, the stationary distribution was conjecturally linked to Schubert polynomials [18], and explicit formulas for steady state probabilities were subsequently given in terms of multiline queues [4, 5]. In the case of general $y_i$, Cantini [7] showed that $n$ of the $n!$ states have probabilities proportional to double Schubert polynomials. In this paper, we introduce the class of evilavoiding permutations, which are the permutations avoiding the patterns $2413, 4132, 4213,$ and $3214$. We show that there are $\frac {(2+\sqrt {2})^{n1}+(2\sqrt {2})^{n1}}{2}$ evilavoiding permutations in $S_n$, and for each evilavoiding permutation $w$, we give an explicit formula for the steady state probability $\psi _w$ as a product of double Schubert polynomials. (Conjecturally, all other probabilities are proportional to a positive sum of at least two Schubert polynomials.) When $y_i=0$ for all $i$, we give multiline queue formulas for the $\textbf {z}$deformed steady state probabilities and use this to prove the monomial factor conjecture from [18]. Finally, we show that the Schubert polynomials arising in our formulas are flagged Schur functions, and we give a bijection in this case between multiline queues and semistandard Young tableaux.

The notion of comparison between system runs is fundamental in formal verification. This concept is implicitly present in the verification of qualitative systems, and is more pronounced in the verification of quantitative systems. In this work, we identify a novel mode of comparison in quantitative systems: the online comparison of the aggregate values of two sequences of quantitative weights. This notion is embodied by comparator automata (comparators, in short), a new class of automata that read two infinite sequences of weights synchronously and relate their aggregate values. Weshowthat aggregate functions that can be represented with B¨uchi automaton result in comparators that are finitestate and accept by the B¨uchi condition as well. Such ωregular comparators further lead to generic algorithms for a number of wellstudied problems, including the quantitative inclusion and winning strategies in quantitative graph games with incomplete information, as well as related nondecision problems, such as obtaining a f inite representation of all counterexamples in the quantitative inclusion problem. We study comparators for two aggregate functions: discountedsum and limitaverage. We prove that the discountedsum comparator is ωregular iff the discountfactor is an integer. Not every aggregate function, however, has an ωregular comparator. Specifically, we show that the language of sequencepairs for which limitaverage aggregates exist is neither ωregular nor ωcontextfree. Given this result, we introduce the notion of prefixaverage as a relaxation of limitaverage aggregation, and show that it admits ωcontextfree comparators i.e. comparator automata expressed by B¨uchi pushdown automata.more » « less