HIIT seminar, Friday Mar 19, 10:15 a.m. (coffee from 10), Exactum C222
Dr. Petteri Kaski
Helsinki Institute for Information Technology HIIT
Aalto University, Department of Information and Computer Science
The Cycle Switching Graph of the STS(19)s is Connected
Abstract:
In combinatorics, "switching" usually refers to a local transformation that is applied to a combinatorial object to produce an object with the same general structure. For example, a sequence of random switches is frequently applied to randomize an object. The present work studies "cycle switching" operations for Steiner triple systems using computational tools. We find that for order 19, all of the isomorphism classes are connected to each other by cycle switching.
In terms of algorithm engineering, this talk is about a specific computation establishing that an implicitly given graph with 11,084,874,829 vertices is connected.
Joint work with Veli Mäkinen and Patric Östergård.
Last updated on 19 Mar 2010 by Visa Noronen - Page created on 19 Mar 2010 by Visa Noronen