Spelling suggestions: "subject:"permutation patterns"" "subject:"ermutation patterns""
1 |
Some New Probability Distributions Based on Random Extrema and Permutation PatternsHao, Jie 01 May 2014 (has links)
In this paper, we study a new family of random variables, that arise as the distribution of extrema of a random number N of independent and identically distributed random variables X1,X2, ..., XN, where each Xi has a common continuous distribution with support on [0,1]. The general scheme is first outlined, and SUG and CSUG models are introduced in detail where Xi is distributed as U[0,1]. Some features of the proposed distributions can be studied via its mean, variance, moments and moment-generating function. Moreover, we make some other choices for the continuous random variables such as Arcsine, Topp-Leone, and N is chosen to be Geometric or Zipf. Wherever appropriate, we estimate of the parameter in the one-parameter family in question and test the hypotheses about the parameter. In the last section, two permutation distributions are introduced and studied.
|
2 |
New combinatorial techniques for nonlinear ordersMarcus, Adam Wade 26 June 2008 (has links)
This thesis focuses on the use of extremal techniques in analyzing problems that historically have been associated with other areas of discrete mathematics. We establish new techniques for analyzing combinatorial problems with two different types of nonlinear orders, and then use them to solve important previously-open problems in mathematics. In addition, we use entropy techniques to establish a variety of bounds in the theory of sumsets.
In the second chapter, we examine a problem of Furedi and Hajnal regarding forbidden patterns in (0,1)-matrices. We introduce a new technique that gives an asymptotically tight bound on the number of 1-entries that a (0,1)-matrix can contain while avoiding a fixed permutation matrix. We use this result to solve the Stanley-Wilf conjecture, a well-studied open problem in enumerative combinatorics. We then generalize the technique to give results on d-dimensional matrices.
In the third chapter, we examine a problem of Pinchasi and Radoicic on cyclically order sets. To do so, we prove an upper bound on the sizes of such sets, given that their orders have the intersection reverse property. We then use this to give an upper bound on the number of edges that a graph can have, assuming that the graph can be drawn so that no cycle of length four has intersecting edges. This improves the previously best known bound and (up to a log-factor) matches the best known lower bound. This result implies improved bounds on a number of well-studied problems in geometric combinatorics, most notably the complexity of pseudo-circle arrangements.
In the final chapter, we use entropy techniques to establish new bounds in the theory of sumsets. We show that such sets behave fractionally submultiplicatively, which in turn provides new Plunecke-type inequalities of the form first introduced by Gyarmati, Matolcsi, and Ruzsa.
|
3 |
Pattern posets: enumerative, algebraic and algorithmic issuesCervetti, Matteo 22 March 2021 (has links)
The study of patterns in combinatorial structures has grown up in the past few decades to one of the most active trends of research in combinatorics. Historically, the study of permutations which are constrained by not containing subsequences ordered in various prescribed ways has been motivated by the problem of sorting permutations with certain devices. However, the richness of this notion
became especially evident from its plentiful appearances in several very different disciplines, such as pure mathematics, mathematical physics, computer science,biology, and many others. In the last decades, similar notions of patterns have been considered on discrete structures other than permutations, such as integer sequences, lattice paths, graphs, matchings and set partitions. In the first part of
this talk I will introduce the general framework of pattern posets and some classical problems about patterns. In the second part of this talk I will present some enumerative results obtained in my PhD thesis about patterns in permutations, lattice paths and matchings. In particular I will describe a generating tree with a single label for permutations avoiding the vincular pattern 1 - 32 - 4, a finite automata approach to enumerate lattice excursions avoiding a single pattern and some results about matchings avoiding juxtapositions and liftings of patterns.
|
Page generated in 0.1117 seconds