**Combinatorics**

**
MA 216, Spring 2005**

Announcements

5/12/05 Final grades have been posted. Good work all!! PS--cool planarity link: http://www.addictinggames.com/planarity.html

5/6/06 Chpt 5 homeworks are graded--please come by my office first thing on Monday to pick them up. There seem to be a couple from the end of chpt 5 missing--please check for yours! Grades are posted, with everything up-to-date except the special topics. PS--someone seems to left their book in my office...

5/6/06 Overheads from Alice Dean's talk: AliceDeanUBVGs.pdf 4/28/05 Date: Thursday, 05/05/05

Time: 3:30 – 4:30 p.m.

Location: SMC Campus, Jeanmarie 362

Title: Characterizations of Unit-Bar Visibility Graphs

Speaker: Alice Dean, Department of Mathematics and Computer Science, Skidmore College

Abstract:

Representations of graphs using horizontal bars for vertices and vertical visibilities for edges have been studied since the mid 1980s, motivated by applications to circuit design and display of data. Graphs that can be represented in this way have been fully characterized, but the bar lengths may differ by impractical amounts. I consider graphs that can be represented using bars all of equal length. These graphs, called

unit-bar visibility graphs(orUBVGs), have not been fully characterized. I will discuss results for several classes of graphs, including trees and outerplanar graphs. The final result is a characterization of thetriangulated polygons(TPs) that are UBVGs. The characterization uses a character string associated with each TP to determine if a UBV layout exists and if so, to produce such a layout.4/14/05 Mark your calendar: There will be another speaker, Alice Dean, coming on Thursday, May 5, 3:30 to 4:30, Title to be announced. This talk is not required, but is recommended. You may use it instead of the John Schmitt talk if you missed that one. You may use it on the final in the same way as one of the inclass special topic presentations if you wish. If you did already turn in write ups on the other speakers, you may turn in a write up on this talk for a little extra credit (but can't get both extra credit and use it for your final exam). 4/7/05 Final Exam--Due in my office by 11:30, Thursday, May 12. 4/1/05 Required Talk--Date: Thursday, 4/7/05

Time: 3:30 – 4:30 p.m.

Location: SMC Campus, JEM 362

Title: A Problem in Extremal Graph Theory

Speaker: John Schmidt, Department of Mathematics, Emory University

Abstract:

Graphs have proven to be a very important mathematical model. For example, computer or telephone networks can be viewed as graphs. Often, one would like to build a graph that has a certain property. A natural question then arises:

"How much does one have to spend to build the graph with the desired property?"

We will discuss such a question as asked by Paul Erdos and its solution.

No previous knowledge of graph theory is assumed.

3/16/05 Some of your books may have a typo on page 117, second line--make sure it says "also entry c_21 must be ..." and not c_12. 3/1/05 Here is the midterm, due 3/24. 3/1/05 REQUIRED TALKS--There will be guest speakers during class time for the week of March 7, one on Tuesday and one on Thursday. There is no homework this week (good time to work on the midterm), but you must write up 2 paragraphs on each talk and turn those in the Tuesday after break. It is possible that a question from either or both of these talks will appear on the final, so engage in conversation with the speakers until you understand what they are presenting.3/1/05 EXTRA CREDIT TALK--Extra credit is available for attending this talk. As usual, write up and turn in 2 paragraphs about the talk (due the Tuesday after break) for credit. This is a very entertaining and easy to understand speaker.2/25/05 Grades to date have been posted. See me for your code or if you have any questions. 2/25/05 A note about both special topic and original research papers-- you MUST look beyond the internet! While the internet is a great place to get started, and to get a good quick idea of what you are working on, it is highly unreliable, especially for rigorous mathematical proofs. You MUST use other sources, in particular published and reviewed sources such as journal articles. MathSciNet is a good resourse. 2/17/05 NASA Space Grant Scholarship (or see http://www.emba.uvm.edu/VSGC/scholarship.htmfor the application form)2/14/05 Happy Valentine's Day! 2/10/05 Is there any interest in Tatoos for Pi-Day? (3/14). We could probably get the department to order us some. Let me know ASAP. http://www.math.pepperdine.edu/~kkillpat/Mathevents/PiDay2005-proof.pdf 2/9/05 The date of the required talk has been changed to next week--2/17/05, and the extra credit talk has also been changed to next week--2/18/05. 2/7/05

Extra Credit talk:A Second David Wood Talk!! He will be speaking at the UVM Math department colloquium this week as well as in the combo seminar. The colloquium talk is aimed at a general audience and should be quite accessible--a great source for special topics/open questions.Date: 2/11/05--

(Changed to 2/18/05)Time: 4:00 – 5:00 p.m.

Location: 004 Kalkin, UVM Campus

Title: Drawing of Graphs in Two and Three Dimensions

2/3/05 REQUIRED TALK

Date:2/10/05(Changed to 2/17/05)

Time:4:00 – 5:00 p.m.

Location:Farrell Room (St. Edmunds, Room 315), St. Michael’s College

Title:Fast Separation in Graphs with an Excluded Minor

Speaker:David Wood, McGill University, Montreal

For more info: AbstractTalk overheads: DavidWood-Separators.pdf2/2/05 The calendar has been updated--please check your due dates to be sure you are current. 2/1/05 Mark your calendar! The first of the required talks will be given by David Wood of McGill University on graph drawing algorithms. It will be here at SMC (room TBA), on Thursday, February 10th probably from 4 to 5 pm. You need to make arrangements with me asap if you are unable to attend at this time. There will be a second talk, less technical, at UVM on Friday, February 11, also from 4 to 5. Extra credit is available for attending this. These talks are excellent sources for special topics/open questions. 2/1/05 Please add 8b to the homework for 2.2 2/1/05 The room for the Monday night previews has been changed to JEM 366. 2/1/05 Another source of special topics/open problems, especially folks interested in engineering applications and/or computer algorithsm is: http://www.cs.sunysb.edu/~algorith/ The SMC library has the book Algorithm Design Manual. One of the things I like about this book is that he give specific examples of how he has used these algorithms and graph theoretical approaches for specific industry applications. 1/27/05 Cynthia Kelley's tips ‘n tricks in PPT 1/25/05 Slight change on the calendar--switched April 21 and 28 events. 1/25/05 I sent an email at the start of the semester asking for people's schedules--I do need this from every one ASAP please!! No later than class tomorrow. 1/24/05 'rought draft' means a rough draft in power point, not on paper (except for the rough draft of the special topics paper obviously). 1/20/05 A1 and B1, please check the calendar for updated special topics dates--I realized that the original calendar didn't give enough time to prepare. 1/19/05 Here is one set of 'professional dress guidelines': http://amdt.wsu.edu/research/dti/General_Guidelines.html 1/19/05 You may order a personal copy of Maple 9.5 at a discounted price of $75 if you wish: Secure ordering address: http://webstore.maplesoft.com. TheNEWPromotion Code is: AD7229 Course Name: Math 109 Ellis-Monag AD7236 Course Name: Math 216 Ellis-Monag1/12/03 The postings on this site have all been tested and all work. If you have any difficulty getting material off this site, you can try any of the following: 1. See if someone in your study group was able to print the file you want and make a photocopy of it.

2. Try using one of the lab computers in case the problem is with how your own computer is configured.

3. Using Explorer, right click on the link, select "save target as", then save the file to your home computer. You should be able to open and print it from there.

4. Contact Cynthia Kelley at 654-2756 or ckelley2@smcvt.edu. She is the person for website trouble shooting.