We consider combinatorial t-design problems as discrete optimization problems. Our motivation is that only a few studies have been done on the use of exact optimization techniques in designs, and that classical methods in design theory have still left many open existence questions. Roughly defined, t-designs are pairs of discrete sets that are related following some strict properties of size, balance, and replication. These highly structured relationships provide optimal solutions to a variety of problems in computer science like error-correcting codes, secure communications, network interconnection, design of hardware; and are applicable to other areas like statistics, scheduling, games, among others. We give a new approach to combinatorial t-designs that is useful in constructing t-designs by polyhedral methods. The first contribution of our work is a new result of equivalence of t-design problems with a graph theory problem. This equivalence leads to a novel integer programming formulation for t-designs, which we call GDP. We analyze the polyhedral properties of GDP and conclude, among other results, the associated polyhedron dimension. We generate new classes of valid inequalities to aim at approximating this integer program by a linear program that has the same optimal solution. Some new classes of valid inequalities are generated as Chv´atal-Gomory cuts, other classes are generated by graph complements and combinatorial arguments, and others are generated by the use of incidence substructures in a t-design. In particular, we found a class of valid inequalities that we call stable-set class that represents an alternative graph equivalence for the problem of finding a t-design. We analyze and give results on the strength of these new classes of valid inequalities. We propose a separation problem and give its integer programming formulation as a maximum (or minimum) edge-weight biclique subgraph problem. We implement a pure cutting-plane algorithm using one of the stronger classes of valid inequalities derived. Several instances of t-designs were solved efficiently by this algorithm at the root node of the search tree. Also, we implement a branch-and-cut algorithm and solve several instances of 2-designs trying different base formulations. Computational results are included.

This project deals with the automorphism group G of a Steiner system S (3, 4, 10). S₁₀, the symmetrical group of degree 10, acts transitively on T, the set of all Steiner systems with parameters 3, 4, 10. The purpose of this project is to study the action of S₁₀ on cosets of G. This will be achieved by means of a graph of S₁₀ on T x T. The orbits of S₁₀ on T x T are in one-one correspondence with the orbits of G, the stabilizer of an S [e] T on T.

Este trabalho é sobre as geométrias finitas com 3 ou 4 pontos na cada reta e os loops e qiasigrupos relacionados. Em caso de 3 pontos na cada reta descrevemos o loop de Steiner correspondente livre e calculamos o grupo de automorfismos em caso de 3 geradores livres. Além disso descrevemos os loopos de Steiner nilpotentes de clase dois e classificamos estes loopos com 3 geradores. Em caso de 4 pontos na cada reta construimos as geometrias novas atraves de expanção central de um análogo não comutativo do quasigrupo de Steiner. Temos fortes indícios que esta construção é universal em algum sentido. / This work is about finite geometries with 3 or 4 points on every line and related loops and quasigroups. In the case of 3 points on any line we describe the structure of free loops in the variety of corresponding Steiner loops and we calculate the group of automorphisms of free Steiner loop with three generators. We describe the structure of nilpotent class two Steiner loops and classifiy all such loops with three generators. In the case of 4 points on a line we constructe new series of such geometries as central extension of corresponding non-commutative Steiner quasigroups. We conjecture that those geometries are universal in some sense.

In 1992 Du and Hwang published a paper confirming the correctness of a well known 1968 conjecture of Gilbert and Pollak suggesting that the Euclidean Steiner ratio for the plane is 2/3. The original objective of this thesis was to adapt the technique used in this proof to obtain results for other Minkowski spaces. In an attempt to create a rigorous and complete version of the proof, some known results were given new proofs (results for hexagonal trees and for the rectilinear Steiner ratio) and some new results were obtained (on approximation of Steiner ratios and on transforming Steiner trees). The most surprising result, however, was the discovery of a fundamental gap in the proof of Du and Hwang. We give counter examples demonstrating that a statement made about inner spanning trees, which plays an important role in the proof, is not correct. There seems to be no simple way out of this dilemma, and whether the Gilbert-Pollak conjecture is true or not for any number of points seems once again to be an open question. Finally we consider the question of whether Du and Hwang's strategy can be used for cases where the number of points is restricted. After introducing some extra lemmas, we are able to show that the Gilbert-Pollak conjecture is true for 7 or fewer points. This is an improvement on the 1991 proof for 6 points of Rubinstein and Thomas. / Mathematical Sciences / Ph. D. (Mathematics)

In 1992 Du and Hwang published a paper confirming the correctness of a well known 1968 conjecture of Gilbert and Pollak suggesting that the Euclidean Steiner ratio for the plane is 2/3. The original objective of this thesis was to adapt the technique used in this proof to obtain results for other Minkowski spaces. In an attempt to create a rigorous and complete version of the proof, some known results were given new proofs (results for hexagonal trees and for the rectilinear Steiner ratio) and some new results were obtained (on approximation of Steiner ratios and on transforming Steiner trees). The most surprising result, however, was the discovery of a fundamental gap in the proof of Du and Hwang. We give counter examples demonstrating that a statement made about inner spanning trees, which plays an important role in the proof, is not correct. There seems to be no simple way out of this dilemma, and whether the Gilbert-Pollak conjecture is true or not for any number of points seems once again to be an open question. Finally we consider the question of whether Du and Hwang's strategy can be used for cases where the number of points is restricted. After introducing some extra lemmas, we are able to show that the Gilbert-Pollak conjecture is true for 7 or fewer points. This is an improvement on the 1991 proof for 6 points of Rubinstein and Thomas. / Mathematical Sciences / Ph. D. (Mathematics)