================================================================= SIAM Activity group on Discrete Mathematics DM-Net ----------------------------------------------------------------- June 17, 2009 (Number 2009.04) ----------------------------------------------------------------- Email contributions to: Address changes to: Archive URL: ================================================================= ================================================================= CONTENTS: 1. Editor's Note 2. Nominations solicited for SIAGDM Officers 3. Nominations solicited for 2010 Konig Prize 4. Announcement of SIAM DM10 - Austin, TX, June 14-17, 2010 5. Travel support for SODA10 now available 6. In Memory of Michael O. Albertson, 1946 - 2009 ================================================================= 1. *** Editor's Note *** ------ This edition is dedicated to the memory of Mike Albertson whom we lost this year to cancer. Joan Hutchinson has written a tribute which is below. This tribute, along with the references, can be found at http://orion.math.iastate.edu/rymartin/MOASIAM.pdf The 17th International Symposium on Graph Drawing is in Chicago, IL, Sept. 22-25, 2009: http://www.cdm.depaul.edu/gd2009 Keep sending your announcements of interest to the discrete mathematics community to dm-net@siam.org. The URL for the newsletter archive is http://orion.math.iastate.edu/rymartin/dm-net.html -- Ryan Martin ================================================================= 2. *** Nominations solicited for SIAGDM Officers *** ------ The term of the current officers of the SIAM Activity Group on Discrete Mathematics is up at the end of 2009. Nominations are solicited for officers for 2010-2012. "There shall be a chairperson, vice-chairperson, secretary, and program director, all of whom shall be regular members in good standing of the SIAG. The SIAG shall hold an election to fill those offices every two years." Nominating Committee: Glenn Hurlbert, Mark Kayll (chair), Lorna Stewart, Ann Trenk Please send nominations to the chair of the committee: Mark Kayll mark.kayll@umontana.edu Deadline: July 31, 2009 ================================================================= 3. *** Nominations solicited for 2010 Konig Prize *** ------ http://www.siam.org/prizes/sponsored/konig.php Nominations are open for the 2010 Denes Konig Prize. Prize committee: Noga Alon, Bill Cook, Pavol Hell, Bojan Mohar (Chair), Eva Tardos The SIAM Activity Group on Discrete Mathematics (SIAG/DM) Denes Konig Prize is awarded biennially to a junior researcher or junior researchers for outstanding research, as determined by the prize committee, in an area of discrete mathematics, based on a publication by the candidate(s) in a peer-reviewed journal published in the three calendar years prior to the year of the award. The recipient should be a graduate student or, at the time of the award, be within four years after completing a Ph.D. The prize is named in honor of Denes Konig (1884-1944), a Hungarian mathematician and early pioneer of discrete mathematics, whose influence over the field is still being felt. Please send nominations, with supporting details, to the chair of the prize committee: Bojan Mohar mohar@sfu.ca Deadline: October 1, 2010 ================================================================= 4. *** Announcement of SIAM DM10 - Austin, TX, June 14-17, 2010 *** ------ SIAM Conference on Discrete Mathematics (DM10) will be held June 14-17, 2010 in Austin, Texas at the Hyatt Regency Austin. http://www.siam.org/meetings/dm10/ Organizing Committee: Michael Molloy (chair), University of Toronto, Canada Peter Cameron, University of London, UK Anne Condon, University of British Columbia, Canada Bertrand Guenin, University of Waterloo, Canada Ken-ichi Kawarabayashi, National Institute of Informatics, Japan Mohit Singh, Microsoft Research Frank Sottile, Texas A&M University Eva Tardos, Cornell University Stephan Thomasse, University of Montpellier, France Van H. Vu, Rutgers University Peter Winkler, Dartmouth College Invited Plenary Speakers: Imre Barany, Hungarian Academy of Sciences, Hungary Jim Geelen, University of Waterloo, Canada Penny Haxell, University of Waterloo, Canada Anna R. Karlin, University of Washington Richard P. Stanley, Massachusetts Institute of Technology Madhu Sudan, Microsoft Research Terence Tao, University of California, Los Angeles Robin Thomas, Georgia Institute of Technology The call for papers will be posted at the website in mid August 2009. Information about travel support for students will also be posted at the website. ================================================================= 5. *** Travel support for SODA10 now available *** ------ Students are encouraged to attend the ACM-SIAM Symposium on Discrete Algorithms (SODA10), January 17-19, 2010, at the Hyatt Regency Austin in Austin, TX. The NSF has provided funding in the amount of $15,000 to support student travel grants. The nominal award is $500 toward travel to SODA10. In special cases of large travel costs, somewhat larger grants may be given. Any full-time student in good standing who is affiliated with a U.S. institution is eligible to receive an award plus complimentary symposium registration. Application deadline or these awards is November 6, 2009. To apply for travel support please visit: http://www.siam.org/meetings/da10/students.php for details ================================================================= 6. *** In Memory of Michael O. Albertson, 1946 - 2009 *** ------ Michael Albertson died in March after a short, intense battle with a rare form of thyroid cancer. He was a mathematician fully engaged in teaching, graph theory research, and the SIAM Discrete Mathematics (DM) community. He taught at Smith College for 37 years, where he was the L. Clark Seelye Professor. He produced research and scholarly work for 40 years and collaborated with many, including undergraduate students. A summary of his collaborative work can be found in a recent AWM Newsletter [H]. A complete list of his publications can be found at http://math.smith.edu/~albertson; copies of almost all his papers are linked to the web site and freely available. Mike was chair of the SIAM DM Activity Group between 2000 and 2002, served on the SIAM Coordinating Committee for the annual AMS-MAA-SIAM Joint Math Meetings from 2006 to 2008, and was an enthusiastic supporter of the alternate-year SIAM DM Conferences, organizing many minisymposia for these. With K. Collins and R. Haas he ran the Combinatorists of New England (CoNE) weekend conferences, held several times a year at Smith College between 1993 and 2001. Next March 26 - 28, 2010, at Smith College, a conference in memory of Mike will be held and run in the style of the CoNE conferences with a limited number of speakers, no parallel sessions, and plenty of time for discussion between talks. For more information on "CoNE Revisited: a celebration of the inspirations of Michael Albertson," see http://www.math.smith.edu/cone/MikeAlbertsonConference.html. In this article we pay tribute to Mike's research by presenting some of his many outstanding conjectures and questions; most are in the areas of chromatic, topological, geometric, and group- theoretic graph theory. All graph theory terminology can be found in [W, MT]; n always denotes the number of vertices of a graph. Mike earned his Ph.D. in 1971 at the University of Pennsylvania, under the direction of Professor H.S. Wilf. We, myself included, were fortunate to study at Penn in the late 60s since Prof. Wilf had just returned from a 1966 sabbatical at Imperial College, London, and taught a course in the new area of Combinatorial Analysis and Graph Theory. In London Prof. Wilf found in Math. Reviews, and read, every paper in this new field, then began writing pioneering, now fundamental, papers in combinatorics. Since Mike wanted to work in an important area, he chose to work on aspects of the Four-Color Problem. Among other results, he worked on the Erdos-Vizing Conjecture [V; see Ber], which conjectures that every planar graph (on n vertices) contains an independent set of at least n/4 vertices. Mike established the existence of an independent set with at least 2n/9 vertices [A], and his concisely proven bound remains the best result today on this conjecture that is independent of the (now) Four Color Theorem [ApH, RSST]. David Berman, now Professor Emeritus of the University of New Orleans, also studied combinatorics at Penn with us, and became a lifelong collaborator with Mike. He and Mike conjectured [ABe2] a stronger result, implying Erdos-Vizing, that every planar graph contains an induced forest on at least n/2 vertices. They worked on Grunbaum's Conjecture [G] and showed that the acyclic chromatic number of the plane is at most 7 [ABe]. That conjecture was proven by Borodin [Bor], who showed the best-possible bound to be 5, which also implies an induced forest on at least 2n/5 vertices. Mike joined the Smith mathematics faculty in 1973 and I was hired there in 1976. Starting in 1973 we began work together on coloring and embedding problems in topological graph theory. We introduced the concept of width of an embedded graph, which is the length of the graph's shortest noncontractible cycle [AHu1], and found that concept useful, even essential, in proving topological results, such as the fact that every triangulation of a nonplanar surface contains a noncontractible cycle of length at most (2n)^{1/2} [AHu2]. As a consequence, all but at most (2n)^{1/2} vertices of a triangulation of the torus can 4-colored, using the Four Color Theorem. Mike recently reported that his most favorite conjecture, among all that he made, was that all but at most three vertices of a triangulation of the torus can be 4-colored [A2]. He also conjectured that for each nonplanar surface S, there is an integer f(S) such that all but at most f(S) vertices of a triangulation of S can be 4-colored. In [JT] these are known as the Albertson Four- Color Problem. The concept of width is now a fundamental one in topological graph theory; it merits, for example, a whole chapter in [MT]. In 1982 Mike and Walter Stromquist [AS] introduced the idea of a locally planar embedded graph, which is one embedded with large width, where large typically is a function of the genus of the embedding surface. They proved that width at least 8 implies that a graph on the torus is 5-colorable and conjectured that locally planar graphs on each surface can be 5-colored. The latter conjecture was proven by Carsten Thomassen [T]. A more extensive summary of Mike's work on coloring graphs on surfaces can be found in [H2]. Mike went on to work on many generalizations of graph coloring, often with undergraduate students, including Karen Collins, and with colleague Ruth Haas. They obtained results on graph homomorphisms along with other chromatic-related problems. Mike worked with Doug West on the circular chromatic number, with Bojan Mohar on coloring vertices and faces of embedded graphs, on edge- coloring and list-coloring with R. Haas. If G is an r-chromatic graph and t <= r, let u(t,G) denote the maximum number of vertices in an induced t-colorable subgraph of G. Then in [AC] Mike and K. Collins showed that if f is a homomorphism from G to H and H is vertex-transitive, then for all t, u(t,G) >= u(t,H). Ruth Haas reports that her favorite conjecture with Mike and S. Grossman is the following [AGH]. Recall that if G is r-colorable, then for all t <= r, u(t,G) >= (t/r)n. They conjecture that if G is s-list- colorable (also known as s-choosable) and if every vertex of G is assigned a list of t colors, with t <= s, then at least (t/s)n vertices of G can be t-list-colored. Apparently their related question is still open: if G is planar, can at least n/2 vertices of G be 2-list colored? Mike worked with a number of people on pre-coloring extensions; I recommend highly his paper, "You can't paint yourself into a corner" [A3] for particularly good reading and a number of intriguing open questions. In [AC2] Mike and K. Collins introduced the concept of the distinguishing number, D(G), of a graph G, which is the smallest number of labels needed, with labels attached to the vertices of G, so that no nontrivial automorphism of G preserves all the vertex labels. A number of papers have been and are being written in this area, including some by Mike and Debra Boutin that have a geometric flavor. A geometric graph is a straight-line drawing of a graph in the plane with vertices in general position, and its geometric automorphisms are those automorphisms that preserve both crossing edges and noncrossing edges. In [ABo] the authors studied the distinguishing number of geometric graphs using geometric automorphisms as follows: The geometric distinguishing number of a graph G is given by D_g(G) = max{D(G^*): G^* is a geometric realization of G}. They showed that for 3 <= n <= 6, D_g(K_n) = 3 except when K_4 has a nonconvex drawing, and for that geometric graph D(K_4^*) = 4. Then they ask whether for n >= 7, D_g(K_n) = 2, or if not, whether there is an N > 7 such that for all n <= N, D_g(K_n) = 2. This pattern of distinguishing number being initially 3, then decreasing to 2, is seen with cycles and with Kneser graphs [ABo2]. This study of geometric graphs leads one to think about the notoriously difficult area of crossing numbers. [A4] is a stimulating paper of Mike's that includes a mixture of coloring, independent sets, and geometric graphs. Given a geometric graph, two crossings are dependent if two edges of the crossings are incident with the same vertex, and otherwise they are independent. Mike conjectured: If G has a representation as a geometric graph with all crossings independent, then the chromatic number of G, c(G), is at most 5. He proved c(G) <= 6, and I am pleased to report that this conjecture has just been proven by Daniel Kral and Ladislav Stacho [KS]. At times Mike used the moniker "graphcolormike". I would propose also "planargraphmike" since from the beginning and throughout his career he was interested in planar and planar-like graphs. In 2007 at the 6th Slovenian International Conference on Graph Theory, Bled' 07, he gave a talk on "Independence ratios of nearly planar graphs." Nearly planar graphs include those of thickness 2; Mike considered thickness an especially challenging parameter. Though the chromatic number of thickness-2 graphs is known only to lie between 9 and 12, inclusive, Mike had asked in the mid 1990s (personal communication) whether every thickness-2 graph had a(G)/n >= 1/8, where a(G) is the independence number of G. A counterexample with a(G)/n = 2/17 was found and given in [GS], and in Bled he asked more cautiously about how close a(G)/n might get to 1/9. May we all continue to work on these intriguing, important conjectures and questions of Mike Albertson, to achieve success with these, and to remember him with these living testimonials to his mathematics and life. Joan P. Hutchinson, Macalester College and University of Colorado Denver Acknowledgements. I want to thank all the referenced co-authors and collaborators, and in addition D. Archdeacon, E. Gethner, G. MacGillivray, and H. Wilf, for help with this article. ================================================================= ================================================================= DM-Net is a forum of the SIAM Activity Group on Discrete Mathematics We disseminate your contributions on anything of interest to the discrete mathematics community. This includes personal news about our members, conferences, mathematical problems, education issues, job/fellowship information, research announcements, etc. The moderator is Ryan Martin ----------------------------------------------------------------- Send submissions to: Send address changes to: Info on joining SIAM and this activity group: Archive URL: ----------------------------------------------------------------- Carla Savage North Carolina State Univ. Chair Bojan Mohar Simon Fraser University Vice Chair Mark Kayll University of Montana Secretary Lorna Stewart University of Alberta Program Director Ryan Martin Iowa State University DM-Net Editor =================================================================