CAG Schedule of Talks: Summer 2004

Schedule of Talks: Summer 2004

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (

Schedule for Talks:

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 Projective-Planar and Toroidal Graphs Avoiding K3,3-Subdivisions
July 2 EOW 430 2:30 No CAG. Canada Day Holiday
August 6 EOW 430 2:30 Nate Kube Foundations for Generating n-Reorders
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

Previous Talks:

More Fun with Symmetric Venn Diagrams
Mark Weston
Friday May 14, 2:30, EOW 430

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 near-Venn 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 non-congruent and give examples of small visually-striking monochrome symmetric Venn diagrams found by algorithmic searches. A Venn diagram partitions the plane into 2n open regions. For non-prime n we also consider symmetric diagrams where the number of regions is as close to 2n 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.

Parent/Child Generation of Combinatorial Objects
Wendy Myrvold
Wednesday May 26, 12:30, Elliott 062

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.

SIAM Practice Day
Wed. June 9, 3:00, EOW 430

SIAM Practice Talk 1
Gray Codes for Polyominoes
Frank Ruskey

We show various results (and open problems) about the exhaustive enumeration of column convex polyominoes where successive polyominoes differ by a small amount. [Joint research with Stirling Chow.]

SIAM Practice Talk 2
Parent/Child Generation of Combinatorial Objects
Wendy Myrvold

This talk will be a much shorter version of the talk described

Connectivity of Wireless Sensor Networks with Constant Density
Sarah Carruthers
Friday June 18, 2:30, EOW 430

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(log2 n) and O(log N) respectively), so that their relative sizes grow smaller as N increases. This is joint work with Valerie King.

Projective-Planar and Toroidal Graphs Avoiding K3,3-Subdivisions: Detection, Forbidden Minors and Enumeration
Andrei Gagarin
Laboratoire de Combinatoire et d'Informatique Mathématique
Université du Québec à Montréal
Wed. June 23, 12:30, EOW 430

By Kuratowski's theorem, a non-planar graph G contains a subdivision of K5 or K3,3. Suppose that G contains a subdivision of K5. We describe a linear-time algorithm which either reduces a projective-planarity-checking or toroidality-checking algorithm to a small constant number of planarity tests, or finds a subdivision of K3,3 in G. The algorithm is based on the transformation of a fixed subdivision of K5 into a subdivision of K3,3 in G, or else, on the decomposition of G into smaller pieces. The approach uses the properties of a K5-subdivision and its embeddings in the projective plane and torus. It is easy to implement using a breadth-first or depth-first search (joint work with W.L. Kocay).

The algorithmic results show the structure of the corresponding projective-planar and toroidal graphs in terms of planar graphs. The structure can be used to prove Kuratowski type theorems for projective-planar and toroidal graphs with no K3,3-subdivisions (joint work with W. Myrvold).

The uniqueness of the decomposition gives a characterization of projective-planarity for graphs with no K3,3-subdivisions. A refinement of the structural results for the torus provides a characterization of toroidal graphs with no K3,3-subdivisions. The characterizations can be used to enumerate the corresponding projective-planar and toroidal graphs (labelled enumeration, joint work with P. Leroux and G. Labelle).

Foundations for Generating n-Reorders
Nate Kube
Friday August 6, 2:30, EOW 430

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 real-time media stream. Numerous metrics exist for classifying the degree of reordering present in a stream. We will focus on one, the n-reordering 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 n-reorder specification.

We will also look at 2 heuristical algorithms for generating satisfying permutations and discuss their use in real-life traffic shaping.

This talk is sponsored by the chemistry department, but CAG members are welcome to attend:

Current Density Maps - Direct Visualisation of Aromaticity
Patrick Fowler
Dept. of Chemistry, University of Exeter
Thursday August 12, 10:30am, Elliott 160

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 symmetry-based rules for sense and magnitude of ring currents.

Applications to annulenes, distorted large annulenes, trannulenes, porphin macrocycles, clamped benzenes and cyclo-octatetrenes, all-metal 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:

Fullerenes: A Bridge between Mathematics and Chemistry.
Patrick Fowler
Dept. of Chemistry, University of Exeter
Friday August 13, 2:30, EOW 430

Fullerene chemistry and physics is an area where two-way 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 chemical-mathematical 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 bond-polarisability 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 electronic-structure rules for toroidal and more exotic fullerene analogues and to some chemically useful relations for mobius molecules.

Looking at the Stars: Algorithms for Packing Stars in General Graphs
Elena Prieto
Monday August 16, 2:30, EOW 430

The problem of packing k vertex-disjoint copies of a graph H into another graph G is NP-complete 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 = K1,s is in general fixed-parameter 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(25.3k).

This is joint work with Christian Sloper.

CAG Schedule of Talks: Summer 2004 / maintained by Wendy Myrvold / / revised June 10, 2004