Ottawa-Carleton Discrete Math Day 2002
Saturday April 13, 2002
NEW: photographs of the event.
The Ottawa-Carleton Discrete Math Day is held annually in the Spring. It location alternates between Carleton University and University of Ottawa. It is a continuation of the Carleton Discrete Math Day held since 1978 at Carleton University. The meeting format consists of 4 lectures by leading researchers covering a broad range of topics in Discrete Mathematics and presented during one day. This year in addition to these talks, there is a related Colloquium talk on the Friday before the Discrete Math Day.
The objective of the meeting is to gather researchers, postdocs and graduate students in various fields of Discrete Mathematics during one weekend in order to stimulate research collaboration in this vibrant and inter-disciplinary area.
Discrete Mathematics is a broad area involving the study of the properties, algorithms and applications of mathematical structures built on discrete objects. This year's speakers for the Discrete Mathematics Day conduct research in the areas of combinatorial designs, combinatorial optimization, semidefinite programming, and combinatorial enumeration. They have been involved in theoretical, algorithmic and applied aspects of discrete mathematics. The Friday Colloquium will be given by a leader in probabilistic analysis of algorithms.
The Ottawa-Carleton Discrete Math Day will be held in room HP 3120 of the Herzberg Laboratories, Carleton University on Saturday April 13, 2002. The Colloquium talk will be on Friday April 12 in HP 4351. There will be a reception at the end of the Discrete Math Day. This event is partially sponsored by the Fields Institute.
Information regarding the schedule of talks, the list of titles and abstracts of talks, accommodation, parking is below.
It would be very helpful if you would let the organizers know if you plan to attend. Please forward this webpage link to any colleagues and students who might be interested.
Friday April 12, 2002
All activities are in HP 4351.
Saturday April 13, 2002
All talks and coffee breaks in HP 3120.
We revisit tries (digital trees) from several perspectives. Topics include universal laws of large numbers for trie parameters, partial match, and level compaction.
Two Steiner triple systems (STS) are said to be orthogonal if their sets of triples are disjoint, and two disjoint pairs of points defining intersecting triples in one system fail to do so in the other. The notion of orthogonal STS (OSTS) was first introduced by O'Shaughnessey in 1968 and he provided several small examples at that time. It was not until 1994 that it was proven that a pair of OSTS of order $v$ exist if and only if $v \equiv 1,3$ (mod 6) with $v \geq 7$ ($v \neq 9$), completely settling the existence problem for OSTS.
In this talk we will we consider the quantity $\sigma(v)$, the size of a maximum collection of pairwise orthogonal STS of order $v$. So the result mentioned above says that $\sigma(v) \geq 2$ for all $v \equiv 1,3$ (mod 6) with $v \geq 7$ ($v \neq 9$). We will give constructions in finite fields for improving this lower bound on $\sigma(v)$ and will also discuss hill-climbing algorithms used to improve this bound for many orders.
Finally we will prove that $\sigma(v) \geq 3$ for all $v \equiv 1,3$ (mod 6) $v \geq 19$ for all but a small number of possible exceptions.
Cutting plane methods are well established as effective tools for solving many classes of integer programming problems, including Traveling Salesman Problems and Vehicle Routing Problems. The key to their success is the creation of effective cuts which can be introduced to eliminate infeasible solutions. We discuss two new approaches. The first, developed by Applegate, Bixby, Cook and Chvatal automatically generates "unstructured" cuts which have proven to be very effective in practice. The second class, jointly developed with Ralphs, Kopman and Trotter, uses convex decompositions of fractional solutions to find violated structured cuts, and is particularly suited to parallel computers.
The recent development of efficient interior-point algorithms for convex optimization problems involving linear matrix inequalities (LMIs) has spurred research in a wide variety of application fields, including control system analysis and synthesis, combinatorial optimization, circuit design, structural optimization, experiment design, and geometrical problems involving elipsoidal bounding and approximation.
In the first part of the talk, I will describe the basic properties of semidefinite programming and linear matrix inequalities, and give a brief description of interior-point methods for their solution. In the second half of the talk I will survey several applications, including recent applications in statistical estimation and detection.
Euler's original discovery that the number of partitions of an integer into distinct parts is equal to the number into odd parts, has been extended, in a series of papers beginning in the 1980's, to a very general algorithm which will produce, on demand, a bijective mapping between two equinumerous families of integer partitions, or other combinatorial objects. We will survey some of the main developments of this stream of ideas, due to Garsia-Milne, Remmel, Gordon, O'Hara, myself, and others, and discuss the increased scope of our understanding of partitions that has resulted from them.
If you are planning to park your car on Carleton's campus on Friday April 12, please e-mail one of the organizers for a parking permit well in advance of the conference. You should park in one of the ``pay and display'' parking lots (lots P2 and P6) with your permit displayed. Otherwise, you will have to pay. A map of the campus can be found at http://www.carleton.ca/cu/campus/. Parking is free on Saturday April 13.