Ottawa-Carleton Discrete Math Day 2004 Saturday April 24, 2004 School of Mathematics and Statistics Carleton University

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

Program

Friday April 23, 2004
All activities are in HP 4351.

• 2:30 - 3:30: coffee break.
• Colloquium by Eric Mendelsohn (University of Toronto): ``The Evolution of Intelligent Designs''.
• We will suggest some possible restaurants for dinner.

Saturday April 24, 2004
All talks and coffee breaks in SC 103 (Steacie Building).

• 9:30 - 10:00 Coffee and registration (no fee).
• 10:00 - 11:00: David Avis (McGill University): ``All Meals for a dollar, Nash Equilibria, and other Vertex Enumeration Problems''.
• 11:00 - 11:30: coffee break.
• 11:30 - 12:30: Gert Sabidussi (Universite de Montreal): ``How well does the euclidean metric behave on rational points? (Some properties of euclidean unit-distance graphs)''.
• 12:30-1:00: Lunch at HP4351.
• 1:00-2:00: Walk to the falls.
• 2:15 - 3:15: Carla Savage (North Carolina State University): ``Venn Diagrams and Symmetric Chain Decompositions in the Boolean Lattice''.
• 3:15 - 3:45: coffee break.
• 3:45 - 4:45: Robert Sedgewick (Princeton University): ``Finding Paths in Graphs''.
• 5:00 - 8:00: reception in 20th floor Dunton Tower Lounge.

Titles and abstracts of talks

• David Avis (McGill University):
  ``All Meals for a dollar, Nash Equilibria, and other Vertex Enumeration Problems''.
  

  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.

• Eric Mendelsohn (University of Toronto):
  ``The Evolution of Intelligent Designs''.
  

  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.

• Gert Sabidussi (Universite de Montreal):
  ``How well does the euclidean metric behave on rational points? (Some properties of euclidean unit-distance graphs)''.
  

  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.

• Carla Savage (North Carolina State University):
  ``Venn Diagrams and Symmetric Chain Decompositions in the Boolean Lattice''.
  A Venn diagram for sets is a collection of simple closed curves in the plane, , with the property that for each the region
  
  
  
  
  is nonempty and connected.

  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.

• Robert Sedgewick (Princeton University):
  ``Finding Paths in Graphs''.
  

  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.

Accommodation

• Bed and Breakfast:
  • A Rose on Colonel By, 9 Rosedale Avenue, Ottawa, K1S 4T2,
    Phone : (613) 291-7831.
  • By-the-Way, 310 First Avenue, Ottawa, K1S 2G8,
    Fax/Phone: (613) 232-6840.
  • By-the-Pond, 18 Wilton Crescent, Ottawa, K1S 2T5,
    Phone: (613) 236-5693; Fax: (613) 236-9302.
• Hotel: for hotel accomomodations see http://www.ottawatourism.ca/english/accommodations/accomodations.cfm.

Parking

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.

Organizers

Contacts

Daniel Panario  Carleton University  (613) 520-2600 x2159  FAX: (613) 520-3536  daniel@math.carleton.ca

Mateja Sajna  University of Ottawa  (613) 562-5800 x3788  FAX: (613) 562-5776  msajna@uottawa.ca

This conference is supported by The Fields Institute for Research in Mathematical Sciences.

Address