Ottawa-Carleton Discrete Math Day 2004
Saturday April 24, 2004
Past years homepages: DMD 2003, and DMD 2002.
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. 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 algorithms, combinatorial optimization, combinatorial enumeration and graph theory. They have been involved in theoretical, algorithmic and applied aspects of discrete mathematics. The Friday Colloquium will be given by a leader in combinatorial design theory.
The Ottawa-Carleton Discrete Math Day will be held in room SC 103 (Steacie Building), Carleton University on Saturday April 24, 2004. The Colloquium talk will be on Friday April 23 in HP 4351. There will be a reception at the end of the Discrete Math Day. This event is 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.
This year the Ontario Combinatorics Workshop will be in Kingston on May 6-7. Please contact Claude.Tardif@rmc.ca
Friday April 23, 2004
All activities are in HP 4351.
Saturday April 24, 2004
All talks and coffee breaks in SC 103 (Steacie Building).
The vertex enumeration problem is to take a system of linear inequalities defining a convex polyhedron and to output its vertices. The equivalent facet enumeration takes the vertices as input, and outputs a defining set of linear inequalities. In this talk I will begin by giving a few examples of vertex/facet enumeration problems from various fields. I will then describe the reverse search technique, developed with Komei Fukuda, that can be used to generate objects without repetition from loosely structured sets without the need to store the generated items. Finally I will show how this method is used to solve the vertex/facet enumeration problem, and give some empirical experience with its implementation as the lrs package.
The ability to determine through a small number of experiments which drugs have harmful or beneficial effects when used together, the ability receive pictures from outer space clearly, the ability to map the human genome even though some results are inconsistent, the ability to use digital cellphones, listen to cds or write to computer discs, all involve the use mathematical objects (highly structured finite sets) called combinatorial designs. In this lecture we will show the evolution of concept of a combinatorial design from its beginnings as a problem involving the Russian military in the 1700's in St Petersburg through to the present day. Except for some college algebra used in the last few minutes of the talk, no mathematics beyond high school is needed.
Prompted by a search for "natural" infinite automorphic graphs (i.e., graphs where every endomorphism is an automorphism) we present a survey of various properties of euclidean unit-distance graphs (real and rational) that are relevant to automorphicity.
It was known that Venn diagrams for -sets exist for all and that Venn diagrams with -fold rotational symmetry cannot exist unless is prime. But it was an open question whether symmetric Venn diagrams exist for all prime . We show this is always possible by exploiting some interesting properties of a well-known symmetric chain decomposition in the Boolean lattice.
This is joint work with Charles Killian and Jerrold Griggs.
This talk describes a start towards basic research on the analysis of graph algorithms, centered on an experimental study to analyze the performance of algorithms for finding a path from a source to a destination in a graph. Numerous elementary algorithms can find a path in time proportional to the number of edges in the graph, but there is significant room, in numerous natural graph models, for improving upon this performance. Specific open problems will be presented that address validating these results through analysis.
If you are planning to park your car on Carleton's campus on Friday April 23, 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 24.
(613) 520-2600 x2159
FAX: (613) 520-3536
University of Ottawa
(613) 562-5800 x3788
FAX: (613) 562-5776
This conference is supported by The Fields Institute for Research in Mathematical Sciences.