Orientador: Jose Plinio de Oliveira Santos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatisitca e Computação Cientifica / Made available in DSpace on 2018-08-06T23:31:58Z (GMT). No. of bitstreams: 1 Alegri_Mateus_M.pdf: 858876 bytes, checksum: ff48274e36a7a886794139ed3337dee8 (MD5) Previous issue date: 2006 / Resumo: Neste trabalho estudaremos a estrutura dos quadrados latinos sob ponto de vista da matemática discreta. Faremos uma série de equivalências com outras estruturas tais como Teoria dos Grafos, Grupos, e sempre enfocando questões enumerativas. Certas propriedades de quadrados latinos, tais como ortogonalidade vão trabalhadas. E encerraremos com aplicações a teoria dos códigos algébricos. Palavras chave: quadrados latinos; Quadrados latinos mutualmente ortogonais; MOLS; hipercubos; códigos MDS / Abstract: In this work, we study the structure of latin squares on the discrete mathematics viewpoint. We do a lot of equivalences with some others structures, such that Graph theory, Groups, e ever we loking enumeration questions. Certains proprieties of latin squares, such ortogonality will be worked. And we finish with aplications to the Algebric Code Theory / Mestrado / Matematica Discreta / Mestre em Matemática Aplicada

O estudo do comportamento assintótico de densidades de algumas subestruturas é uma das principais áreas de estudos em combinatória. Na Teoria das Permutações, fixadas permutações ?1 e ?2 e um inteiro n > 0, estamos interessados em estudar o comportamento das densidades de ?1 e ?2 na família de permutações de tamanho n. Assim, existem duas direções naturais que podemos seguir. Na primeira direção, estamos interessados em achar a permutação de tamanho n que maximiza a densidade das permutações ?1 e ?2 simultaneamente. Para n suficientemente grande, explicitamos a densidade máxima que uma família de permutações podem assumir dentre todas as permutações de tamanho n. Na segunda direção, estamos interessados em achar a permutação de tamanho n que minimiza a densidade de ?1 e ?2 simultaneamente. Quando ?1 é a permutação identidade com k elementos e ?2 é a permutação reversa com l elementos, Myers conjecturou que o mínimo é atingido quando tomamos o mínimo dentre as permutações que não possuem a ocorrência de ?1 ou ?2. Mostramos que se restringirmos o espaço de busca somente ao conjunto de permutações em camadas, então a Conjectura de Myers é verdadeira. Por outro lado, na Teoria dos Grafos, o problema de encontrar um circuito Hamiltoniano é um problema NP-completo clássico e está entre os 21 problemas Karp. Dessa forma, uma abordagem comum na literatura para atacar esse problema é encontrar condições que um grafo deve satisfazer e que garantem a existência de um circuito Hamiltoniano em tal grafo. O célebre resultado de Dirac afirma que se um grafo G de ordem n possui grau mínimo pelo menos n/2, então G possui um circuito Hamiltoniano. Seguindo a linha de Dirac, mostramos que, dados inteiros 1 6 l 6 k/2 e ? > 0 existe um inteiro n0 > 0 tal que, se um hipergrafo k-uniforme H de ordem n satisfaz ?k-2(H) > ((4(k - l) - 1)/(4(k - l)2) + ?) (n 2), então H possui um l-circuito Hamiltoniano. / The study of asymptotic behavior of densities of some substructures is one of the main areas in combinatorics. In Permutation Theory, fixed permutations ?1 and ?2 and an integer n > 0, we are interested in the behavior of densities of ?1 and ?2 among the permutations of size n. Thus, there are two natural directions we can follow. In the first direction, we are interested in finding the permutation of size n that maximizes the density of the permutations ?1 and ?2 simultaneously. We explicit the maximum density of a family of permutations between all the permutations of size n. In the second direction, we are interested in finding the permutation of size n that minimizes the density of ?1 and ?2 simultaneously. When ?1 is the identity permutation with l elements and ?2 is the reverse permutation with k elements, Myers conjectured that the minimum is achieved when we take the minimum among the permutations which do not have the occurrence of ?1 or ?2. We show that if we restrict the search space only to set of layered permutations and k > l, then the Myers\' Conjecture is true. On the other hand, in Graph Theory, the problem of finding a Hamiltonian cycle is a NP-complete problem and it is among the 21 Karp problems. Thus, one approach to attack this problem is to find conditions that a graph must meet to ensure the existence of a Hamiltonian cycle on it. The celebrated result of Dirac shows that a graph G of order n that has minimum degree at least n/2 has a Hamiltonian cycle. Following the line of Dirac, we show that give integers 1 6 l 6 k/2 and gamma > 0 there is an integer n0 > 0 such that if a hypergraph k-Uniform H of order n satisfies ?k-2(H) > ((4(k-l)-1)/(4(k-l)2)+?) (n 2), then H has a Hamiltonian l-cycle.

A permutation class C is splittable if it is contained in a merge of its two proper subclasses, and it is 1-amalgamable if given two permutations σ, τ ∈ C, each with a marked element, we can find a permutation π ∈ C containing both σ and τ such that the two marked elements coincide. In this thesis, we study both 1-amalgamability and splittability of permutation classes. It was previously shown that unsplittability implies 1-amalgamability. We prove that unsplittability and 1-amalgamability are not equivalent properties of permutation classes by showing that there is a permutation class that is both splittable and 1-amalgamable. Moreover, we show that there are infinitely many such classes. Our construction is based on the concept of LR-inflations or more generally on hereditary 2-colorings, which we both introduce here and which may be of independent interest. 1

Masters of Science / Codes Related to and Derived from Hamming Graphs T.R Muthivhi M.Sc thesis, Department of Mathematics, University of Western Cape For integers n; k 1; and k n; the graph 􀀀k n has vertices the 2n vectors of Fn2 and adjacency de ned by two vectors being adjacent if they di er in k coordinate positions. In particular, 􀀀1 n is the classical n-cube, usually denoted by H1(n; 2): This study examines the codes (both binary and p-ary for p an odd prime) of the row span of adjacency and incidence matrices of these graphs. We rst examine codes of the adjacency matrices of the n-cube. These have been considered in [14]. We then consider codes generated by both incidence and adjacency matrices of the Hamming graphs H1(n; 3) [12]. We will also consider codes of the line graphs of the n-cube as in [13]. Further, the automorphism groups of the codes, designs and graphs will be examined, highlighting where there is an interplay. Where possible, suitable permutation decoding sets will be given.

Multivariate normal distribution is commonly encountered in any field, a frequent issue is the missing values in practice. The purpose of this research was to estimate the parameters in three-dimensional covariance permutation-symmetric normal distribution with complete data and all possible patterns of incomplete data. In this study, MLE with missing data were derived, and the properties of the MLE as well as the sampling distributions were obtained. A Monte Carlo simulation study was used to evaluate the performance of the considered estimators for both cases when ρ was known and unknown. All results indicated that, compared to estimators in the case of omitting observations with missing data, the estimators derived in this article led to better performance. Furthermore, when ρ was unknown, using the estimate of ρ would lead to the same conclusion.

This thesis presents and evaluates a new parallel algorithm that computes all single cosets in the double coset M₂₄ P M₂₄, where P is a permutation on n points of a certain cycle structure, and M₂₄ is the Mathieu group related to a Steiner system S(5, 8, 24) as its automorphism group. The purpose of this work is not to replace the existing algorithms, but rather to explore a possibility to extend calculations of single cosets beyond the limits encountered when using currently available methods.

A Schur ring is a subring of the group algebra with a basis that is formed by a partition of the group. These subrings were initially used to study finite permutation groups, and classifications of Schur rings over various finite groups have been studied. Here we investigate Schur rings over various infinite groups, including free groups. We classify Schur rings over the infinite cyclic group.

A new approach for solving permutation scheduling problems with ant colony optimization (ACO) is proposed in this paper. The approach assumes that no precedence constraints between the jobs have to be fulfilled. It is tested with an ACO algorithm for the single-machine total weighted deviation problem. In the new approach the ants allocate the places in the schedule not sequentially, as in the standard approach, but in random order. This leads to a better utilization of the pheromone information. It is shown by experiments that adequate combinations between the standard approach which can profit from list scheduling heuristics and the new approach perform particularly well.

In the first chapter, we define Steinhaus set as a set that meets every isometric copy of another set at exactly one point. We show that there is no Steinhaus set for any four-point subset in a plane.In the second chapter, we define the orbit tree of a permutation group of natural numbers, and further introduce compressed orbit trees. We show that any rooted finite tree can be realized as a compressed orbit tree of some permutation group. In the third chapter, we investigate certain classes of closed permutation groups of natural numbers with respect to their universal and surjectively universal groups. We characterize two-sided invariant groups, and prove that there is no universal group for countable groups, nor universal group for two-sided invariant groups in permutation groups of natural numbers.

When classifying high-dimensional data, a lot can be gained, in terms of both computational time and precision, by only considering the most important features. Many feature selection methods are based on the assumption that important features are highly correlated with their corresponding classes, but mainly uncorrelated with each other. Often, this assumption can help eliminate redundancies and produce good predictors using only a small subset of features. However, when the predictability depends on interactions between the features, such methods will fail to produce satisfactory results. Also, since the suitability of the selected features depends on the learning algorithm in which they will be used, correlation-based filter methods might not be optimal when using genetic programs as the final classifiers, as they fail to capture the possibly complex relationships that are expressible by the genetic programming rules. In this thesis a method that can find important features, both independently and dependently discriminative, is introduced. This method works by performing two different types of permutation tests that classifies each of the features as either irrelevant, independently predictive or dependently predictive. The proposed method directly evaluates the suitability of the features with respect to the learning algorithm in question. Also, in contrast to computationally expensive wrapper methods that require several subsets of features to be evaluated, a feature classification can be obtained after only one single pass, even though the time required does equal the training time of the classifier. The evaluation shows that the attributes chosen by the permutation tests always yield a classifier at least as good as the one obtained when all attributes are used during training - and often better. The proposed method also fares well when compared to other attribute selection methods such as RELIEFF and CFS. / Då man handskas med data av hög dimensionalitet kan man uppnå både bättre precision och förkortad exekveringstid genom att enbart fokusera på de viktigaste attributen. Många metoder för att hitta viktiga attribut är baserade på ett grundantagande om en stark korrelation mellan de viktiga attributen och dess tillhörande klass, men ofta även på ett oberoende mellan de individuella attributen. Detta kan å ena sidan leda till att överflödiga attribut lätt kan elimineras och därmed underlätta processen att hitta en bra klassifierare, men å andra sidan också ge missvisande resultat ifall förmågan att separera klasser i hög grad beror på interaktioner mellan olika attribut. Då lämpligheten av de valda attributen också beror på inlärningsalgoritmen i fråga är det troligtvis inte optimalt att använda sig av metoder som är baserade på korrelationer mellan individuella attribut och dess tillhörande klass, ifall målet är att skapa klassifierare i form av genetiska program, då sådana metoder troligtvis inte har förmågan att fånga de komplexa interaktioner som genetiska program faktiskt möjliggör. Det här arbetet introducerar en metod för att hitta viktiga attribut - både de som kan klassifiera data relativt oberoende och de som får sina krafter endast genom att utnyttja beroenden av andra attribut. Den föreslagna metoden baserar sig på två olika typer av permutationstester, där attribut permuteras mellan de olika dataexemplaren för att sedan klassifieras som antingen oberende, beroende eller irrelevanta. Lämpligheten av ett attribut utvärderas direkt med hänsyn till den valda inlärningsalgoritmen till skillnad från så kallade wrappers, som är tidskrävande då de kräver att flera delmängder av attribut utvärderas. Resultaten visar att de attribut som ansetts viktiga efter permutationstesten genererar klassifierare som är åtminstone lika bra som när alla attribut används, men ofta bättre. Metoden står sig också bra när den jämförs med andra metoder som till exempel RELIEFF och CFS.