搜索结果：Avoiding

We study a variant of the color-avoiding percolation model introduced by Krause et al., namely we investigate the color-avoiding bond percolation setup on (not necessarily properly) edge-colored Erdős-Rényi random graphs. We say that two vertices are color-avoiding connected in an edge-colored graph if after the removal of the edges of any color, they are in the same component in the remaining graph. The color-avoiding connected components of an edge-colored graph are maximal sets of vertices such that any two of them are color-avoiding connected. We consider the fraction of vertices contained in color-avoiding connected components of a given size as well as the fraction of vertices contained in the giant color-avoiding connected component. Under some mild assumptions on the color-densities, we prove that these quantities converge and the limits can be expressed in terms of probabilities associated to edge-colored branching process trees. We provide explicit formulas for the limit of the normalized size of the giant color-avoiding component, and in the two-colored case we also provide explicit formulas for the limit of the fraction of vertices contained in color-avoiding connected

Fix a strong rectangulation pattern $P$ of size $L$. We show that the growth constant of the class of strong rectangulations avoiding $P$ is strictly smaller than $Λ=27/2$, the growth constant for all strong rectangulations. More precisely, forbidding any such $P$ yields a pattern-uniform exponential drop of at least $Λ- 1/Λ^{3L-1}$. Consequently, the proportion of $P$-avoiding rectangulations among all rectangulations tends to zero as $n\to \infty$. This is the first result on the uniform drop of exponential growth for pattern-avoiding rectangulations. The proof utilizes the standard correspondence with leftmost history quadrant walks, along with a pattern-insertion scheme that controls the radius of convergence of the associated generating functions, thereby establishing the first uniform exponential upper bound for rectangulation classes defined by geometric avoidance.

In the 1960s Moser asked how dense a subset of $\mathbb{R}^d$ can be if no pairs of points in the subset are exactly distance 1 apart. There has been a long line of work showing upper bounds on this density. One curious feature of dense unit distance avoiding sets is that they appear to be ``clumpy,'' i.e. forbidding unit distances comes hand in hand with having more than the expected number distance $\approx 2$ pairs. In this work we rigorously establish this phenomenon in $\mathbb{R}^2$. We show that dense unit distance avoiding sets have over-represented distance $\approx 2$ pairs, and that this clustering extends to typical unit distance avoiding sets. To do so, we build off of the linear programming approach used previously to prove upper bounds on the density of unit distance avoiding sets.

We initiate an in-depth study of pattern avoidance on modified ascent sequences. Our main technique consists in using Stanley's standardization to obtain a transport theorem between primitive modified ascent sequences and permutations avoiding a bivincular pattern of length three. We enumerate some patterns via bijections with other combinatorial structures such as Fishburn permutations, lattice paths and set partitions. We settle the last remaining case of a conjecture by Duncan and Steingrímsson by proving that modified ascent sequences avoiding 2321 are counted by the Bell numbers.

Permutations whose prefixes contain at least as many ascents as descents are called ballot permutations. Lin, Wang, and Zhao have previously enumerated ballot permutations avoiding small patterns and have proposed the problem of enumerating ballot permutations avoiding a pair of permutations of length $3$. We completely enumerate ballot permutations avoiding two patterns of length $3$ and we relate these avoidance classes with their respective recurrence relations and formulas, which leads to an interesting bijection between ballot permutations avoiding $132$ and $312$ with left factors of Dyck paths. In addition, we also conclude the Wilf-classification of ballot permutations avoiding sets of two patterns of length $3$, and we then extend our results to completely enumerate ballot permutations avoiding three patterns of length $3$.

Inversion sequences are integer sequences $(σ_1, \dots, σ_n)$ such that $0 \leqslant σ_i < i$ for all $1 \leqslant i \leqslant n$. The study of pattern-avoiding inversion sequences began in two independent articles by Mansour-Shattuck and Corteel-Martinez-Savage-Weselcouch in 2015 and 2016. These two initial articles solved the enumeration of inversion sequences avoiding a single pattern for every pattern of length 3 except the patterns 010 and 100. The case 100 was recently solved by Mansour and Yildirim. We solve the final case by making use of a decomposition of inversion sequences avoiding the pattern 010. Our decomposition needs to take into account the maximal value, and the number of distinct values occurring in the inversion sequence. We then expand our method to solve the enumeration of inversion sequences avoiding the pairs of patterns $\{010, 000\}, \{010, 110\}, \{010, 120\}$, and the Wilf-equivalent pairs $\{010, 201\} \sim \{010, 210\}$. For each family of pattern-avoiding inversion sequences considered, its enumeration requires the enumeration of some family of constrained words avoiding the same patterns, a question which we also solve.

We study groups generated by sets of pattern avoiding permutations. In the first part of the paper we prove some general results concerning the structure of such groups. In the second part we carry out a case-by-case analysis of groups generated by permutations avoiding few short patterns.

In 2019, Bóna and Smith introduced the notion of strong pattern avoidance, saying that a permutation $π$ strongly avoids a pattern $σ$ if $π$ and $π^2$ both avoid $σ$. Recently, Archer and Geary generalized the idea of strong pattern avoidance to chain avoidance, in which a permutation $π$ avoids a chain of patterns $(τ^{(1)}:τ^{(2)}:\cdots:τ^{(k)})$ if the $i$-th power of the permutation avoids the pattern $τ^{(i)}$ for $1\leq i\leq k$. In this paper, we give explicit formulae for the number of sets of permutations avoiding certain chains of patterns. Our results give affirmative answers to two conjectures proposed by Archer and Geary.

Two Eulerian circuits, both starting and ending at the same vertex, are avoiding if at every other point of the circuits they are at least distance 2 apart. An Eulerian graph which admits two such avoiding circuits starting from any vertex is said to be doubly Eulerian. The motivation for this definition is that the extremal Eulerian graphs, i.e. the complete graphs on an odd number of vertices and the cycles, are not doubly Eulerian. We prove results about doubly Eulerian graphs and identify those that are the `densest' and `sparsest' in terms of the number of edges.

Recently, Chen et al. derived the generating function for partitions avoiding right nestings and posed the problem of finding the generating function for partitions avoiding right crossings. In this paper, we derive the generating function for partitions avoiding right crossings via an intermediate structure of partial matchings avoiding 2-right crossings and right nestings. We show that there is a bijection between partial matchings avoiding 2-right crossing and right nestings and partitions avoiding right crossings.

A word $w=w_1w_2\cdots w_n$ is alternating if either $w_1<w_2>w_3<w_4>\cdots$ (when the word is up-down) or $w_1>w_2<w_3>w_4<\cdots$ (when the word is down-up). The study of alternating words avoiding classical permutation patterns was initiated by the authors in~\cite{GKZ}, where, in particular, it was shown that 123-avoiding up-down words of even length are counted by the Narayana numbers. However, not much was understood on the structure of 123-avoiding up-down words. In this paper, we fill in this gap by introducing the notion of a cut-pair that allows us to subdivide the set of words in question into equivalence classes. We provide a combinatorial argument to show that the number of equivalence classes is given by the Catalan numbers, which induces an alternative (combinatorial) proof of the corresponding result in~\cite{GKZ}. Further, we extend the enumerative results in~\cite{GKZ} to the case of alternating words avoiding a vincular pattern of length 3. We show that it is sufficient to enumerate up-down words of even length avoiding the consecutive pattern $\underline{132}$ and up-down words of odd length avoiding the consecutive pattern $\underline{3

We study the problem of counting alternating permutations avoiding collections of permutation patterns including 132. We construct a bijection between the set S_n(132) of 132-avoiding permutations and the set A_{2n + 1}(132) of alternating, 132-avoiding permutations. For every set p_1, ..., p_k of patterns and certain related patterns q_1, ..., q_k, our bijection restricts to a bijection between S_n(132, p_1, ..., p_k), the set of permutations avoiding 132 and the p_i, and A_{2n + 1}(132, q_1, ..., q_k), the set of alternating permutations avoiding 132 and the q_i. This reduces the enumeration of the latter set to that of the former.

A permutation of the integers avoiding monotone arithmetic progressions of length $6$ was constructed in (Geneson, 2018). We improve on this by constructing a permutation of the integers avoiding monotone arithmetic progressions of length $5$. We also construct permutations of the integers and the positive integers that improve on previous upper and lower density results. In (Davis et al. 1977) they constructed a doubly infinite permutation of the positive integers that avoids monotone arithmetic progressions of length $4$. We construct a doubly infinite permutation of the integers avoiding monotone arithmetic progressions of length $5$. A permutation of the positive integers that avoided monotone arithmetic progressions of length $4$ with odd common difference was constructed in (LeSaulnier and Vijay, 2011). We generalise this result and show that for each $k\geq 1$, there exists a permutation of the positive integers that avoids monotone arithmetic progressions of length $4$ with common difference not divisible by $2^k$. In addition, we specify the structure of permutations of $[1,n]$ that avoid length $3$ monotone arithmetic progressions mod $n$ as defined in (Davis et al. 1977)

How many matchings on the vertex set V={1,2,...,2n} avoid a given configuration of three edges? Chen, Deng and Du have shown that the number of matchings that avoid three nesting edges is equal to the number of matchings avoiding three pairwise crossing edges. In this paper, we consider other forbidden configurations of size three. We present a bijection between matchings avoiding three crossing edges and matchings avoiding an edge nested below two crossing edges. This bijection uses non-crossing pairs of Dyck paths of length 2n as an intermediate step. Apart from that, we give a bijection that maps matchings avoiding two nested edges crossed by a third edge onto the matchings avoiding all configurations from an infinite family, which contains the configuration consisting of three crossing edges. We use this bijection to show that for matchings of size n>3, it is easier to avoid three crossing edges than to avoid two nested edges crossed by a third edge. In this updated version of this paper, we add new references to papers that have obtained analogous results in a different context.

We prove the Castelnuovo--Mumford regularity of 321-avoiding Kazhdan--Lusztig varieties can be computed combinatorially in terms of $K$-theoretic skew excited Young diagrams. We present an algorithm which gives a lower bound for this regularity and describe a setting in which this algorithm provides precise regularity computations. This algorithm specializes to compute the regularity of all two-sided mixed ladder determinantal varieties.

We obtain the generating functions for partial matchings avoiding neighbor alignments and for partial matchings avoiding neighbor alignments and left nestings. We show that there is a bijection between partial matchings avoiding three neighbor patterns (neighbor alignments, left nestings and right nestings) and set partitions avoiding right nestings via an intermediate structure of integer compositions. Such integer compositions are known to be in one-to-one correspondence with self-modified ascent sequences or $3\bar{1}52\bar{4}$-avoiding permutations, as shown by Bousquet-Mélou, Claesson, Dukes and Kitaev.

We say that an element $x$ of a topological space $X$ avoids measures if for every Borel measure $μ$ on $X$ if $μ(\{x\})=0$, then there is an open $U i x$ such that $μ(U)=0$. The negation of this property can viewed as a local version of the property of supporting a strictly positive measure. We study points avoiding measures in the general setting as well as in the context of $ω^\ast$, the remainder of Stone-Čech compactification of $ω$.

We construct a sequence of finite automata that accept subclasses of the class of 4231-avoiding permutations. We thereby show that the Wilf-Stanley limit for the class of 4231-avoiding permutations is bounded below by 9.35. This bound shows that this class has the largest such limit among all classes of permutations avoiding a single permutation of length 4 and refutes the conjecture that the Wilf-Stanley limit of a class of permutations avoiding a single permutation of length k cannot exceed (k-1)^2.