COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Summer 2004

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 2ⁿ open regions. For non-prime n we also consider symmetric diagrams where the number of regions is as close to 2ⁿ 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.

SIAM Practice Talk 1
Gray Codes for Polyominoes
Frank Ruskey

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

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² 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 non-planar graph G contains a subdivision of K₅ or K_3,3. Suppose that G contains a subdivision of K₅. 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 K_3,3 in G. The algorithm is based on the transformation of a fixed subdivision of K₅ 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₅-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 K_3,3-subdivisions (joint work with W. Myrvold).

The uniqueness of the decomposition gives a characterization of projective-planarity 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 projective-planar 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 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.

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.

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.

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 = K_1,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(2^5.3k).

This is joint work with Christian Sloper.