A Steiner triple system of order ν, denoted STS(ν), is said to be tricyclic if it admits an automorphism whose disjoint cyclic decomposition consists of three cycles. In this paper we give necessary and sufficient conditions for the existence of a tricyclic STS(ν) for several cases. We also pose conjectures concerning their existence in two remaining cases.

Philosophiae Doctor - PhD / A tactical con guration consists of a nite set V of points, a nite set B of blocks and an incidence relation between them, so that all blocks are incident with the same number k points, and all points are incident with the same number r of blocks (See [14] for example ). If v := jV j and b := jBj; then v; k; b; r are known as the parameters of the con guration. Counting incident point-block pairs, one sees that vr = bk: In this thesis, we generalize tactical con gurations on Steiner triple systems obtained from projective geometry. Our objects are subgeometries as blocks. These subgeometries are collected into systems and we study them as designs and graphs. Considered recursively is a further tactical con guration on some of the designs obtained and in what follows, we obtain similar structures as the Steiner triple systems from projective geometry. We also study these subgeometries as factorizations and examine the automorphism group of the new structures. These tactical con gurations at rst sight do not form interesting structures. However, as will be shown, they o er some level of intriguing symmetries. It will be shown that they inherit the automorphism group of the parent geometry.

In this paper we extend the study of Heffter arrays and the biembedding of graphs on orientable surfaces first discussed by Archdeacon in 2014. We begin with the definitions of Heffter systems, Heffter arrays, and their relationship to orientable biembeddings through current graphs. We then focus on two specific cases. We first prove the existence of embeddings for every K_(6n+1) with every edge on a face of size 3 and a face of size n. We next present partial results for biembedding K_(10n+1) with every edge on a face of size 5 and a face of size n. Finally, we address the more general question of ordering subsets of Z_n take away {0}. We conclude with some open conjectures and further explorations.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-09-16T12:52:36Z No. of bitstreams: 2 Dissertação EnioPerez.pdf: 2190954 bytes, checksum: 8abd6c2cd31279e28971c632f6ed378b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-09-16T14:10:30Z (GMT) No. of bitstreams: 2 Dissertação EnioPerez.pdf: 2190954 bytes, checksum: 8abd6c2cd31279e28971c632f6ed378b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-09-16T14:10:30Z (GMT). No. of bitstreams: 2 Dissertação EnioPerez.pdf: 2190954 bytes, checksum: 8abd6c2cd31279e28971c632f6ed378b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2011-08-26 / Intuitively, the basic idea of Design Theory consists of a way to select subsets, also called blocks, of a finite set, so that some properties are satisfied. The more general case are the blocks designs. A PBD is an ordered pair (S;B), where S is a finite set of symbols, and B is a collection of subsets of S called blocks, such that each pair of distinct elements of S occur together in exactly one block of B. A Steiner Triple System is a particular case of a PBD, where every block has size only 3, being called triples. The main focus is in building technology systems. By resolvability is discussed as a Steiner Triple Systems is resolvable, and when it is not resolvable. This theory has several applications, eg, embeddings and even problems related to computational complexity. / Intuitivamente, a idéia básica de um Planejamento Combinatório consiste em uma maneira de selecionar subconjuntos, também chamados de blocos, de um conjunto finito, de modo que algumas propriedades especificadas sejam satisfeitas. O caso mais geral são os planejamentos balanceados. Um PBD é um par ordenado (S;B), onde S é um conjunto finito de símbolos, e B é uma coleção de subconjuntos de S chamados blocos, tais que cada par de elementos distintos de S ocorrem juntos em exatamente um bloco de B. Um Sistema Triplo de Steiner é um caso particular de um PBD, em que todos os blocos tem tamanho único 3, sendo chamados de triplas. O foco principal está nas técnicas de construção dos sistemas. Por meio da resolubilidade se discute quando um Sistema Triplo de Steiner é resolvível e quando não é resolvível. Esta teoria possui várias aplicações, por exemplo: imersões e até mesmo problemas relacionados à complexidade computacional.

A critical set in a Latin square of order n is a set of entries in an n×n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n²-n. In Chapter 4, it is shown that lcs(n)<=n²-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders m×2^α (m odd, α>=2) and m×2^α+1 (m odd, α>=2 and α≠3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n²÷ 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

A critical set in a Latin square of order n is a set of entries in an n×n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n²-n. In Chapter 4, it is shown that lcs(n)<=n²-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders m×2^α (m odd, α>=2) and m×2^α+1 (m odd, α>=2 and α≠3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n²÷ 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

A critical set in a Latin square of order n is a set of entries in an n×n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n²-n. In Chapter 4, it is shown that lcs(n)<=n²-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders m×2^α (m odd, α>=2) and m×2^α+1 (m odd, α>=2 and α≠3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n²÷ 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

[pt] Algoritmos para a resolução de problemas de programação mista 0-1 gerais baseados em cortes derivados dos métodos lift-and-project, tem se mostrado bastante eficientes na prática. Estes cortes são gerados resolvendo um problema que depende de uma certa normalização. Desde um ponto de vista teórico, o bom comportamento destes algoritmos não foi completamente compreendido, especialmente no que diz respeito à normalização. Neste trabalho consideramos normalizações gerais definidas por um conjunto convexo fechado arbitrário, estendendo assim a análise teórica desenvolvida nos anos noventa. Apresentamos um marco teórico que abarca todas as normalizações previamente estudadas e introduzimos novas normalizações, analisando as propriedades dos cortes associados.Introduzimos também uma nova fórmula de atualização do parâmetro proximal para uma variante dos métodos de feixes. Estes métodos são bem conhecidos pela sua eficiência na resolução de problemas de otimização não diferenciável. Por último, propomos uma metodologia para eliminr soluções redundantes de programas inteiros combinatórios. Nossa proposta baseia-se na utilização da informação de simetria do problema, eliminam a simetria sem prejudicar a solução do problema inteiro. / [en] Algorithms for general 0-1 mixed integer programs can be successfully developed by using lift-and-project methods to generate cuts. Cuts are generated by solving a cut- generation-program that depends on a certain normalization. From a theoretical point of view, the good numerical behavior of these cuts is not completely understood yet, specially, concerning to the normalization chosen. We consider a general normalization given by an arbitrary closed convex set, extending the theory developed in the 90's. We present a theoretical framework covering a wide group of already known normalizations. We also introduce new normalizations and analyze the properties of the associated cuts. In this work, we also propose a new updating rule for the prox parameter of a variant of the proximal bundle methods, making use of all the information available at each iteration. Proximal bundle methods are well known for their efficiency in nondifferentiable optimization. Finally, we introduce a way to eliminate redundant solutions ( due to geometrical symmetries ) of combinatorial integer program. This can be done by using the information about the problem symmetry in order to generate inequalities, which added to the formulation of the problem, eliminate this symmetry without affecting solution of the integer problem. / [es] Los algoritmos para la resolución de problemas de programación mixta 0-1 generales que utilizan cortes derivados de los métodos lift-and-project, se han mostrado bastante eficientes en la práctica. Estos cortes se generan resolviendo un problema que depende de una cierta normalización. Desde el punto de vista teórico, el buen comportamiento de estos algoritmos no fue completamente comprendido, especialmente respecto a la normalización. En este trabajo consideramos normalizaciones generales definidas por un conjunto convexo cerrado arbitrario, extendiendo así el análisis teórico desarrollado en los años noventa. Presentamos un marco teórico que abarca todas las normalizaciones previamente estudiadas e introducimos nuevas normalizaciones, analizando las propiedades de los cortes asociados. Introducimos una nueva fórmula de actualización del parámetro de. Estoss métodos son bien conocidos por su eficiencia en la resolución de problemas de optimización no diferenciable. Por último, proponemos una metodología para eliminar soluciones redundantes de programas enteros combinatorios. Nuestra propuesta se basa en la utilización de la información de simetría del problema, eliminan la simetría sin perjudicar la solución del problema entero.