Combinatorics Seminars Academic year 2008-2009 |
SMC Math Dept. | SMC Home | Jo Ellis-Monaghan Home | |
UVM Math Dept. | UVM CS Dept. | UVM Home | Dan Archdeacon Home |
SMC/UVM Joint Combinatorics Seminar, Fall 2008-Spring 2009.
(Note: If you are on the announcement distribution list, and wish to be removed, or if you or someone you know would like to be added, please contact the organizers at: jellis-monaghan@smcvt.edu or dan.archdeacon@uvm.edu).
For
many years the Math and CS departments at UVM have conducted weekly discrete
math/combinatorics/computer science seminars.
These seminars are now held jointly with St. Michael's
college, with the location alternating campuses. Recently, in addition to traditional talks in theoretical combinatorics,
there has also been a focus on the applications of
combinatorics. Our
goal is to bring
together academic and industry researchers for a productive exchange of the
theory and applications of combinatorics.
Examples
of areas of application in computer science include data mining, storage in disk
arrays, the design of parallel algorithms, software testing, database
formatting, file organization, the analysis of algorithms, the design of
networks, and interconnection strategies for networks.
Applications in information theory include wireless networking (the
design of radio and satellite networks), internet communication protocols,
signal processing, timing analysis and multiaccess communications. Combinatorial
techniques are also used to address problems involving scheduling, packing, data
compression, and book-width and fault-tolerant processing.
In molecular biology/biotechnology, applications include mapping genomes,
forming the clone libraries, and designing chips for DNA probes.
In the past year and a half, new applications have even come out of Wall
Street; (t,m,s)-nets are being used in numerical integration problems in
financial mathematics.
A wide range of combinatorial techniques and theory is available for such applications. In recent years a great deal of work has been done on developing new constructions, and a powerful theory of combinatorial constructions is emerging. These applications come at a time when the power of combinatorial constructions combined with computational methods is beginning to be fully realized. The problems appearing in these applications are providing us with new and challenging existence questions as well as surprising applications of familiar and long studied combinatorial techniques.
These seminars are open to the public. No registration or fees are required to attend.
Both industry and academic users of combinatorial techniques are invited to share their own particular interests by conducting one of the seminars. If you have an industry problem or other application that you are working with, this is an opportunity to present it to group of people who may be able to offer some approaches to it using newly developed techniques. If you are a mathematician or computer scientist, this is a chance to hear about interesting problems and to share your techniques with people who might have a real need for them.
The
format of the seminars may be presentations, workshops, background followed by
discussion, or even brain-storming sessions, at the discretion of the individual
speakers. If you are interested in
conducting a session, please contact the organizers at
jellis-monaghan@smcvt.edu
or dan.archdeacon@uvm.edu
with a brief description of what you would like to talk about.
The seminars generally will occur every other week, mid-afternoon on Monday, Wednesday or Friday, depending on the speaker's schedule. Check specific abstracts for details.
Links to on-line slides and other resources from the various talks (if available) are provided at the end of each abstract.
Date |
Speaker |
Title |
9-11-08 | Dan Archdeacon | The crossing numbers of graphs on the plane, the torus, and the double torus |
9-18-08 | John Voight | On lattice polygons |
9-26-08 | Thomas Prellberg | Car parking and combinatorics |
10-2-08 | Alan Ling | Some results on Deletion/Insertion Codes |
10-9-08 | Jeff Dinitz | Perfect one-factorizations of the complete graph |
10-16-08 | Dan Archdeacon | A partial dual of a polyhedron |
10-23-08 | Jo Ellis-Monaghan | Graph Theory and Complex Systems in Statistical Mechanics |
10-30-08 | Victor Larsen | Coloring with an unruly partner |
11-6-08 | Jeff Dinitz | The Existence of $N_2$ Resolvable Latin Squares |
11-13-08 | John Schmitt | Generalizing the degree sequence problem |
11-20-08 | Sam Northshield | Some problems with Beatty sequences |
1-22-09 | Jo Ellis-Monaghan | The topological Tutte polynomial of Bollobas and Riordan |
2-11-09 | Dan McQuillan | Strong magic labelings and Kotzig completion |
2-26-09 | Alan Ling | Constructions for Hash families |
3-19-09 | Tom Zaslavsky | Eight Queens and More |
3-26-09 | Seth Chaiken | Ported Parametrized Tutte Functions: Old and New Applications |
4-15-09 | Jeff Dinitz | SPECIAL EVENT: University Scholar Lecture |
5-14-09 | Iain Moffatt | Partial and natural duality |
6-7-09 | Discrete Math in the North East Conference | Meeting at UVM, Five great speakers. Details here. |
6-17-09 | Tom Zaslavsky | A Mobius drawing of the Peterson graph |
[Fall 2001 Abstracts] [Spring 2001 Abstracts] [Spring 2002 Abstracts] [Fall 2003 - Spring 2004 Abstracts] [Fall 2004-Spring 2005 Abstracts]
[Fall 2005-Spring 2006 Abstracts] [Fall 2006-Spring 2007 Abstracts] [Fall 2007-Spring-Summer 2008 Abstracts]
Date: Thursday, November 20, 2008
Time: 2:00-3:15 pm
Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus
Title: Some problems with Beatty sequences
Speaker: Sam Northshield, SUNY Plattsburg
Abstract: A Beatty sequence is a sequence of the form [an+b] , n=1,2,3…
(a,b fixed reals) where [x] is the greatest integer not exceeding x. We
shall give a short geometric proof of Beatty’s theorem (a necessary and
sufficient condition for two Beatty sequences to partition the natural
numbers). We generalize this theorem and discuss Fraenkel’s conjecture
concerning when the natural numbers are partitioned by three or more
Beatty sequences. Another problem concerns the infinitude of primes in a
Beatty sequence (done first by Vinogradov). I will discuss attempts made
to solve this. Possibly, I will also discuss a problem concerning
composition of Beatty sequences.
Date: Thursday, November 13, 2008
Time: 2:00-3:15 pm
Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus
Title: Generalizing the degree sequence problem
Speaker: John Schmitt, Middlebury
The degree sequence problem, determining when there exists an n-vertex graph whose list of vertex degrees matches a given list of n non-negative integers, has been well-studied. The Havel-Hakimi algorithm gives an efficient greedy solution to the problem. Another solution was provided by Erdos and Gallai. They gave a set of n inequalities to check and subsequently showed that, in the case of a positive solution, if the integer list summed to at least 2n-2, then there exists a graph with a spanning tree.
We discuss a generalization of the degree sequence problem as recently given by Amanatidis, Green and Mihail. Given a list of n non-negative integers and a square matrix whose entries are non-negative integers, they show how to determine if there is a graph whose list of vertex degrees matches the given list and the number of edges between the set of vertices of degree d_i and the set of vertices of degree d_j matches the (i,j)-entry of the given matrix. The solution to this problem given by Amanatidis et al. requires one to check a set of inequalities and a set of equations. We hope to use this result in future to determine the minimum sum necessary for a degree sequence to have a realization with a prescribed subgraph.
John Schmitt received his MS from UVM in 1998, his PhD from Emory University in 2005, and is currently an Assistant Professor at Middlebury College.
Date: Thursday, November 6, 2008
Time: 2:00-3:15 pm
Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus
Title: The Existence of $N_2$ Resolvable Latin Squares
Speaker: Jeff Dinitz, UVM
An $N_2$ resolvable latin squares is a latin square with no $2 \times 2$ subsquares that also has an orthogonal mate. In this talk I show that $N_2$ resolvable latin squares exist for all orders $n$ with $n \neq 2,4,6,8$ This is joint work with Alan Ling and Adam Wolfe.
Date: Thursday, October 30, 2008
Time: 2:00-3:15 pm
Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus
Title: Coloring with an unruly partner
Speaker: Victor Larsen, Middlebury College
Competitive graph coloring considers the r-coloring game originally
introduced by Bodlaender in 1991, so it is a fairly new topic with many
unexplored possibilities. In this game, Alice and Bob alternately color
the vertices of a graph G with a set X of r colors. Alice seeks to color
the graph using the fewest possible number of colors. Bob, however,
tries to force Alice to use more colors. This game has been studied on
many classes of graphs (trees, planar graphs, partial k-trees, etc.) and
bounds have been proven for the different classes, some significantly
looser than others. We will give a brief introduction to this topic and
highlight some of the more significant theorems.
Date: Thursday, October 23, 2008
Time: 2:00-3:15 pm
Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus
Title: Graph Theory and Complex Systems in Statistical Mechanics.
Speaker: Jo Ellis-Monaghan, SMC
What do beer foam, ghetto formation, and tumor migration have in common? They are all complex systems where microscale nearest neighbor interactions (neighboring bubbles, neighboring residences, neighboring cells) determine macroscale properties. These macroscale phenomena can lead to bottling problems, segregation, or malignancy. How then do we model, and thereby predict, the behaviors of such systems?
Statistical mechanics provides one tool in the q-state Potts model. Its nascent form, the Ising model, allows only two spins (up or down), and provides a model for magnetism. The Potts model with q > 2 allows more spins (thousands in the case of foam models). These models play important roles in the theory of phase transitions and critical phenomena in physics, and now have applications in every science.
The Potts model is typically constructed on various lattices. When these lattices are viewed as graphs, then, remarkably, the Potts model is also equivalent to one of the most renown graph invariants, the Tutte polynomial. Thus, there has been a remarkable synergy between the two fields in recent years. This talk will explore the Potts model, how it captures macroscale properties, its applications, and its relation to the Tutte and Chromatic polynomials.
Date: Thursday, October 16, 2008
Time: 2:00-3:15 pm
Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus
Title: A partial dual of a polyhedron
Speaker: Dan Archdeacon, UVM
An example of geometric duality of polyhedra is "the dual of the cube is the octahedron". In this classical dual the faces become vertices, the vertices become faces, and an edge joining two vertices at its ends becomes an edge joining the two faces on its sides. It has the nice property that "the dual of the dual is the original". What if one only required that a subset of edges switch their roles from joining points to joining faces, or even if a single edge switches its role? What would be the vertices or faces of such a partial dual? Try an example and you'll discover that the familiar concepts of point and face quickly become quite muddled. In this talk I will describe how to make *some* sense out of such a partial duality. This partial duality preserves the properties that a) repeating it twice returns to the original polyhedron, and b) dualizing over all edges corresponds to the classical geometric duality. We'll examine some properties of our partial duality, including its geometric interpretation, prove some quick results, and discuss where it might be applied.
Date: Thursday, October 9, 2008
Time: 2:00-3:15 pm
Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus
Title: Perfect one-factorizations of the complete graph
Speaker: Jeff Dinitz, UVM
A one factorization of the complete graph is perfect if the union of any two one-factors forms a Hamiltonian circuit. Perfect one-factorizations are known to exist in complete graphs of orders p+1 and 2p for primes p and for some other sporadic orders. Recently, our own Adam Wolfe constructed a perfect one-factorization or order 52. This is the first new “small” order found in nearly 20 years. In this talk I will give background information on perfect one-factorizations and discuss Adam Wolfe’s new result.
Date: Thursday, October 2, 2008
Time: 2:00-3:15 pm
Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus
Title: Some results on Deletion/Insertion Codes
Speaker: Alan Ling, UVM
We present some spectrum-type results for delete/insertion codes on length 3 and 4.
Date: Friday, September 26, 2008
Time: 3:35-4:25 pm
Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus
Title: Car parking and combinatorics
Speaker: Thomas Prellberg, Queen Mary University of London
Abstract:
Suppose that m drivers each choose a preferred parking space in a linear car park with n spaces. Each driver goes to the chosen space and parks there if it is free, and otherwise takes the first available space with larger number (if any). We will consider the combinatorial question of how many assignments of m drivers to n spaces lead to p spaces being occupied (or equivalently, the probability that for a randomly chosen assignment exactly p spaces get occupied). This problem is relevant for computer science (hashing with linear probing) and has also been studied in the physics literature in the context of percolation.
Date: Thursday, September 18, 2008
Time: 2:00-3:15 pm
Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus
Title: On lattice polygons
Speaker: John Voight, UVM
Recently, we discovered (in joint work with Wouter Castryck at Leuven) an inequality that relates the number of interior and boundary lattice points of a lattice polygon, generalizing the elementary and beautiful "onion skin" theorem of Haase and Schicho (using work of Poonen and Rodriguez-Villegas). In this talk we will discuss these matters and ask some basic open questions on lattice polygons. Students are particularly encouraged to attend!
Date: Thursday, September 11, 2008
Time: 2:00-3:15 pm
Location: Math Department Conference Room, 16 Cochester Avenue, UVM Campus
Title: The crossing numbers of graphs on the plane, the torus, and the double torus
Speaker: Dan Archdeacon, UVM
Abstract: A common way to present a graph is to draw it on the plane with as few crossings as possible. Also interesting, but less common, is to draw it on the torus with as few crossings as possible. Or on the double torus. As we add handles we can decrease the number of crossings. How much can this number of crossings decrease, and which "sequences of crossing numbers" are possible? The answer is surprising. Lots of pictures are promised.
Date: Thursday, January 22, 2009
Time: 4:00-5:00 pm
Location: Mathematics Department Conference Room, 16 Colchester Avenue, UVM Campus
Title: The topological Tutte polynomial of Bollobas and Riordan
Speaker: Jo Ellis-Monaghan, Saint Michael's College
The ribbon graph polynomial of Bollobas and Riordan extends the classical Tutte polynomial to ribbon graphs, or graphs cellularly embedded in a two-dimensional surface. We will introduce these ideas, and prove a recipe theorem for the ribbon graph polynomial that justifies calling it _the_ topological Tutte polynomial. This talk will lay the ground work for a future second talk detailing further results in this area.
This is joint work with Irasema Sarmiento.
Date: Thursday, February 11, 2009
Time: 3:30-4:30 pm
Location: Mathematics Department Conference Room, 16 Colchester Avenue, UVM Campus
Title: Strong Magic Labelings and Kotzig Completion
Speaker: Daniel McQuillan, Norwich
Abstract:
A total labeling is a bijective assignment of integers 1,2,3,.. to the vertices and edges of a graph. A vertex-magic total labeling (VMTL) has the added property that for each vertex v, the sum of its label and its incident edge labels is a constant. A VMTL is strong if the smallest labels are assigned to the edges and the largest are assigned to the vertices. It is unknown which 2-regular graphs have a strong VMTL. We discuss recent progress on this problem, using many different applications of Kotzig arrays. A Kotzig array is a jxk matrix, each row being a permutation of {0,1,…,k-1} and each column having constant column sum.
Date: Thursday, February 26, 2009
Time: 3:30-4:30 pm
Location: Mathematics Department Conference Room, 16 Colchester Avenue, UVM Campus
Title: Constructions for Hash families
Speaker: Alan Ling, CS, UVM
Abstract: A {\em perfect hash family} $\PHF(N; k, w, t)$ is an $N \times k$ array on $w$ symbols, in which in every $N \times t$ subarray, at least one row consists of distinct symbols. In this talk, we give various constructions for perfect hash families and its generalizations. In addition, various old and recent applications of hash families are discussed.
Date: Thursday, March 19, 2009
Time: 4:00-5:00 pm
Location: Mathematics Department Conference Room, 16 Colchester Avenue, UVM Campus
Title: Eight Queens and More
Speaker: Tom Zaslavsky, SUNY Binghamton
Abstract: Zaslavsky abstract 3-19-09.pdf
Date: Thursday, March 26, 2009
Time: 4:00-5:00 pm
Location: Mathematics Department Conference Room, 16 Colchester Avenue, UVM Campus
Title: Ported Parametrized Tutte Functions: Old and New Applications
Speaker: Seth Chaiken, CS, SUNY Albany
Abstract: Chaiken abstract 3-26-09.pdf
Slides: Chaiken slides 2.pdf
SPECIAL EVENT THIS WEEK!
UVM UNIVERSITY SCHOLAR LECTURE
Our own Jeff Dinitz has been named a UVM University Scholar for 2008-2009 in recognition of his “sustained excellence in research and scholarly activities” in the field of combinatorics. (Congratulations Jeff!) As part of this award, he will be presenting a special University Scholar Lecture, which we encourage all to attend in lieu of the usual combo seminar this week. The University Scholar Lectures, open to the general public, present an accessible glimpse into the scholar’s work, so this will be an excellent opportunity to see a great overview of Jeff Dinitz’ specialty in design theory.
Combinatorics Seminar Special Event
Date: Wednesday, April 15, 2009
Time: 4:00-5:00 pm
Location: Memorial Lounge, Waterman Building, UVM Campus (note change of venue and time)
Title: Thinking Deeply about Putting Numbers in Boxes
Speaker: Jeff Dinitz, UVM
For more information, see: http://www.uvm.edu/~uvmpr/?Page=News&storyID=14066
Date: Thursday, May 14, 2009
Time: 2:00-3:00 pm
Location: Mathematics Department Conference Room, 16 Colchester Avenue, UVM Campus
Speaker: Iain Moffatt, University of Southern Alabama
Title: Partial and natural duality
Abstract: Partial duality is is a far reaching generalization of the natural dual (or Euler-Poincare dual) of a graph. Roughly speaking, a partial dual of a ribbon graph is constructed by forming the natural dual only at a subset of edges of the ribbon graph. In this talk, after giving a definition of partial duality and describing a few of its basic properties, I will explain how partially dual ribbon graphs can be viewed as a decoration of a graph and its natural dual. The advantage of this point of view of partial duality is that it provides a way to extend know results about naturally dual graphs to results about partially dual graphs. As an illustration of this, I explain how Edmonds' well known characterization of natural duals can be extended to give a characterization of partial duals.
Date: Wednesday, June 17, 2009
Time: 10:30 – 11:30 a.m.
Location: Halstead Lab (Basement of Jeanmarie Hall), SMC Campus
Title: A Mobius Drawing of the Petersen Graph
Speaker: Thomas Zaslavsky, Binghamton University (SUNY)
Abstract:
Only a comparatively few graphs can be drawn in the plane so that no two edges cross. When a graph does have such a plane drawing, it divides the plane into regions, whose boundaries are made up of edges of the graph.
There are several ways to prove a graph cannot be drawn in the plane: it may have too many edges, it may have a bad subgraph, it may look evil (sorry, forget that, it's not math). If it can't be drawn in the plane, though, it might still be drawn in some other surface, with the aid of some handles attached to the plane (yes, handles, which can act like bridges for edges to cross over without touching).
Some of these handles might be twisted. Passing through a twisted handle reverses orientation. In fact, there are twisted half-handles, called crosscaps, which have the same reversing effect. Explained naively, if I walk through a twisted handle or a crosscap, my left and right get switched, so my heart is on the right and my liver on the left. I say my "orientation" has been reversed. Having my heart in the wrong place does not mean I am evil.
Now I want to draw a graph in a surface so that, if I go along a closed path of odd length, my orientation is reversed. I call this "parity embedding". Specifically, I want to draw the famous Petersen graph this way. (If you don't know that the Petersen graph is famous, that will not impede your understanding of the talk.)
Again, a graph may not be drawable without adding some crosscaps or handles. It may have too many edges, or bad subgraphs. I will show that the Petersen graph requires exactly 4 crosscaps in order to be drawn without crossing edges, by the unusual method of analyzing incompatibilities amongst potential face boundaries.
The Petersen graph's potential boundaries, called circles, have an intricate combinatorial structure that leads to proofs of several theorems, of which the parity embedding theorem is only one.
Directions to SMC: From major cities, see SMC
Directions
Once on Interstate 89 see below:
Maps: There are campus maps on the SMC website at SMC
Campus Map
Most talks are likely to be held in Jeanmarie, St. Edmunds Hall, or the Science
building.
UVM
Picture: There is a picture of the Math Department building (Lord House, 16
Colchester Avenue) at http://www.emba.uvm.edu/math
.
The seminars are
often held
here in the conference room on the first floor.
Parking: The easiest place to park is probably the Visitor Lot at Waterman.
It is located on College Street, across the street from the Waterman
administration building. Parking is paid, 75 cents/hour, 7 a.m. to 5
p.m., Monday through Friday, and free after 5 p.m. and on weekends and holidays.
Directions to the Vistors' lot:
From I-89: Take Exit 14W into Burlington. This puts you heading west on Williston Road going up hill.
Turn right onto North Prospect Street. Take first left onto College Street. Take first left into
visitor parking lot.
Heading north from Route 7: Follow Shelburne Road/Route 7 into
Burlington. At rotary, bear right. Approximately 1/4 mile to first four-way stop, turn right onto Cliff Street. Head uphill to end of
Cliff; take left onto South Prospect Street. Cross Main Street/Route 2. Take first left onto College Street. Take first left into visitor
parking lot.
Maps: There are campus maps on the UVM website, and the direct URAL is:
http://www.uvm.edu/map (the Math
Department is 16 Colchester, the visitor lot is across College street from
Waterman building).
From Interstate 89: Coming from the north or south, take exit 12. From the north, turn left off exit ramp; from the south, turn right onto Route 2A. Follow the road past three traffic lights, over a bridge and up a hill. Watch for (and turn into) IBM entrance signs on the right.
For the WILLISTON LOBBY: After turning into IBM, go straight. Pass the “Main Lobby” signs. Go around the S-curve and over bridge. Take third left-hand turn into the visitor parking lot.
Map: Here is a map of the area near IBM. The Williston site is the dark rectangle just to the south of the rectangle marked IBM.