COMBINATORIAL ALGORITHMS GROUP

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca).
Date  Place  Time  Speaker  Abbreviated Title 

May 14  EOW 430  2:30  Mark Weston  More Fun with Symmetric Venn Diagrams 
Wed. May 26  Elliott 062  12:30  Wendy Myrvold  Parent/Child Generation of Combinatorial Objects 
Wed. June 9  EOW 430  3:00  Ruskey and Myrvold  SIAM Practice Day 
June 11  EOW 430  2:30  No CAG.  SIAM Discrete Math conference 
June 18  EOW 430  2:30  Sarah Carruthers  Connectivity of Wireless Sensor Networks with Constant Density 
Wed. June 23  EOW 430  12:30  Andrei Gagarin  ProjectivePlanar and Toroidal Graphs Avoiding K_{3,3}Subdivisions 
July 2  EOW 430  2:30  No CAG.  Canada Day Holiday 
August 6  EOW 430  2:30  Nate Kube  Foundations for Generating nReorders 
Aug. 12  Elliott 160  10:30am  Patrick Fowler  Current Density Maps  Direct Visualisation of Aromaticity 
Aug. 13  EOW 430  2:30  Patrick Fowler  Fullerenes: A Bridge between Mathematics and Chemistry. 
August 16  EOW 430  2:30  Elena Prieto  Looking at the Stars: Algorithms for Packing Stars in General Graphs 
Many researchers have had fun searching for and rendering symmetric Venn diagrams, culminating in the recent result of Griggs, Killian and Savage [``Venn Diagrams and Symmetric Chain Decompositions in the Boolean Lattice", Electronic Journal of Combinatorics, 11 (2004) R2], that symmetric Venn diagrams on n curves exist if and only if n is prime. Our purpose here is to point out ways to prolong the fun by introducing and finding the basic properties of Venn and nearVenn diagrams that satisfy relaxed notions of symmetry, while leaving tantalizing open problems. A symmetric Venn diagram is one that possesses a rotational symmetry in the plane. A monochrome symmetric Venn diagram is one that is rotationally symmetric when the colours of the curves are ignored. A necessary condition for the existence of a monochrome simple Venn diagram is that the number of curves be a prime power. We specify conditions under which all curves must be noncongruent and give examples of small visuallystriking monochrome symmetric Venn diagrams found by algorithmic searches. A Venn diagram partitions the plane into 2^{n} open regions. For nonprime n we also consider symmetric diagrams where the number of regions is as close to 2^{n} as possible, both larger and smaller.
This is a practise talk for a paper to be presented at Fun with Algorithms 2004 (which explains the title), in Tuscany, Italy, later in May. The talk will be 1/2 hour (a short CAG!!) as that is the time I have at the conference. Anyone who attended my thesis defence will recognize much of the material...
This is joint work with Frank Ruskey.
When making conjectures about combinatorial objects (e.g. graphs, trees, Latin squares, planar graphs) it is often helpful to have access to all of the small objects in the class. A standard tactic for generating exactly one object in each isomorphism class is a parent/child generation scheme. In this talk, we discuss the general methodology plus also computational techniques for making the generation process faster.
We consider the connectivity of a wireless sensor network in which each sensor is able to transmit within a disk of radius one. We show with elementary techniques that there exists a constant c such that if we throw cN sensors into an n by n square (of area N) independently at random, then with high probability there will be exactly one connected component which reaches all sides of the square. Its expected size is a constant fraction of the total number of sensors, and it covers a constant fraction of the area of the square. Furthermore, the other connected components of sensors and uncovered contiguous portions of the square are each very small (O(log^{2} n) and O(log N) respectively), so that their relative sizes grow smaller as N increases. This is joint work with Valerie King.
By Kuratowski's theorem, a nonplanar graph G contains a subdivision of K_{5} or K_{3,3}. Suppose that G contains a subdivision of K_{5}. We describe a lineartime algorithm which either reduces a projectiveplanaritychecking or toroidalitychecking algorithm to a small constant number of planarity tests, or finds a subdivision of K_{3,3} in G. The algorithm is based on the transformation of a fixed subdivision of K_{5} into a subdivision of K_{3,3} in G, or else, on the decomposition of G into smaller pieces. The approach uses the properties of a K_{5}subdivision and its embeddings in the projective plane and torus. It is easy to implement using a breadthfirst or depthfirst search (joint work with W.L. Kocay).
The algorithmic results show the structure of the corresponding projectiveplanar and toroidal graphs in terms of planar graphs. The structure can be used to prove Kuratowski type theorems for projectiveplanar and toroidal graphs with no K_{3,3}subdivisions (joint work with W. Myrvold).
The uniqueness of the decomposition gives a characterization of projectiveplanarity for graphs with no K_{3,3}subdivisions. A refinement of the structural results for the torus provides a characterization of toroidal graphs with no K_{3,3}subdivisions. The characterizations can be used to enumerate the corresponding projectiveplanar and toroidal graphs (labelled enumeration, joint work with P. Leroux and G. Labelle).
In computer networking, the ordered delivery of packets is a property of a successful transfer. Under "normal" conditions, packet order is not expected to change throughout a transmission. There are however several "abnormal" path specific properties that can force such an occurrence.
Assessing such reordering is important to applications such as voice over IP or any others requiring a realtime media stream. Numerous metrics exist for classifying the degree of reordering present in a stream. We will focus on one, the nreordering metric for its significance to TCP.
This talk will address early results and open problems involving the enumeration of the satisfying permutations for a given nreorder specification.
We will also look at 2 heuristical algorithms for generating satisfying permutations and discuss their use in reallife traffic shaping.
This talk is sponsored by the chemistry department, but CAG members are welcome to attend:
Hückel's venerable 4n+2 rule rests on the formal analogy between the pi orbitals of annulenes and the solutions of the problem of the particle moving freely on a circle. The implication that aromatic 4n+2 systems should support diatropic ring currents, and antiaromatic 4n systems paratropic ring currents has long been understood. With the advent of the ipsocentric method of calculation of induced current density, it has become possible to identify these currents in an ab initio calculation and to see that, in a precisely defined sense, exactly four of the 4n+2, and two of the 4n pi electrons are responsible for those currents.
Ring currents in cyclically delocalised systems are determined by symmetry and energy of orbitals at or close to the HOMO/LUMO frontier. The ipsocentric treatment of vector potential offers an accurate and economical ab initio treatment of magnetic response properties, visualisation in the form of readily interpreted current maps, and a simple and predictive orbital model incorporating symmetrybased rules for sense and magnitude of ring currents.
Applications to annulenes, distorted large annulenes, trannulenes, porphin macrocycles, clamped benzenes and cyclooctatetrenes, allmetal aromatics, aromatic transition states and many other systems will be used to show the utility and scope of the method.
This talk is geared towards our typical CAG audience:
Fullerene chemistry and physics is an area where twoway interaction between chemistry and mathematics is particularly strong. Some applications of graphs and their embeddings will be discussed for these chemically important carbon polyhedra, with emphasis on the variety of present results in chemistry and the future directions for joint chemicalmathematical exploration.
Systematics of fullerene physics and chemistry can be developed using a mixture of symmetry, combinatoric and graph theoretical arguments. Isomer counts, magic numbers in electronic structure, energetics and patterns of addition chemistry can all be understood with symmetry/graph theory based models.
Adjacency matrices and their eigenvalues partially characterise stability and reactivity of the unsaturated fullerene carbon frameworks, Other matrices are less well exploited in chemistry; eigenvectors of bondpolarisability matrices characterise the degree of distortivity of the framework; distance matrices, independence numbers and codes all model the addition chemistry of fullerenes. Qualitative relations between distance and adjacency spectra are observed, and constructions for specific `leapfrog' fullerenes suggest chemically relevant conjectures. Embeddings of fullerene and related graphs on 2D manifolds lead to electronicstructure rules for toroidal and more exotic fullerene analogues and to some chemically useful relations for mobius molecules.
The problem of packing k vertexdisjoint copies of a graph H into another graph G is NPcomplete if H has more than two vertices in some connected component. In the framework of parameterized complexity we analyze a particular family of instances of this problem, namely the packing of stars. We prove that packing k copies of H = K_{1,s} is in general fixedparameter tractable and give a quadratic kernel in the general case. When we consider the special case of H being a star with two leaves we give a linear kernel and an algorithm running in time O(2^{5.3k}).
This is joint work with Christian Sloper.