To see the other types of publications on this topic, follow the link: Permutation.
Dissertations / Theses on the topic 'Permutation'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Permutation.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Cox, Charles. "Infinite permutation groups containing all finitary permutations." Thesis, University of Southampton, 2016. https://eprints.soton.ac.uk/401538/.
Full textAbstract:
Groups naturally occu as the symmetries of an object. This is why they appear in so many different areas of mathematics. For example we find class grops in number theory, fundamental groups in topology, and amenable groups in analysis. In this thesis we will use techniques and approaches from various fields in order to study groups. This is a 'three paper' thesis, meaning that the main body of the document is made up of three papers. The first two of these look at permutation groups which contain all permutations with finite support, the first focussing on decision problems and the second on the R? property (which involves counting the number of twisting conjugacy classes in a group). The third works with wreath products C}Z where C is cyclic, and looks to dermine the probability of choosing two elements in a group which commute (known as the degree of commutativity, a topic which has been studied for finite groups intensely but at the time of writing this thesis has only two papers involving infinite groups, one of which is in this thesis).
2
Neou, Both Emerite. "Permutation pattern matching." Thesis, Paris Est, 2017. http://www.theses.fr/2017PESC1239/document.
Full textAbstract:
Cette thèse s'intéresse au problème de la recherche de motif dans les permutations, qui a pour objectif de savoir si un motif apparaît dans un texte, en prenant en compte que le motif et le texte sont des permutations. C'est-à-dire s'il existe des éléments du texte tel que ces éléments sont triés de la même manière et apparaissent dans le même ordre que les éléments du motif. Ce problème est NP complet. Cette thèse expose des cas particuliers de ce problème qui sont solvable en temps polynomial.Pour cela nous étudions le problème en donnant des contraintes sur le texte et/ou le motif. En particulier, le cas où le texte et/ou le motif sont des permutations qui ne contiennent pas les motifs 2413 et 3142 (appelé permutation séparable) et le cas où le texte et/ou le motif sont des permutations qui ne contiennent pas les motifs 213 et 231 sont considérés. Des problèmes dérivés de la recherche de motif et le problème de la recherche de motif bivinculaire sont aussi étudiésThis thesis focuses on permutation pattern matching problem, which askswhether a pattern occurs in a text where both the pattern and text are permutations.In other words, we seek to determine whether there exist elements ofthe text such that they are sorted and appear in the same order as the elementsof the pattern. The problem is NP-complete. This thesis examines particularcases of the problem that are polynomial-time solvable.For this purpose, we study the problem by giving constraints on the permutationstext and/or pattern. In particular, the cases in which the text and/orpattern are permutations in which the patterns 2413 and 3142 do not occur(also known as separable permutations) and in which the text and/or patternare permutations in which the patterns 213 and 231 do not occur (also known aswedge permutations) are also considered. Some problems related to the patternmatching and the permutation pattern matching with bivincular pattern arealso studied
3
Cernes, John. "Ends of permutation groups and some centrality properties of permutational wreath products." Thesis, University of Oxford, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.339282.
Full text
4
Hyatt, Matthew. "Quasisymmetric Functions and Permutation Statistics for Coxeter Groups and Wreath Product Groups." Scholarly Repository, 2011. http://scholarlyrepository.miami.edu/oa_dissertations/609.
Full textAbstract:
Eulerian quasisymmetric functions were introduced by Shareshian and Wachs in order to obtain a q-analog of Euler's exponential generating function formula for the Eulerian polynomials. They are defined via the symmetric group, and applying the stable and nonstable principal specializations yields formulas for joint distributions of permutation statistics. We consider the wreath product of the cyclic group with the symmetric group, also known as the group of colored permutations. We use this group to introduce colored Eulerian quasisymmetric functions, which are a generalization of Eulerian quasisymmetric functions. We derive a formula for the generating function of these colored Eulerian quasisymmetric functions, which reduces to a formula of Shareshian and Wachs for the Eulerian quasisymmetric functions. We show that applying the stable and nonstable principal specializations yields formulas for joint distributions of colored permutation statistics. The family of colored permutation groups includes the family of symmetric groups and the family of hyperoctahedral groups, also called the type A Coxeter groups and type B Coxeter groups, respectively. By specializing our formulas to these cases, they reduce to the Shareshian-Wachs q-analog of Euler's formula, formulas of Foata and Han, and a new generalization of a formula of Chow and Gessel.
5
Urfer, Jean-Marie. "Modules d'endo-p-permutation /." [S.l.] : [s.n.], 2006. http://library.epfl.ch/theses/?nr=3544.
Full text
6
Kuzucuoglu, M. "Barely transitive permutation groups." Thesis, University of Manchester, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.233097.
Full text
7
BREGA, LEONARDO SANTOS. "COMPRESSION USING PERMUTATION CODES." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2003. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=4379@1.
Full textAbstract:
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOREm um sistema de comunicações, procura-se representar a informação gerada de forma eficiente, de modo que a redundância da informação seja reduzida ou idealmente eliminada, com o propósito de armazenamento e/ou transmissão da mesma. Este interesse justifica portanto, o estudo e desenvolvimento de técnicas de compressão que vem sendo realizado ao longo dos anos. Este trabalho de pesquisa investiga o uso de códigos de permutação para codificação de fontes segundo um critério de fidelidade, mais especificamente de fontes sem memória, caracterizadas por uma distribuição uniforme e critério de distorção de erro médio quadrático. Examina-se os códigos de permutação sob a ótica de fontes compostas e a partir desta perspectiva, apresenta-se um esquema de compressão com duplo estágio. Realiza-se então uma análise desse esquema de codificação. Faz-se também uma extensão L- dimensional (L > 1) do esquema de permutação apresentado na literatura. Os resultados obtidos comprovam um melhor desempenho da versão em duas dimensões, quando comparada ao caso unidimensional, sendo esta a principal contribuição do presente trabalho. A partir desses resultados, busca-se a aplicação de um esquema que utiliza códigos de permutação para a compressão de imagens.
In communications systems the information must be represented in an efficient form, in such a way that the redundancy of the information is either reduced or ideally eliminated, with the intention of storage or transmission of the same one. This interest justifies the study and development of compression techniques that have been realized through the years. This research investigates the use of permutation codes for source encoding with a fidelity criterion, more specifically of memoryless uniform sources with mean square error fidelity criterion. We examine the permutation codes under the view of composed sources and from this perspective, a project of double stage source encoder is presented. An analysis of this project of codification is realized then. A L-dimensional extension (L > 1) of permutation codes from previous research is also introduced. The results prove a better performance of the version in two dimensions, when compared with the unidimensional case and this is the main contribution of the present study. From these results, we investigate an application for permutation codes in image compression.
8
Diene, Adama. "Structure of Permutation Polynomials." University of Cincinnati / OhioLINK, 2005. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1123788311.
Full text
9
Lajeunesse, Lisa (Lisa Marie) Carleton University Dissertation Mathematics and Statistics. "Models and permutation groups." Ottawa, 1996.
Find full text
10
Fawcett, Joanna Bethia. "Bases of primitive permutation groups." Thesis, University of Cambridge, 2013. https://www.repository.cam.ac.uk/handle/1810/252304.
Full text
11
Campbell, Peter Steven. "Permutation modules and representation theory." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp01/MQ60107.pdf.
Full text
12
Beane, Robbie Allen. "Inverse limits of permutation maps." Diss., Rolla, Mo. : Missouri University of Science and Technology, 2008. http://scholarsmine.mst.edu/thesis/pdf/Beane_09007dcc804f93c9.pdf.
Full textAbstract:
Thesis (Ph. D.)--Missouri University of Science and Technology, 2008.Vita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed May 9, 2008) Includes bibliographical references (p. 71-73).
13
Zmiaikou, David. "Origamis et groupes de permutation." Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00648120.
Full textAbstract:
Un origami est un revêtement du tore T2, éventuellement ramifié au-dessus de l'origine.Cet objet a été introduit par William P. Thurston et William A. Veech dans les années 1970.Un origami peut être vu comme un ensemble fini de copies du carreau unitaire qui sont collées par translations. Ainsi, un origami est un cas particulier d'une surface de translation,un élément de l'espace des modules de surfaces de Riemann munies d'une 1-forme holomorphe.Un origami O avec n carreaux correspond à une paire de permutations (σ, τ ) Є 2 Sn X Sn définie à conjugaison près. Le groupe Mon(O) engendré par une telle paire s'appelle le groupe de monodromie de O. On dit qu'un origami est primitif si son groupe de monodromie est un groupe de permutation primitif. Il y a une action naturelle du groupeGL2(Z) sur les origamis, le stabilisateur de O pour cette action est le groupe de Veechdésigné par GL(O). Le groupe de monodromie est un invariant des GL2(Z)-orbites.Dans le chapitre 3 de la thèse, nous montrons que le groupe de monodromie de tout origami primitif à n carreaux dans la strate H(2k) est An ou Sn si n ≥ 3k + 2, et noustrouvons la borne exacte quand 2k + 1 est premier. La même proposition est vraie pourla strate H(1; 1) si n =/= 6. Dans le chapitre 4, nous considérons les origamis réguliers,i.e. ceux pour lesquels le nombre de carreaux est égal à l'ordre du groupe de monodromie.Nous construisons de nouvelles familles d'origamis intéressantes et cherchons leurs strates et groupes de Veech. Nous estimons également le nombre de GL2(Z)-orbites et strates distinctes des origamis réguliers ayant un groupe de monodromie donné. Afin de trouver une borne inférieure pour les origamis alternés, nous prouvons que chaque permutation dans An quifixe peu de points est le commutateur d'une paire engendrant An. Dans le chapitre 6, nous étudions une propriété de sous-groupes de PSL2(Z) qui est liée à la propriété d'être le groupe de Veech d'un origami.
14
Spiga, Pablo. "P elements in permutation groups." Thesis, Queen Mary, University of London, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.413152.
Full text
15
McNab, C. A. "Some problems in permutation groups." Thesis, University of Oxford, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.382633.
Full text
16
Astles, David Christopher. "Permutation groups acting on subsets." Thesis, University of East Anglia, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.280040.
Full text
17
Chen, Cheng S. M. Massachusetts Institute of Technology. "Security of substitution-permutation network." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/101582.
Full textAbstract:
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 43-44).
In this thesis, we study the security of a block cipher design called substitution-permutation network (SPN). We prove that when S-box is chosen uniformly at random as a permutation, the resulting SPN is a strong pseudorandom permutation even against an adversary having oracle access to that S-box. We then examine some special cases of SPN for a fixed S-box and prove two special cases of SPN inspired by AES are 2-wise independent.
by Cheng Chen.
S.M.
18
Nguyen, Ha Quy. "Generalizations of permutation source codes." Thesis, Massachusetts Institute of Technology, 2009. http://hdl.handle.net/1721.1/54652.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.Cataloged from PDF version of thesis.
Includes bibliographical references (p. 87-90).
Permutation source codes are a class of structured vector quantizers with a computationally- simple encoding procedure. In this thesis, we provide two extensions that preserve the computational simplicity but yield improved operational rate-distortion performance. In the first approach, the new class of vector quantizers has a codebook comprising several permutation codes as subcodes. Methods for designing good code parameters are given. One method depends on optimizing the rate allocation in a shape-gain vector quantizer with gain-dependent wrapped spherical shape codebook. In the second approach, we introduce frame permutation quantization (FPQ), a new vector quantization technique using finite frames. In FPQ, a vector is encoded using a permutation source code to quantize its frame expansion. This means that the encoding is a partial ordering of the frame expansion coefficients. Compared to ordinary permutation source coding, FPQ produces a greater number of possible quantization rates and a higher maximum rate. Various representations for the partitions induced by FPQ are presented and reconstruction algorithms based on linear programming and quadratic programming are derived. Reconstruction using the canonical dual frame is also studied, and several results relate properties of the analysis frame to whether linear reconstruction techniques provide consistent reconstructions. Simulations for uniform and Gaussian sources show performance improvements over entropy-constrained scalar quantization for certain combinations of vector dimension and coding rate.
by Ha Quy Nguyen.
S.M.
19
Zeileis, Achim, and Torsten Hothorn. "Permutation Tests for Structural Change." Department of Statistics and Mathematics, WU Vienna University of Economics and Business, 2006. http://epub.wu.ac.at/1182/1/document.pdf.
Full textAbstract:
The supLM test for structural change is embedded into a permutation test framework for a simple location model. The resulting conditional permutation distribution is compared to the usual (unconditional) asymptotic distribution, showing that the power of the test can be clearly improved in small samples. Furthermore, generalizations are discussed for binary and multivariate dependent variables as well as model-based permutation testing for structural change. The procedures suggested are illustrated using both artificial and real-world data (number of youth homicides, employment discrimination data, structural-change publications, and stock returns).Series: Research Report Series / Department of Statistics and Mathematics
20
Yang, Keyan. "On Orbit Equivalent Permutation Groups." The Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=osu1222455916.
Full text
21
Lin, Zhicong. "Eulerian calculus arising from permutation statistics." Phd thesis, Université Claude Bernard - Lyon I, 2014. http://tel.archives-ouvertes.fr/tel-00996105.
Full textAbstract:
In 2010 Chung-Graham-Knuth proved an interesting symmetric identity for the Eulerian numbers and asked for a q-analog version. Using the q-Eulerian polynomials introduced by Shareshian-Wachs we find such a q-identity. Moreover, we provide a bijective proof that we further generalize to prove other symmetric qidentities using a combinatorial model due to Foata-Han. Meanwhile, Hyatt has introduced the colored Eulerian quasisymmetric functions to study the joint distribution of the excedance number and major index on colored permutations. Using the Decrease Value Theorem of Foata-Han we give a new proof of his main generating function formula for the colored Eulerian quasisymmetric functions. Furthermore, certain symmetric q-Eulerian identities are generalized and expressed as identities involving the colored Eulerian quasisymmetric functions. Next, generalizing the recent works of Savage-Visontai and Beck-Braun we investigate some q-descent polynomials of general signed multipermutations. The factorial and multivariate generating functions for these q-descent polynomials are obtained and the real rootedness results of some of these polynomials are given. Finally, we study the diagonal generating function of the Jacobi-Stirling numbers of the second kind by generalizing the analogous results for the Stirling and Legendre-Stirling numbers of the second kind. It turns out that the generating function is a rational function, whose numerator is a polynomial with nonnegative integral coefficients. By applying Stanley's theory of P-partitions we find combinatorial interpretations of those coefficients
22
Schaefer, Artur. "Synchronizing permutation groups and graph endomorphisms." Thesis, University of St Andrews, 2016. http://hdl.handle.net/10023/9912.
Full textAbstract:
The current thesis is focused on synchronizing permutation groups and on graph endo- morphisms. Applying the implicit classification of rank 3 groups, we provide a bound on synchronizing ranks of rank 3 groups, at first. Then, we determine the singular graph endomorphisms of the Hamming graph and related graphs, count Latin hypercuboids of class r, establish their relation to mixed MDS codes, investigate G-decompositions of (non)-synchronizing semigroups, and analyse the kernel graph construction used in the theorem of Cameron and Kazanidis which identifies non-synchronizing transformations with graph endomorphisms [20]. The contribution lies in the following points: 1. A bound on synchronizing ranks of groups of permutation rank 3 is given, and a complete list of small non-synchronizing groups of permutation rank 3 is provided (see Chapter 3). 2. The singular endomorphisms of the Hamming graph and some related graphs are characterised (see Chapter 5). 3. A theorem on the extension of partial Latin hypercuboids is given, Latin hyper- cuboids for small values are counted, and their correspondence to mixed MDS codes is unveiled (see Chapter 6). 4. The research on normalizing groups from [3] is extended to semigroups of the form < G, T >, and decomposition properties of non-synchronizing semigroups are described which are then applied to semigroups induced by combinatorial tiling problems (see Chapter 7). 5. At last, it is shown that all rank 3 graphs admitting singular endomorphisms are hulls and it is conjectured that a hull on n vertices has minimal generating set of at most n generators (see Chapter 8).
23
Xu, Jing. "On closures of finite permutation groups." University of Western Australia. School of Mathematics and Statistics, 2006. http://theses.library.uwa.edu.au/adt-WU2006.0023.
Full textAbstract:
[Formulae and special characters in this field can only be approximated. See PDF version for accurate reproduction] In this thesis we investigate the properties of k-closures of certain finite permutation groups. Given a permutation group G on a finite set Ω, for k ≥ 1, the k-closure G(k) of G is the largest subgroup of Sym(Ω) with the same orbits as G on the set Ωk of k-tuples from Ω. The first problem in this thesis is to study the 3-closures of affine permutation groups. In 1992, Praeger and Saxl showed if G is a finite primitive group and k ≥ 2 then either G(k) and G have the same socle or (G(k),G) is known. In the case where the socle of G is an elementary abelian group, so that G is a primitive group of affine transformations of a finite vector space, the fact that G(k) has the same socle as G gives little information about the relative sizes of the two groups G and G(k). In this thesis we use Aschbacher’s Theorem for subgroups of finite general linear groups to show that, if G ≤ AGL(d, p) is an affine permutation group which is not 3-transitive, then for any point α ∈ Ω, Gα and (G(3) ∩ AGL(d, p))α lie in the same Aschbacher class. Our results rely on a detailed analysis of the 2-closures of subgroups of general linear groups acting on non-zero vectors and are independent of the finite simple group classification. In addition, modifying the work of Praeger and Saxl in [47], we are able to give an explicit list of affine primitive permutation groups G for which G(3) is not affine. The second research problem is to give a partial positive answer to the so-called Polycirculant Conjecture, which states that every transitive 2-closed permutation group contains a semiregular element, that is, a permutation whose cycles all have the same length. This would imply that every vertex-transitive graph has a semiregular automorphism. In this thesis we make substantial progress on the Polycirculant Conjecture by proving that every vertex-transitive, locally-quasiprimitive graph has a semiregular automorphism. The main ingredient of the proof is the determination of all biquasiprimitive permutation groups with no semiregular elements. Publications arising from this thesis are [17, 54].
24
Xu, Jing. "On closures of finite permutation groups /." Connect to this title, 2005. http://theses.library.uwa.edu.au/adt-WU2006.0023.
Full text
25
Riehl, Amanda. "Ribbon Schur functions and permutation patterns." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2008. http://wwwlib.umi.com/cr/ucsd/fullcit?p3307163.
Full textAbstract:
Thesis (Ph. D.)--University of California, San Diego, 2008.Title from first page of PDF file (viewed July 9, 2008). Available via ProQuest Digital Dissertations. Vita. Includes bibliographical references (p. 154-157).
26
Gilbey, Julian David. "Permutation group algebras and parking functions." Thesis, Queen Mary, University of London, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.269637.
Full text
27
Maroti, Attila. "Permutation groups and representation theoretic invariants." Thesis, University of Birmingham, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.403013.
Full text
28
Jaha, Yousif Abdulhamid H. "Construction of permutation mixture experiment designs." Thesis, University of Glasgow, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.400735.
Full text
29
Benjamin, Ian Francis. "Quasi-permutation representations of finite groups." Thesis, University of Liverpool, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.250561.
Full text
30
Tracey, Gareth M. "Minimal generation of transitive permutation groups." Thesis, University of Warwick, 2017. http://wrap.warwick.ac.uk/97251/.
Full textAbstract:
This thesis discusses upper bounds on the minimal number of elements d(G) required to generate a finite group G. We derive explicit upper bounds for the function d on transitive and minimally transitive permutation groups, in terms of their degree n. In the transitive case, bounds obtained first by Kovács and Newman, then by Bryant, Kovács and Robinson, and finally by Lucchini, Menegazzo and Morigi, show that d(G) = O(n/ √log n), for a transitive permutation group G of degree n. In this thesis, we find best possible estimates for the constant involved.
31
Sheikh, Atiqa. "Orbital diameters of primitive permutation groups." Thesis, Imperial College London, 2017. http://hdl.handle.net/10044/1/58869.
Full textAbstract:
Let G be a transitive permutation group acting on a finite set X. Recall that G is primitive if there are no non-trivial equivalence relations on X which are preserved by G. An orbital graph of G is a graph with vertex set X and edges {x,y}, where (x,y) belongs to a fixed orbit of the natural action of G on the set X x X. A well-known result by D.G. Higman asserts that G is primitive if and only if all the orbital graphs are connected. For a primitive group G, we define the orbital diameter of G to be the maximum of the diameters of all orbital graphs of G. Let C be an infinite class of finite primitive permutation groups. This gives rise to an infinite family of orbital graphs. It may be that the diameters of these orbital graphs tend to infinity. More interestingly, it may be that the diameters of all the orbital graphs are bounded above by some fixed constant; if this is the case, then we say that C is bounded. Previous results by M. W. Liebeck, D. Macpherson and K. Tent focus attention on classes of almost simple primitive permutation groups which are bounded. In the thesis we analyse the orbital diameters of three families of groups, as follows. Firstly, we analyse the alternating and symmetric groups. For the primitive actions of these groups, we give necessary numerical conditions for the orbital diameter to be bounded above by some constant c and we make the result precise for c=5. For each primitive action, we also describe either all or an infinite family of orbital graphs of diameter 2. Then we analyse the almost simple groups with socle isomorphic to the projective special linear group PSL(2,q). For the primitive actions of these groups we give necessary conditions for the orbital diameter to be bounded above by 2 and we also give information about orbital graphs of diameter 2. Lastly, we analyse a large family of simple groups known as the simple groups of Lie type which consist of the simple classical groups and exceptional groups. In particular, we analyse a class of primitive actions known as parabolic actions, giving a precise description of the actions for which the orbital diameter is at most 2. For the simple classical groups, we also describe infinite families of orbital graphs of diameter 2.
32
Bahier, Valentin. "Spectre de matrices de permutation aléatoires." Thesis, Toulouse 3, 2018. http://www.theses.fr/2018TOU30069/document.
Full textAbstract:
Dans cette thèse, nous nous intéressons à des matrices aléatoires en lien avec des permutations. Nous abordons l'étude de leurs spectres de plusieurs manières, et à différentes échelles d'observation. Dans un premier temps, nous prolongeons l'étude de Wieand à propos des nombres de valeurs propres appartenant à certains arcs fixés du cercle unité. Pour cela nous tirons parti des travaux réalisés par Ben Arous et Dang sur les statistiques linéaires du spectre de matrices de permutation pour une famille de lois à un paramètre englobant le cas de la loi uniforme sur le groupe symétrique, appelée famille des lois d'Ewens. Une partie innovante de notre travail réside dans la généralisation à des arcs non nécessairement fixés. Nous obtenons en effet des résultats similaires en autorisant les longueurs des arcs à décroître lentement vers zéro avec la taille des matrices. Dans un deuxième temps, nous regardons le spectre à échelle microscopique. En nous inspirant des travaux de Najnudel et Nikeghbali en rapport avec la convergence de mesures empiriques des angles propres normalisés, nous commençons par donner un sens à la convergence en terme de comptages de points sur des intervalles fixés. A partir du processus ponctuel limite, nous montrons que le nombre de points dans un intervalle a des fluctuations asymptotiquement gaussiennes lorsque la longueur de l'intervalle tend vers l'infini. Enfin, nous adaptons certains résultats de Chhaibi, Najnudel et Nikeghbali sur le polynôme caractéristique de matrices du CUE à échelle microscopique, et les développons dans notre cadre. De manière analogue mais avec d'autres techniques de preuves, nous obtenons des convergences des polynômes caractéristiques vers des fonctions entières, et cela pour une grande famille de lois pour le tirage des permutations, incluant les lois d'EwensIn this thesis, our goal is to study random matrices related to permutations. We tackle the study of their spectra in various ways, and at different scales. First, we extend the work of Wieand about the numbers of eigenvalues lying in some fixed arcs of the unit circle. We take advantage of the results of Ben Arous and Dang on the linear statistics of the spectrum of permutation matrices for a one-parameter family of deformations of the uniform law on the symmetric group, called Ewens' measures. One of the most innovative parts of our work is the generalization to non-fixed arcs. Indeed we get similar results when we let the lengths of the arcs decrease to zero slower than 1/n. Then, we look at the spectrum at microscopic scale. Inspired by the work of Najnudel and Nikeghbali about the convergence of empirical measures of rescaled eigenangles, we give a meaning to the convergence in terms of indicator functions of intervals. From the limiting point process, we show that the number of points in any interval is asymptotically normal as the length of the interval goes to infinity. Finally, we adapt some results of Chhaibi, Najnudel and Nikeghbali on the characteristic polynomial of the CUE at microscopic scale, and develop them in our framework. Analogously but with different techniques of proof, we get that the characteristic polynomials converge to entire functions, and this for a large family of laws including the Ewens' measures
33
Kamath, Pritish. "Communication complexity of permutation-invariant functions." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/99861.
Full textAbstract:
Thesis: S.M. in Computer Science & Engineering, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 68-71).
Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of "permutation-invariant" functions. A partial function f : {0, 1}n x {0, 1}n --> {0, 1, ?} is permutation-invariant if for every bijection [pi]: {1,..., n} --> {1,.. ., n} and every x, y [sum] {0, I}n, it is the case that f (x, y) = f (x[pi], y[pi]). Most of the commonly studied functions in communication complexity are permutation-invariant. For such functions, we present a simple complexity measure (computable in time polynomial in n given an implicit description of f) that describes their communication complexity up to polynomial factors and up to an additive error that is logarithmic in the input size. This gives a coarse taxonomy of the communication complexity of simple functions. Our work highlights the role of the well-known lower bounds of functions such as SET-DISJOINTNESS and INDEXING, while complementing them with the relatively lesser-known upper bounds for GAP-INNER-PRODUCT (from the sketching literature) and SPARSE-GAP-INNER-PRODUCT (from the recent work of Canonne et al. [ITCS 2015]). We also present consequences to the study of communication complexity with imperfectly shared randomness where we show that for total permutation-invariant functions, imperfectly shared randomness results in only a polynomial blow-up in communication complexity after an additive O(log log n) loss.
by Pritish Kamath.
S.M. in Computer Science & Engineering
34
Al-Amri, Ibrahim Rasheed. "Computational methods in permutation group theory." Thesis, University of St Andrews, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.636485.
Full textAbstract:
In Chapters 2 and 3 of this thesis, we find the structure of all groups generated by an n-cycle and a 2-cycle or a 3-cycle. When these groups fail to be either Sn or An then we show that they form a certain wreath product or an extension of a wreath product. We also determine, in Chapters 4 and 5, the structure of all groups generated by an n-cycle and the product of two 2-cycles or a 4-cycle. The structure of these groups depends on the results obtained in the previous chapters. In Chapter 6 we give some general results of groups generated by an n-cycle and a k-cycle. In Chapter 7 we calculate the probability of generating a proper subgroup, other than the alternating group, by two elements one of which is an n-cyc1e and the other is chosen randomly. In Chapters 8 and 9 we give some of the programs written in GAP language, which used in the earlier work and which can be used by other workers in this area.
35
SILVA, Caio César Sabino. "Motion compensated permutation-based video encryption." Universidade Federal de Pernambuco, 2015. https://repositorio.ufpe.br/handle/123456789/23821.
Full textAbstract:
Submitted by Rafael Santana (rafael.silvasantana@ufpe.br) on 2018-02-21T17:49:09Z
No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
dissertacao-caio-cesar.pdf: 1833894 bytes, checksum: 738a1e0a2b6bcf2f5c13dca42eaee10c (MD5)Made available in DSpace on 2018-02-21T17:49:09Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) dissertacao-caio-cesar.pdf: 1833894 bytes, checksum: 738a1e0a2b6bcf2f5c13dca42eaee10c (MD5) Previous issue date: 2015-08-25
In the context of multimedia applications security, digital video encryption techniques have been developed to assure the confidentiality of information contained in such media type. Compression and encryption used to be considered as opposite in terms of exploring the data’s entropy, however in the last decades there was an increase of data volume operated by video encryption applications which demanded improvements on data compressibility in video encryption. In this sense, many techniques have been developed as entropy coding providing both encryption and compression simultaneously. An existing cryptographic scheme, introduced by Socek et al., is based on permutation transformations and applies encryption prior to the compression stage. The encryption applied by this technique may not be as safe as a conventional encryption technique, but its security is still considered acceptable for most video applications. It can improve the original data’s spatial correlation in case the consecutive frames are similar, making it possibly even more compressible than the original video. However the original cryptographic scheme was designed to explore only the spatial correlation inside every frame, but codecs can also explore non-trivial temporal correlation. Also the improvements on the data’s spatial correlation coming from the permutation transformations are highly based on the natural temporal correlation in the video. Hence its performance is extremely associated to the amount of motion in the video. The work developed in this dissertation aims to extend this cryptographic scheme, including motion compensation concepts to the permutation based transformations used in the video encryption technique to improve its performance and make it more resilient to high motion videos.
No contexto de segurança de aplicações multimídia, técnicas de encriptação de vídeo têm sido desenvolvidas com o intuito de assegurar a confidencialidade das informações contidas em tal tipo de mídia. Compressão e encriptação costumavam ser consideradas áreas opostas em termos de exploração de entropia de dados, entretanto nas últimas décadas houve um aumento significante no volume de dados operado por aplicações de encriptação de vídeo, o que exigiu melhoras na compressão de vídeos encriptados. Neste sentido, diversas técnicas têm sido desenvolvidas como codificação de entropia provendo encriptação e compressão simultaneamente. Um esquema criptográfico existente, introduzido por Socek et al., é baseado em transformações de permutação e aplica encriptação anteriormente à fase de compressão. A encriptação aplicada por essa técnica pode ser considerada não tão segura quanto um esquema criptográfico convencional, mas ainda aceitável pela maioria das aplicações de vídeo. A mesma é capaz de melhorar a correlação espacial do vídeo original, caso os quadros consecutivos sejam suficientemente similares, tornando-o possivelmente mais compressível que o vídeo original. Entretanto, o esquema criptográfico original foi designado para explorar apenas correlação espacial de cada quadro, e codificadores podem explorar também correlação temporal não trivial. Além disso, as melhoras na correção espacial advindas das transformações de permutação são altamente baseadas na correlação temporal natural do vídeo. Portanto, a performance do esquema é extremamente associada à quantidade de movimento no vídeo. O trabalho desenvolvido nesta dissertação tem como objetivo estender esse esquema criptográfico, incluindo conceitos de compensação de movimento nas transformações baseadas em permutação usadas na encriptação de vídeo para melhorar sua performance, tornando o esquema mais resiliente a vídeos com muito movimento.
36
Winkler, Anderson M. "Widening the applicability of permutation inference." Thesis, University of Oxford, 2016. https://ora.ox.ac.uk/objects/uuid:ce166876-0aa3-449e-8496-f28bf189960c.
Full textAbstract:
This thesis is divided into three main parts. In the first, we discuss that, although permutation tests can provide exact control of false positives under the reasonable assumption of exchangeability, there are common examples in which global exchangeability does not hold, such as in experiments with repeated measurements or tests in which subjects are related to each other. To allow permutation inference in such cases, we propose an extension of the well known concept of exchangeability blocks, allowing these to be nested in a hierarchical, multi-level definition. This definition allows permutations that retain the original joint distribution unaltered, thus preserving exchangeability. The null hypothesis is tested using only a subset of all otherwise possible permutations. We do not need to explicitly model the degree of dependence between observations; rather the use of such permutation scheme leaves any dependence intact. The strategy is compatible with heteroscedasticity and can be used with permutations, sign flippings, or both combined. In the second part, we exploit properties of test statistics to obtain accelerations irrespective of generic software or hardware improvements. We compare six different approaches using synthetic and real data, assessing the methods in terms of their error rates, power, agreement with a reference result, and the risk of taking a different decision regarding the rejection of the null hypotheses (known as the resampling risk). In the third part, we investigate and compare the different methods for assessment of cortical volume and area from magnetic resonance images using surface-based methods. Using data from young adults born with very low birth weight and coetaneous controls, we show that instead of volume, the permutation-based non-parametric combination (NPC) of thickness and area is a more sensitive option for studying joint effects on these two quantities, giving equal weight to variation in both, and allowing a better characterisation of biological processes that can affect brain morphology.
37
Bevan, David Ian. "On the growth of permutation classes." Thesis, Open University, 2015. http://oro.open.ac.uk/43875/.
Full textAbstract:
We study aspects of the enumeration of permutation classes, sets of permutations closed downwards under the subpermutation order. First, we consider monotone grid classes of permutations. We present procedures for calculating the generating function of any class whose matrix has dimensions m × 1 for some m, and of acyclic and unicyclic classes of gridded permutations. We show that almost all large permutations in a grid class have the same shape, and determine this limit shape. We prove that the growth rate of a grid class is given by the square of the spectral radius of an associated graph and deduce some facts relating to the set of grid class growth rates. In the process, we establish a new result concerning tours on graphs. We also prove a similar result relating the growth rate of a geometric grid class to the matching polynomial of a graph, and determine the effect of edge subdivision on the matching polynomial. We characterise the growth rates of geometric grid classes in terms of the spectral radii of trees. We then investigate the set of growth rates of permutation classes and establish a new upper bound on the value above which every real number is the growth rate of some permutation class. In the process, we prove new results concerning expansions of real numbers in non-integer bases in which the digits are drawn from sets of allowed values. Finally, we introduce a new enumeration technique, based on associating a graph with each permutation, and determine the generating functions for some previously unenumerated classes. We conclude by using this approach to provide an improved lower bound on the growth rate of the class of permutations avoiding the pattern 1324. In the process, we prove that, asymptotically, patterns in Łukasiewicz paths exhibit a concentrated Gaussian distribution.
38
Fiddes, Ceridwyn. "The cyclizer function on permutation groups." Thesis, University of Bath, 2003. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.425697.
Full text
39
Juan, Shirley Marina. "Images of Permutation and Monomial Progenitors." CSUSB ScholarWorks, 2018. https://scholarworks.lib.csusb.edu/etd/720.
Full textAbstract:
We have conducted a systematic search for finite homomorphic images of several permutation and monomial progenitors. We have found original symmetric presentations for several important groups such as the Mathieu sporadic simple groups, Suzuki simple group, unitary group, Janko group, simplectic groups, and projective special linear groups. We have also constructed, using the technique of double coset enumeration, the following groups, L_2(11), S(4,3):2, M11, and PGL(2,11). The isomorphism class of each of the finite images is also given.
40
Acan, Huseyin. "An Enumerative-Probabilistic Study of Chord Diagrams." The Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1373310487.
Full text
41
Boberg, Jonas. "Counting Double-Descents and Double-Inversions in Permutations." Thesis, Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-54431.
Full textAbstract:
In this paper, new variations of some well-known permutation statistics are introduced and studied. Firstly, a double-descent of a permutation π is defined as a position i where πi ≥ 2πi+1. By proofs by induction and direct proofs, recursive and explicit expressions for the number of n-permutations with k double-descents are presented. Also, an expression for the total number of double-descents in all n-permutations is presented. Secondly, a double-inversion of a permutation π is defined as a pair (πi,πj) where i<j but πi ≥ 2πj. The total number of double-inversions in all n-permutations is presented.
42
Li, Wensheng. "Study of hybrid permutation frequency phase modulation." Thesis, University of Ottawa (Canada), 1996. http://hdl.handle.net/10393/9723.
Full textAbstract:
In future communication applications, it is desirable to provide good system performance and more services to a number of users using the minimum resources. These expectations pose challenges in the design of modulation and coding. This thesis presents and studies the hybrid permutation frequency phase modulation (HPM) communication systems. By combining FSK and PSK, the signal energy per symbol is increased. Applying this type of signals to permutation modulation, the concept of HPM is presented and its signal properties have been mathematically analyzed. The expression for bandwidth efficiency is derived. The performance of transmission systems is related with channel characteristics. The behavior of HPM is appraised in the case of AWGN and frequency selective fading channels. The coherent and noncoherent detection have been considered respectively. Our performance analysis are based on the measures of bit error performance and bandwidth efficiency. It is shown that a large set of waveforms can be easily obtained in HPM. For uncoded HPM, most of the possible waveforms are used, and the system power and bandwidth efficiency can be greatly improved in AWGN channels. The nature of permutation modulation indicates an implicit diversity in frequency selective fading channels. By using a small portion of waveforms, which leads to coded HPM, the effective diversity increases. The rule of selecting waveforms is worth studying. We propose t-designs as the candidate. The results show that coded HPM is a power efficient scheme and is robust in fading environments.
43
Chen, Zhi-Guo. "Security aspects of substitution-permutation encryption networks." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/tape17/PQDD_0008/MQ36013.pdf.
Full text
44
Kingston, R. G. "Charge-permutation reactions of gas-phase ions." Thesis, Swansea University, 1986. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.637801.
Full textAbstract:
Collisions of high translational energy ions with neutral gas targets (N) may result in an alteration in the number or sign of the charge and the internal energy of the ion undergoing reaction. These gas-phase reactions are referred to as charge-permutation reactions. In this thesis several types of charge-permutation reaction have been studied, to glean information on the energetics of the reaction. In particular, for doubly- and triply-charged ions, by measuring translational energy changes of the ion undergoing reaction and from energy release data when the ion undergoes fragmentation. Fragmentation patterns have provided structural information. Charge-stripping reactions of polycyclic aromatic species, Mn+ + N → M^(n+1)++N+e^- have been used to determine ionization energies. Relationships between, the ionization energies of M^2+ and M^3+ and the appearance energy of M^+ have been investigated, the charge-stripping efficiency of the collision gas, the ionization energy, the ion velocity and ion radius, have been derived. Charge-inversion reactions of NO^- leading to NO^+, O^+ and N^+ have revealed the role of neutral species and methods are demonstrated to separate and categorise the consecutive reaction steps. Some fragment ion peaks, of composite nature, have been deconvoluted to show the contributions of the various reactions. Charge-exchange reactions (electron capture) M^n+ + N → M(n-1)+ + N+have been used to assign the electronic states for a series of polycyclic aromatic compounds, where n = 2 or 3. Internal energy distributions of product ions have been measured utilising known breakdown graphs. Empirical relationships between cross-sections for electron capture and the energy balance for the reaction have been formulated. The only reaction studied which occurs unimolecularly is charge separation. M(p+q)+ → Mp+atop a + Mq+atop b From energy release data, intercharge distances have been calculated for multiply-charged polycyclic aromatic ions and structural information inferred. Charge exchange and charge stripping have been used to detect structural differences between three C_6H_6 isomers.
45
Lindner, Marko, and Gilbert Strang. "The Main Diagonal of a Permutation Matrix." Universitätsbibliothek Chemnitz, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-80273.
Full textAbstract:
By counting 1's in the "right half" of 2w consecutive rows, we locate the main diagonal of any doubly infinite permutation matrix with bandwidth w. Then the matrix can be correctly centered and factored into block-diagonal permutation matrices.
Part II of the paper discusses the same questions for the much larger class of band-dominated matrices. The main diagonal is determined by the Fredholm index of a singly infinite submatrix. Thus the main diagonal is determined "at infinity" in general, but from only 2w rows for banded permutations.
46
Gray, Darren George David. "The submodule structure of some permutation modules." Thesis, University of East Anglia, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.389230.
Full text
47
SILVA, DANILO. "PERMUTATION CODES FOR DATA COMPRESSION AND MODULATION." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2005. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=6202@1.
Full textAbstract:
CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICOCódigos de permutação são uma interessante ferramenta matemática que pode ser empregada para construir tanto esquemas de compressão com perdas quanto esquemas de modulação em um sistema de transmissão digital. Códigos de permutação vetorial, uma extensão mais poderosa dos códigos de permutação escalar, foram recentemente introduzidos no contexto de compressão de fontes. Este trabalho apresenta novas contribuições a essa teoria e introduz os códigos de permutação vetorial no contexto de modulação. Para compressão de fontes, é demonstrado matematicamente que os códigos de permutação vetorial (VPC) têm desempenho assintótico idêntico ao do quantizador vetorial com restrição de entropia (ECVQ). Baseado neste desenvolvimento, é proposto um método eficiente para o projeto de VPC s. O bom desempenho dos códigos projetados com esse método é verificado através de resultados experimentais para as fontes uniforme e gaussiana: são exibidos VPC s cujo desempenho é semelhante ao do ECVQ e superior ao de sua versão escalar. Para o propósito de transmissão digital, é verificado que também a modulação baseada em códigos de permutação vetorial (VPM) possui desempenho superior ao de sua versão escalar. São desenvolvidas as expressões para o projeto ótimo de VPM, e um método é apresentado para detecção ótima de VPM em canais AWGN e com desvanecimento.
Permutation codes are an interesting mathematical tool which can be used to devise both lossy compression schemes and modulation schemes for digital transmission systems. Vector permutation codes, a more powerful extension of scalar permutation codes, were recently introduced for the purpose of source compression. This work presents new contributions to this theory and also introduces vector permutation codes for the purpose of modulation. For source compression, it is proved that vector permutation codes (VPC) have an asymptotical performance equal to that of an entropy-constrained vector quantizer (ECVQ). Based on this development, an efficient method is proposed for VPC design. Experimental results for Gaussian and uniform sources show that the codes designed by this method have indeed a good performance: VPC s are exhibited whose performances are similar to that of ECVQ and superior to those of their scalar counterparts. In the context of digital transmission, it is verified that also vector permutation modulation (VPM) is superior in performance to scalar permutation modulation. Expressions are developed for the optimal design of VPM, and a method is presented for maximum-likelihood detection of VPM in AWGN and fading channels.
48
Vauhkonen, Antti Kalervo. "Finite primitive permutation groups of rank 4." Thesis, Imperial College London, 1993. http://hdl.handle.net/10044/1/58543.
Full textAbstract:
In this thesis we classify finite primitive permutation groups of rank 4. According to the 0' Nan-Scott theorem, a finite primitive permutation group is an affine group, an almost simple group, or has either simple diagonal action, product action or twisted wreath action. In Chapter 1 we completely determine the primitive rank 4 permutation groups with one of the last three types of actions up to permutation equivalence. In Chapter 2 we use Aschbacher's subgroup structure theorem for the finite classical groups to reduce the classification of affine primitive rank 4 permutation groups G of degree p*^ (p prime) to the case where a point stabilizer G in G satisfies soc(G/Z(G ))=L for some ^ 0 0 0 non-abelian simple group L. In Chapter 3 we classify all such groups G with L a simple group of Lie type over a finite field of characteristic p. Finally, in Chapter 4 we determine all the faithful primitive rank 4 permutation representations of the finite linear groups up to permutation equivalence.
49
Turner, Simon. "The cyclizer series of infinite permutation groups." Thesis, University of Bath, 2013. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.577751.
Full textAbstract:
The cyclizer of an infinite permutation group G is the group generated by the cycles involved in elements of G, along with G itself. There is an ascending subgroup series beginning with G, where each term in the series is the cyclizer of the previous term. We call this series the cyclizer series for G. If this series terminates then we say the cyclizer length of G is the length of the respective cyclizer series. We study several innite permutation groups, and either determine their cyclizer series, or determine that the cyclizer series terminates and give the cyclizer length. In each of the innite permutation groups studied, the cyclizer length is at most 3. We also study the structure of a group that arises as the cyclizer of the innite cyclic group acting regularly on itself. Our study discovers an interesting innite simple group, and a family of associated innite characteristically simple groups.
50
Strasser, Helmut, and Christian Weber. "On the Asymptotic Theory of Permutation Statistics." SFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business, 1999. http://epub.wu.ac.at/102/1/document.pdf.
Full textAbstract:
In this paper limit theorems for the conditional distributions of linear test statistics are proved. The assertions are conditioned by the sigma-field of permutation symmetric sets. Limit theorems are proved both for the conditional distributions under the hypothesis of randomness and under general contiguous alternatives with independent but not identically distributed observations. The proofs are based on results on limit theorems for exchangeable random variables by Strasser and Weber. The limit theorems under contiguous alternatives are consequences of an LAN-result for likelihood ratios of symmetrized product measures. The results of the paper have implications for statistical applications. By example it is shown that minimum variance partitions which are defined by observed data (e.g. by LVQ) lead to asymptotically optimal adaptive tests for the k-sample problem. As another application it is shown that conditional k-sample tests which are based on data-driven partitions lead to simple confidence sets which can be used for the simultaneous analysis of linear contrasts. (author's abstract)Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"