Search

This report documents the program and the outcomes of Dagstuhl Seminar 23161 "Pushing the Limits of Computational Combinatorial Constructions". In this Dagstuhl Seminar, we focused on computational methods for challenging problems in combinatorial construction. This includes algorithms for construction of combinatorial objects with prescribed symmetry, for isomorph-free exhaustive generation, and for combinatorial search. Examples of specific algorithmic techniques are tactical decomposition, the Kramer-Mesner method, algebraic methods, graph isomorphism software, isomorph-free generation, clique-finding methods, heuristic search, SAT solvers, and combinatorial optimization. There was an emphasis on problems involving graphs, designs and codes, also including topics in related fields such as finite geometry, graph decomposition, Hadamard matrices, Latin squares, and q-analogs of designs and codes.

A normal rational curve of the (k-1) -dimensional projective space over Fq is an arc of size q+1 , since any k points of the curve span the whole space. In this paper, we will prove that if q is odd, then a subset of size 3k-6 of a normal rational curve cannot be extended to an arc of size q+2 . In fact, we prove something slightly stronger. Suppose that q is odd and E is a (2k-3) -subset of an arc G of size 3k-6 . If G projects to a subset of a conic from every (k-3) -subset of E , then G cannot be extended to an arc of size q+2 . Stated in terms of error-correcting codes we prove that a k -dimensional linear maximum distance separable code of length 3k-6 over a field Fq of odd characteristic, which can be extended to a Reed–Solomon code of length q+1 , cannot be extended to a linear maximum distance separable code of length q+2 ., Postprint (updated version)

Summary: Every transitive permutation representation of a finite group is the representation of the group in its action on the cosets of a particular subgroup of the group. The group has a certain rank for each of these representations. We first find almost all rank-3 and rank-4 transitive representations of the projective special linear group P SL(2, q) where q = pm and p is an odd prime. We also determine the rank of P SL (2, p) in terms of p on the cosets of particular given subgroups. We then investigate the construction of rank-3 transitive and primitive extensions of a simple group, such that the extension group formed is also simple. In the latter context we present a new, group theoretic construction of the famous Hoffman-Singleton graph as a rank-3 graph., 2015, Includes bibliography., Degree granted: Dissertation (Ph.D.)--Florida Atlantic University, 2015, Collection: FAU Electronic Theses and Dissertations Collection

Summary: In this dissertation, we study some open problems concerning the existence or non-existence of some combinatorial designs. We give the construction or proof of non-existence of some Steiner systems, large sets of designs, and graph designs, with prescribed automorphism groups., by Emre Kolotoæglu., Thesis (Ph.D.)--Florida Atlantic University, 2013., Includes bibliography., Mode of access: World Wide Web., System requirements: Adobe Reader.

Triple factorisations of groups G of the form G = ABA, for proper subgroups A and B, are fundamental in the study of Lie type groups, as well as in geometry. This thesis is devoted to investigating such factorisations in the context of (permutation) group theory and geometry. Here, we rst introduce and develop a general framework for studying triple factorisations of this form for nite groups, especially nondegenerate ones where G 6= AB. We identify two necessary and su cient conditions called the Geometric and Restricted Movement Criteria for subgroups A;B to satisfy G = ABA, in terms of the G-actions on the A-cosets and the B-cosets. This leads to an order (upper) bound for jGj in terms of jAj and jBj which is sharp precisely for the point-line incidence geometries of ag-transitive projective planes. We study in particular triple factorisations where G acts imprimitively on the A-cosets, inducing a permutation group that is naturally embedded in a wreath product G0 oG1. This gives rise to triple factorisations T0; T1; T0 oT1 for G0;G1 and G0 oG1, respectively. We present a rationale for further study of triple factorisations G = ABA in which A is maximal in G, and both A and B are core-free. Geometrically, triple factorisations correspond to ag-transitive point-line incidence geometries in which `each pair of points is incident with at least one line'. We call such rank 2 geometries collinearly connected spaces. Duality gives rise to the notion of a concurrently connected space in which `each pair of lines is incident with at least one point'., An important part of this thesis is devoted to studying triple factorisations of general linear groups and their associated geometries which arise from parabolic subgroups. Here we investigate triple factorisations T = (G; A;B) of general linear groups G = GL(V ) with one of A and B either parabolic, or the stabiliser of a decomposition V = V1 V2. These investigations also give rise to various important examples of ag-transitive collinearly (respectively, concurrently) connected spaces. As duality is important in geometry, we also investigate the concurrent connectivity of the rank 2 geometries associated with triple factorisations T 0 = (G;B;A). These results lead to the conditions under which these new rank 2 geometries are collinearly and/or concurrently connected, or equivalently, G = ABA and/or G = BAB, respectively., Thesis (Ph.D.)--University of Western Australia, 2011