<p> Propositional proof complexity is a field of theoretical computer science which concerns itself with the lengths of formal proofs in various propositional proof systems. Frege systems are an important class of propositional proof systems. Extended Frege augments them by allowing the introduction of new variables to abbreviate formulas. Perhaps the largest open question in propositional proof complexity is whether or not Extended Frege is significantly more powerful that Frege. Several proof systems, each introducing new rules or syntax to Frege, have been developed in an attempt to shed some light on this problem.</p> <p> We introduce one such system, which we call H, which allows for the quantification of transpositions of propositional variables. We show that H is sound and complete, and that H's transposition quantifiers efficiently represent any permutation.</p> <p> The most important contribution is showing that a fragment of this proof system, H*1, is equivalent in power to Extended Frege. This is a complicated and rather technical result, and is achieved by showing that H*1 can efficiently prove translations of the first-order logical theory ∀PLA, a logical theory well suited for reasoning about linear algebra and properties of graphs.</p> / Thesis / Master of Science (MSc)

The original Macdonald polynomials P_μ form a basis for the vector space of symmetric functions which specializes to several of the common bases such as the monomial, Schur, and elementary bases. There are a number of different types of Macdonald polynomials obtained from the original P_μ through a combination of algebraic and plethystic transformations one of which is the modified Macdonald polynomial H̃_μ. In this dissertation, we study a certain specialization F̃_μ(q,t) which is the coefficient of x₁x₂…x_N in H̃_μ and also the Hilbert series of the Garsia-Haiman module M_μ. Haglund found a combinatorial formula expressing F̃_μ as a sum of n! objects weighted by two statistics. Using this formula we prove a q,t-analogue of the hook-length formula for hook shapes. We establish several new combinatorial operations on the fillings which generate F̃_μ. These operations are used to prove a series of recursions and divisibility properties for F̃_μ. / Ph. D.

Maps have been extensively studied and are important in many research fields. A map is a 2-cell embedding of a graph on an orientable surface. Motivated by a new way to read the information provided by the skeleton of a map, we introduce new objects called plane permutations. Plane permutations not only provide new insight into enumeration of maps and related graph embedding problems, but they also provide a powerful framework to study less related genome rearrangement problems. As results, we refine and extend several existing results on enumeration of maps by counting plane permutations filtered by different criteria. In the spirit of the topological, graph theoretical study of graph embeddings, we study the behavior of graph embeddings under local changes. We obtain a local version of the interpolation theorem, local genus distribution as well as an easy-to-check necessary condition for a given embedding to be of minimum genus. Applying the plane permutation paradigm to genome rearrangement problems, we present a unified simple framework to study transposition distances and block-interchange distances of permutations as well as reversal distances of signed permutations. The essential idea is associating a plane permutation to a given permutation or signed permutation to sort, and then applying the developed plane permutation theory. / Ph. D.

L'augmentation du nombre de génomes totalement séquencés rend de plus en plus efficace l'étude des mécanismes évolutifs à partir de la comparaison de génomes contemporains. L'un des principaux problèmes réside dans la reconstruction d'architectures de génomes ancestraux plausibles afin d'apporter des hypothèses à la fois sur l'histoire des génomes existants et sur les mécanismes de leur formation. Toutes les méthodes de reconstruction ancestrale ne convergent pas nécessairement vers les mêmes résultats mais sont toutes basées sur les trois mêmes étapes : l'identification des marqueurs communs dans les génomes contemporains, la construction de cartes comparatives des génomes, et la réconciliation de ces cartes en utilisant le critère de parcimonie maximum. La qualité importante des données à analyser nécessite l'automatisation des traitements et résoudre ces problèmes représente de formidables challenges computationnels. Affiner le modèles et outils mathématiques existants par l'ajout de contraintes biologiques fortes rend les hypothèses établies biologiquement plus réalistes. Dans cette thèse, nous proposons une nouvelle méthode permettant d'identifier des marqueurs communs pour des espèces évolutivement distantes. Ensuite, nous appliquons sur les cartes comparatives reconstituées une nouvelle méthode pour la reconstruction d'architectures ancestrales basée sur les adjacences entre les marqueurs calculés et les distances génomiques entre les génomes contemporains. Enfin, après avoir corrigé l'algorithme existant permettant de déterminer une séquence optimale de réarrangements qui se sont produits durant l'évolution des génomes existants depuis leur ancêtre commun, nous proposons un nouvel outil appelé VIRAGE qui permet la visualisation animée des scénarios de réarrangements entre les espèces / Abstract

Le développement de la numérisation systématique des formes 3D (conservation du patrimoine national, commerce électronique, reverse engineering, intégration d’objets réels dans des environnements de réalité virtuelle) et le besoin toujours croissant de ces objets géométriques dans de nombreuses applications (conception assistée par ordinateur, calcul de simulations par éléments finis, système d’informations géographiques, loisirs numériques) a entrainé une augmentation vertigineuse du volume de données à traiter, avec l’émergence de nombreuses méthodes de compression de modèles 3D. Ce volume de données devient encore plus difficile à maitriser lorsque l’aspect temporel entre en jeu. Les maillages correspondent au modèle classiquement utilisé pour modéliser les formes numérisées et certaines approches de compression exploitent la propriété qu’une bonne estimation de la connectivité peut être déduite de l’échantillonnage, lorsque ce dernier s’avère suffisamment dense. La compression de la connectivité d’un maillage revient alors au codage de l’écart entre deux connectivités proches. Dans ce mémoire, nous nous intéressons au codage compact de cette différence pour des maillages surfaciques. Nos travaux sont fondés sur l’utilisation de la bascule d’arête (edge flip) et l’étude de ses propriétés. Nos contributions sont les suivantes. Etant donné deux triangulations connexes partageant le même nombre de sommets et un même genre topologique, nous proposons un algorithme direct et efficace pour générer une séquence de bascules d’arêtes permettant de passer d’un maillage `a un autre. Nous nous appuyons sur une correspondance entre les sommets des deux maillages, qui, si elle est non fournie, peut être choisie de manière totalement aléatoire / The development of scanning 3D shapes (national heritage conservation, ecommerce, reverse engineering, virtual reality environments) and the growing need for geometric objects in many applications (computer-aided design, simulations, geographic information systems, digital entertainment) have led to a dramatic increase in the volume of data to be processed, and the emergence of many methods of compression of 3D models. This volume of data becomes even more difficult to control when the temporal aspect comes in. Meshes correspond to the pattern typically used to model the scanned forms and some approaches exploit a property of compression that a good estimation of connectivity can be derived from sampling, when it appears sufficiently dense. Compressing the connectivity of a mesh is equivalent to coding the difference between two close connectivities. In this thesis, we focus on the compact coding of this difference for 2-dimensional meshes. Our work is based on the use and study of the properties of the edge flip. Our contributions are the following : - Given two connected triangulations that share the same number of vertices and the same topological genus, we propose a direct and efficient algorithm to generate a sequence of edge flips to change one mesh into the other. We rely on a correspondence between the vertices of the two meshes, which, if not provided, may be chosen randomly. The validity of the algorithm is based on the fact that we intend to work in a triangulation of a different class from those generally used. - We then generalize the edge flips to triangulations in which we identify each edge with a label. We show that a sequence of edge flips can be used to transpose two labels, under certain conditions. From this result, the edge flip can be generalized to meshes whose faces are not necessarily triangular, which allowed us to develop an algorithm for reducing sequences of edge flips. - Finally, we present a compact coding approach for a sequence of edge flips, and determine under what conditions it is better to use this compact transformation between two connectivities instead of coding them independently by a static algorithm

[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].

Previous work by Flaxman (2004) and Biers-Ariel et al. (2018) focused on the number of distinct words embedded in a string of words of length n. In this thesis, we will extend this work to permutations, focusing on the maximum number of distinct permutations contained in a permutation on [n] = {1,2,...,n} and on the expected number of distinct permutations contained in a random permutation on [n]. We further considered the problem where repetition of subsequences are as a result of the occurrence of (Type A and/or Type B) replications. Our method of enumerating the Type A replications causes double counting and as a result causes the count of the number of distinct sequences to go down.

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.

Part I of this thesis presents methods for finding the primitive permutation groups of degree d, where 2500 ≤ d < 4096, using the O'Nan-Scott Theorem and Aschbacher's theorem. Tables of the groups G are given for each O'Nan-Scott class. For the non-affine groups, additional information is given: the degree d of G, the shape of a stabiliser in G of the primitive action, the shape of the normaliser N in S[subscript(d)] of G and the rank of N. Part II presents a new algorithm NormaliserGL for computing the normaliser in GL[subscript(n)](q) of a group G ≤ GL[subscript(n)](q). The algorithm is implemented in the computational algebra system MAGMA and employs Aschbacher's theorem to break the problem into several cases. The attached CD contains the code for the algorithm as well as several test cases which demonstrate the improvement over MAGMA's existing algorithm.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.