Monday January 11, 2010, 4:00 in Kemeny 004
Sergi Elizalde (Dartmouth College)
The number of numerical semigroups of a given genus
A numerical semigroup is a subset of the non-negative integers that contains 0, is closed under addition, and has a finite complement. The size of the complement is called the genus of the semigroup. In this talk I will give some lower and upper bounds on the number ng of numerical semigroups of genus g. The idea is to use a generating tree for all numerical semigroups, approximate it by other generating trees whose succession rules are easier to describe, and then obtain generating functions that enumerate their nodes. It is conjectured that the limit of ng+1/ng as g goes to infinity is the Golden ratio.
Monday January 18, 2010, 3:30 in Kemeny 004
Olivier Bernardi (MIT)
A unified bijective method for maps
A planar map is an embedding of connected planar graph in the sphere considered up to deformation. In the last decades, a bijective approach was developed by Schaeffer and others for studying maps. In this talk, I will present a general bijection between certain oriented maps and certain decorated plane trees. By specializing this bijection to particular classes of maps, we recover and extend several known bijections for triangulations, quadrangulations and bipartite
maps.
This is a joint work with Guillaume Chapuy and Eric Fusy.
Monday January 25, 2010, 4:00 in Kemeny 004
Rosa Orellana (Dartmouth College)
Descents and peaks
In this talk will present a combinatorial introduction to the descent and peak algebras. During the second part of the talk I will discuss recent work with Mathas on a generalization of descent algebras to complex reflection groups.
Thursday February 4, 2010, 1:00 in Kemeny 004
Paul Raff (Rutgers University)
Avoiding prescribed differences, and its generalizations
In this talk, I will primarily discuss the quantity
fΔ(n), defined as the size of the largest subset of [n]
avoiding differences prescribed in the set Δ. This can be
viewed in numerous other ways, including the size of the largest
independent set of circulant graphs. The impetus for investigation was
the short-lived Triangle Conjecture of Schutzenberger and Perrin and
its counterexample by Shor. A generalized recurrence equation will be
shown, leading to various consequences, including details on the
structure of the sequence {fΔ(n)} for any fΔ(n) and an
automated theorem prover (which will be demonstrated). The
investigations into fΔ(n) lead back to the Triangle Conjecture
in the form of an asymptotic proof. Additionally, three
generalizations will be briefly discussed, derived from extending the
idea of “difference”.
Monday February 8, 2010, 4:00 in Kemeny 004
Robert Brignall (University of Bristol)
Antichains and the structure of permutation classes
Permutation classes, the analogue of hereditary properties of graphs for
permutations, are defined as downsets in the permutation containment
partial ordering, and are most commonly described as the collection
avoiding some set of permutations, cf forbidden induced subgraphs for
hereditary graph properties. Much of the emphasis in their recent
intensive study has been on exact and asymptotic enumeration of particular
families of classes, but an ongoing study of the general structure of
permutations is yielding remarkable results which typically also have
significant enumerative consequences.
In this talk I will describe a number of these structural results useful
in studying the question of partial well-order — i.e. the existence or
otherwise of infinite antichains in a given permutation class. The
building blocks of all permutations are “simple permutations”, and we will
see how these on their own contribute to the partial well-order problem.
Seemingly independently, we will see how “grid classes”, a construction
used to express large complicated classes in terms of smaller
easily-described ones, also plays its part. Finally, I will present recent
and ongoing work in combining these two concepts, first describing a
general construction for antichains using “grid pin sequences”, and second
proving where certain families of grid classes are partially well-ordered.
Monday February 15, 2010
Seminar canceled
Monday February 22, 2010, 4:00 in Kemeny 004
John Schmitt (Middlebury College)
Generalizing the degree sequence problem
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 most well-known solution, provided by Erdős and Gallai, gave a set of n inequalities to check. They also showed that in the case of a positive solution if the terms of the degree sequence summed to at least 2n-2, then there exists a graph realizing the degree sequence which contains a spanning tree. In the early 90s Erdős, Jacobson and Lehel (EJL) conjectured that if the terms of a degree sequence summed to at least (t-2)(2n-t+1)+2, then there exists a graph realizing this degree sequence containing a complete graph on t vertices. We discuss our proof to this conjecture. Also, in the hopes of proving a generalization of the EJL-conjecture for a degree sequence to have a realization containing a given subgraph F, we discuss a generalization of the degree sequence problem as recently given by Amanatidis, Green and Mihail. Their generalized degree sequence problem is as follows: given a list of n non-negative integers and a square matrix whose entries are non-negative integers, 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 di and the set of vertices of degree dj matches the (i,j)-entry of the given matrix.
Monday March 1, 2010, 4:00 in Kemeny 004
Matthew Kahle (Stanford University)
Warmth and mobility of random graphs
Brightwell and Winkler defined a graph parameter called
“warmth,” motivated by considerations from statistical physics. They
investigated various properties and showed in particular that the
warmth of a graph is a lower bound on its chromatic number. Although
warmth is not a monotone graph property we show it is nevertheless
“statistically monotone” and that for sparse graphs the warmth is
concentrated on either one or two values. As a corollary we prove that
a conjecture of Lovász holds for almost all graphs. This is based on
joint work with Sukhada Fadnavis.
Monday March 8, 2010, 4:00 in Kemeny 004
Jo Ellis-Monaghan (Saint Michael's College)
Graph theoretical design strategies for self-assembling nanostructures
Recent advances in DNA self-assembly have resulted in nanoscale graphs: cubes, octahedrons, truncated octahedra, and even buckyballs, as well as ultra-fine meshes. These constructs serve emergent applications in biomolecular computing, nanoelectronics, biosensors, drug delivery systems, and organic synthesis.
One construction method uses k-armed branched junction molecules, called tiles, whose arms are double strands of DNA with one strand extending beyond the other, forming a ‘sticky end’ at the end of the arm that can bond to any other sticky end with complementary Watson-Crick bases. A vertex of degree k in the target graph is formed from a k-armed tile, and joined sticky ends form the edges. Another construction method ‘threads’ a single strand of DNA through the graphical structure and then uses short ‘staple’ strands to fold the DNA into the desired geometric realization of the graph. A third method uses circular single strands of DNA to trace the faces of a topological embedding of the graph.
We use graph theory to determine optimal design strategies for biologists producing these nanostructures. For flexible armed tiles, we define two new numerical graph invariants, the minimum number of tiles and minimum number of edge types necessary to create a given graph under three different laboratory scenarios. We determine these values for common graph classes (complete, bipartite, trees, regular, Platonic and Archimedean, etc.). For these classes of graphs, we provide either explicit descriptions of the set of tiles achieving the minimums or efficient algorithms for generating the desired set. For rigid armed tiles, we turn to the octet truss, and identify naturally occurring embedded graphs that may be efficiently constructed. Optimal threadings come from adaptations of the Chinese Postman problem, and we use genus results from topological graph theory for circular strand methods.
This is joint work with Greta Pangborn, and with extensive undergraduate research participation.
Previous Terms:
Fall 2004.
Spring 2006.
Fall 2008
Winter 2009
Spring 2009
If you are interested in speaking please email Vince Vatter (the organizer this term), Sergi Elizalde, or Rosa Orellana.