Search

Abstract In this paper, we study the distribution of consecutive patterns in the set of 123-avoiding permutations and the set of 132-avoiding permutations, that is, in S n (123) and S n (132). We first study the distribution of consecutive pattern γ -matches in S n (123) and S n (132) for each length 3 consecutive pattern γ. Then we extend our methods to study the joint distributions of multiple consecutive patterns. Some more general cases are discussed in this paper as well. [ABSTRACT FROM AUTHOR]

The classical correlation inequality of Harris asserts that any two monotone increasing families on the discrete cube are nonnegatively correlated. In 1996, Talagrand [19] established a lower bound on the correlation in terms of how much the two families depend simultaneously on the same coordinates. Talagrand's method and results inspired a number of important works in combinatorics and probability theory. In this paper we present stronger correlation lower bounds that hold when the increasing families satisfy natural regularity or symmetry conditions. In addition, we present several new classes of examples for which Talagrand's bound is tight. A central tool in the paper is a simple lemma asserting that for monotone events noise decreases correlation. This lemma gives also a very simple derivation of the classical FKG inequality for product measures, and leads to a simplification of part of Talagrand's proof. [ABSTRACT FROM AUTHOR]

Inversive distance circle packing metric was introduced by P Bowers and K Stephenson [7] as a generalization of Thurston's circle packing metric [34] . They conjectured that the inversive distance circle packings are rigid. For nonnegative inversive distance, Guo [22] proved the infinitesimal rigidity and then Luo [27] proved the global rigidity. In this paper, based on an observation of Zhou [37] , we prove this conjecture for inversive distance in ( − 1 , + ∞ ) by variational principles. We also study the global rigidity of a combinatorial curvature introduced in [14,16,19] with respect to the inversive distance circle packing metrics where the inversive distance is in ( − 1 , + ∞ ) . [ABSTRACT FROM AUTHOR]

Given a linear equation L , a set A ⊆ [ n ] is L -free if A does not contain any ‘non-trivial’ solutions to L . In this paper we consider the following three general questions: (i) What is the size of the largest L -free subset of [ n ] ? (ii) How many L -free subsets of [ n ] are there? (iii) How many maximal L -free subsets of [ n ] are there? We completely resolve (i) in the case when L is the equation p x + q y = z for fixed p , q ∈ N where p ≥ 2 . Further, up to a multiplicative constant, we answer (ii) for a wide class of such equations L , thereby refining a special case of a result of Green (2005). We also give various bounds on the number of maximal L -free subsets of [ n ] for three-variable homogeneous linear equations L . For this, we make use of container and removal lemmas of Green (2005). [ABSTRACT FROM AUTHOR]

In this paper we consider a simple algebraic structure — sets with a single endofunction. We shall see that from the point of view of structural limits, even this simplest case is both interesting and difficult. Nevertheless we obtain the shape of limit objects in the full generality, and we prove the inverse theorem in the case of quantifier-free limits. [ABSTRACT FROM AUTHOR]

The generalised colouring numbers col r ( G ) and wcol r ( G ) were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have since then found important theoretical and algorithmic applications. In this paper, we dramatically improve upon the known upper bounds for generalised colouring numbers for graphs excluding a fixed minor, from the exponential bounds of Grohe et al. to a linear bound for the r -colouring number col r and a polynomial bound for the weak r -colouring number wcol r . In particular, we show that if G excludes K t as a minor, for some fixed t ≥ 4 , then col r ( G ) ≤ t − 1 2 ( 2 r + 1 ) and wcol r ( G ) ≤ r + t − 2 t − 2 ( t − 3 ) ( 2 r + 1 ) ∈ O ( r t − 1 ) . In the case of graphs G of bounded genus g , we improve the bounds to col r ( G ) ≤ ( 2 g + 3 ) ( 2 r + 1 ) (and even col r ( G ) ≤ 5 r + 1 if g = 0 , i.e. if G is planar) and wcol r ( G ) ≤ ( 2 g + r + 2 2 ) ( 2 r + 1 ) . [ABSTRACT FROM AUTHOR]

The Ish arrangement was introduced by Armstrong to give a new interpretation of the q , t -Catalan numbers of Garsia and Haiman. Armstrong and Rhoades showed that there are some striking similarities between the Shi arrangement and the Ish arrangement and posed some problems. One of them is whether the Ish arrangement is a free arrangement or not. In this paper, we verify that the Ish arrangement is supersolvable and hence free. Moreover, we give a necessary and sufficient condition for the deleted Ish arrangement to be free. [ABSTRACT FROM AUTHOR]

This paper surveys some combinatorial aspects of Smith normal form, and more generally, diagonal form. The discussion includes general algebraic properties and interpretations of Smith normal form, critical groups of graphs, and Smith normal form of random integer matrices. We then give some examples of Smith normal form and diagonal form arising from (1) symmetric functions, (2) a result of Carlitz, Roselle, and Scoville, and (3) the Varchenko matrix of a hyperplane arrangement. [ABSTRACT FROM AUTHOR]