COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Spring 2007

Matroids are everywhere. Vector spaces are matroids. Matroids are useful in situations that are modelled by both graphs and matrices. Bicircular matroids model generalized network flow problems whose algorithms are more efficient than those available for general linear programming codes.

Let G be a graph (loops and parallel edges allowed) with vertex set V={1,2,...,n} and edge set E. In the classical matroid associated with a graph, a set of edges is independent in the matroid if it contains no cycles, and the circuits of the matroid are the single cycles of G. The bicircular matroid of G is the matroid B(G) defined on E whose circuits are the subgraphs which are subdivisions of one of the graphs:
(i) two loops on the same vertex,
(ii) two loops joined by an edge,
(iii) three edges joining the same pair of vertices.

The bicircular matroid is known to be a transversal matroid and thus can be represented by a family of sets, called a presentation. Given a transversal matroid, we can determine whether it is bicircular. I will show that, given any presentation of a bicircular matroid, we can find a graph representing the matroid, and that, in some cases, there is more than one graph. We investigate how the graphs representing a bicircular matroid are related, and what this means in terms of their presentations as transversal matroids.

Sorting a list of items is perhaps the most celebrated problem in computer science. If one must do this by swapping neighboring pairs, the worst initial condition is when the n items are in reverse order, in which case n choose 2 swaps are needed. A sorting network is any sequence of n choose 2 swaps which achieves this.

We investigate the behavior of a uniformly random n-item sorting network as n->infinity. We prove a law of large numbers for the space-time process of swaps. Exact simulations and heuristic arguments have led us to astonishing conjectures. For example, the half-time permutation matrix appears to be circularly symmetric, while the trajectories of individual items appear to converge to a famous family of smooth curves. We prove the more modest results that, asymptotically, the support of the matrix lies within a certain octagon, while the trajectories are Holder-1/2. A key tool is a connection with Young tableaux.

Consider a maximum-length binary shift-register sequence generated by a primitive polynomial f of degree m. Let C_n^f denote the set of all subintervals of this sequence with length n, where m < n <= 2m, together with the zero vector of length n. Munemasa [MR1640769] considered the case in which the polynomial f generating the sequence is a trinomial satisfying certain conditions. He proved that, in this case, C_n^f corresponds to an orthogonal array of strength 2 that has a property very close to being an orthogonal array of strength 3. Munemasa's result was based on his proof that very few trinomials of degree at most 2m are divisible by the given trinomial f. In this talk, we consider the case in which the sequence is generated by a pentanomial f satisfying certain conditions. Our main result is that no trinomial of degree at most 2m is divisible by the given pentanomial f, provided that f is not in a finite list of exceptions we give. As a corollary, we get that, in this case, C_n^f corresponds to an orthogonal array of strength 3. This effectively minimizes the skew of the Hamming weight distribution of subsequences in the shift-register sequence.

We provide a coupling proof that the transposition shuffle on a deck of n cards is mixing of rate n\log(n) with a moderate constant. This has already been shown by Diaconis and Shahshahani but no natural coupling proof has been demonstrated to date. We also enlarge the methodology of coupling to include intuitive but nonadapted coupling rules, for example, to take in account future events and to prepare for their occurrence. This is joint work with R.Burton)

The Erdos-Renyi random graph G(n,p) is the probability measure on all graphs on the vertex set [n]={1,2,...n}, with each edge inserted independently with probability p. Usually p is defined to be a function of n, and one asks whether a graph in G(n,p) is likely to have some (monotone) property as n goes to infinity. In their seminal 1959 paper, Erdos and Renyi showed that if p << log(n)/n then G(n,p) is almost always disconnected, but if p >> log(n)/n, then it is almost always connected. We view this as a topological statement and seek two-dimensional analogues of the Erdos-Renyi Theorem. We construct a measure on two-dimensional simplicial complexes and look at two questions about phase transitions for topological properties. For which values of p is the random complex almost always simply connected, and for which values of p does the random complex almost always have trivial homology? This is based on joint work with Matt Kahle and Eric Babson.

It is rather easy to triangulate a simple n-gon even under some optimization criterion, such as maximization of the smallest internal angle. A problem we consider in this talk is just a simple extension. Given a simple polygon P and one point p in its interior, we can again find an optimal triangulation maximizing the smallest internal angle just by applying a constrained Delaunay triangulation algorithm. We can associate the smallest angle with the point p. Now, our problem is to find a point that optimizes the evaluation. It looks easy, but no straightforward dynamic programming works. We present a polynomial-time algorithm for the problem. We also show that the result can be extended to a problem of finding where to insert two points to optimize the resulting triangulation in polynomial time in n. A practical heuristic approach called Pixel method is also presented.

This is joint work with Boris Aronov and Stefan Funke.

This talk will survey recent results on convergence to approximate solutions in games. For potential games in which a sequence of best-responses converge to a pure Nash equilibrium, we study the speed of convergence to efficient solutions in three classes of congestion games, selfish scheduling games, and cut games. For non-potential games, we introduce sink equilibria based on the convergence of the best-response moves of players and study the properties of this equilibrium concept. The talk is mainly based on three papers in this area co-authored with A. Vetta, M. Goemans, G. Christodoulou, and A. Sidiroupolous.

The large volume surveillance problem is characterised by the employment of mobile and fixed surveillance assets to a large geographic area in order to identify, assess and track the maximum number of moving, stopped or drifting objects. The observed objects are not necessarily aware of being observed and are cooperative or non-cooperative and friendly or hostile. Coastal and Arctic surveillance are good examples of large volume surveillance. The scarce surveillance and tracking capabilities (e.g. sensors) makes it very difficult to perform large volume surveillance and to keep tracking all activities. The question is therefore how to improve employment of a set of surveillance and patrolling assets, their networking capabilities and fusion engines in order to address large volume surveillance challenges.

This project assumes that available Intelligence, Surveillance and Reconnaissance (ISR) platforms include the long range patrol aircrafts (CP-140), Canadian Forces warships (Frigate and Coastal Patrol Ship), Helicopters, Unmanned Aerial Vehicles (UAVs), CoastGuard ships, Fishery and Ocean, RCMP and other Government departments (OGDs) surveillance resources. These resources have multiple networking capabilities allowing them to exchange information. The volume to be surveyed is very large, thus deploying all the resources will not guarantee full and seamless coverage at all times. At any given time there are many observable dynamic and static objects traveling in that volume. These objects have different characteristics and behaviours. They might appear during an interval of time in the surveyed volume (entrance and exit time windows). A priori information includes identification of a sub-set of these objects and possible intelligence reports about specific behaviours to be identified.

This NSERC-Industry funded project proposes to use distributed information fusion algorithms coupled with decision support tools to address the issues of large volume coastal surveillance. In particular, adaptive fusion, dynamic resource allocation, and configurable network management are combined to form a unique distributed information fusion approach. Tasks will be naturally determined or dynamically allocated as a result of an outcome or changes in current status. The project can be used to pioneer research in the strategic direction of large volume surveillance. It also fills the niche of Canadian needs in the defence, security and information industries for a more autonomous surveillance system.

In this presentation, the project, its motivations and the work plan are discussed. Some initial results are also presented.

About the speaker:

Dr. A. Guitouni is a defence scientist with Defence R&D Canada- Valcartier and Atlantic since 1998. He is specialised in the domain of decision support systems, operational research and artificial intelligence. His work includes planning and optimisation, automated classification, decision analysis, multiple criteria decision aids, net-enabled dynamic resource management, and collaborative decision making (planning). He is an adjunct professor with Laval University, Sherbrooke University, Concordia University and University of Victoria. He has supervised Ph.D., M.Sc. and MBA students.