Seminars and Colloquia by Series

Thursday, April 28, 2011 - 12:05 , Location: Skiles 006 , Chun-Hung Liu , Math, GT , Organizer: Robin Thomas
A Roman dominating function of a graph G is a function f which maps V(G) to {0, 1, 2} such that whenever f(v)=0, there exists a vertex u adjacent to v such that f(u)=2. The weight of f is w(f) = \sum_{v \in V(G)} f(v). The Roman domination number \gamma_R(G) of G is the minimum weight of a Roman dominating function of G. Chambers, Kinnersley, Prince and West conjectured that \gamma_R(G) is at most the ceiling 2n/3 for any 2-connected graph G of n vertices. In this talk, we will give counter-examples to the conjecture, and proves that \gamma_R(G) is at most the maximum among the ceiling of 2n/3 and 23n/34 for any 2-connected graph G of n vertices. This is joint work with Gerard Jennhwa Chang.
Thursday, April 21, 2011 - 12:05 , Location: Skiles 006 , Magnus Egerstedt , ECE, GT , Organizer: Robin Thomas
Arguably, the overarching scientific challenge facing the area of networked robot systems is that of going from local rules to global behaviors in a predefined and stable manner. In particular, issues stemming from the network topology imply that not only must the individual agents satisfy some performance constraints in terms of their geometry, but also in terms of the combinatorial description of the network. Moreover, a multi-agent robotic network is only useful inasmuch as the agents can be redeployed and reprogrammed with relative ease, and we address these two issues (local interactions and programmability) from a controllability point-of-view. In particular, the problem of driving a collection of mobile robots to a given target destination is studied, and necessary conditions are given for this to be possible, based on tools from algebraic graph theory. The main result will be a necessary condition for an interaction topology to be controllable given in terms of the network's external, equitable partitions.
Thursday, April 14, 2011 - 12:05 , Location: Skiles 006 , Peter Whalen , Math, GT , Organizer: Robin Thomas
Steinberg's Conjecture states that any planar graph without cycles of length four or five is three colorable. Borodin, Glebov, Montassier, and Raspaud showed that planar graphs without cycles of length four, five, or seven are three colorable and Borodin and Glebov showed that planar graphs without five cycles or triangles at distance at most two apart are three colorable. We prove a statement similar to both of these results: that any planar graph with no cycles of length four through six or cycles of length seven with incident triangles distance exactly two apart are three colorable. Special thanks to Robin Thomas for substantial contributions in the development of the proof.
Thursday, March 31, 2011 - 11:05 , Location: Skiles 006 , Kenta Ozeki , National Institute of Informatics, Japan , Organizer: Xingxing Yu
A characterization of graphs without an odd cycle is easy, of course,it is exactly bipartite. However, graphs without two vertex disjoint oddcycles are not so simple. Lovasz is the first to give a proof of the twodisjoint odd cycles theorem which characterizes internally 4-connectedgraphs without two vertex disjoint odd cycles. Note that a graph $G$ iscalled internally 4-connected if $G$ is 3-connected, and all 3-cutseparates only one vertex from the other.However, his proof heavily depends on the seminal result by Seymour fordecomposing regular matroids. In this talk, we give a new proof to thetheorem which only depends on the two paths theorem, which characterizesgraphs without two disjoint paths with specified ends (i.e., 2-linkedgraphs). In addition, our proof is simpler and shorter.This is a joint work with K. Kawarabayashi (National Institute ofInformatics).
Thursday, March 17, 2011 - 12:05 , Location: Skiles 006 , Arash Asadi , Math, GT , Organizer: Robin Thomas
The property that a graph has an embedding in projective plane is closed under taking minors. So by the well known theorem of Robertson and Seymour, there exists a finite list of minor-minimal graphs, call it L, such that a given graph G is projective planar if and only if G does not contain any graph isomorphic to a member of L as a minor. Glover, Huneke and Wang found 35 graphs in L, and Archdeacon proved that those are all the members of L. In this talk we show a new strategy for finding the list L. Our approach is based on conditioning on the connectivity of a member of L. Assume G is a member of L. If G is not 3-connected then the structure of G is well understood. In the case that G is 3-connected, the problem breaks down into two main cases, either G has an internal separation of order three or G is internally 4-connected . In this talk we find the set of all 3-connected minor minimal non-projective planar graphs with an internal 3-separation. This is joint work with Luke Postle and Robin Thomas.
Monday, March 14, 2011 - 14:05 , Location: Skiiles 168 , Paul Wollan , School of Mathematics, Georgia Tech and University of Rome , Organizer: Robin Thomas
This lecture will conclude the series. In a climactic finish the speaker will prove the Unique Linkage Theorem, thereby completing the proof of correctness of the Disjoint Paths Algorithm.
Thursday, March 10, 2011 - 12:05 , Location: Skiles 006 , Kevin Milans , University of South Carolina , Organizer: William T. Trotter
First-Fit is an online algorithm that partitions the elements of a poset into chains. When presented with a new element x, First-Fit adds x to the first chain whose elements are all comparable to x. In 2004, Pemmaraju, Raman, and Varadarajan introduced the Column Construction Method to prove that when P is an interval order of width w, First-Fit partitions P into at most 10w chains. This bound was subsequently improved to 8w by Brightwell, Kierstead, and Trotter, and independently by Narayanaswamy and Babu. The poset r+s is the disjoint union of a chain of size r and a chain of size s. A poset is an interval order if and only if it does not contain 2+2 as an induced subposet. Bosek, Krawczyk, and Szczypka proved that if P is an (r+r)-free poset of width w, then First-Fit partitions P into at most 3rw^2 chains and asked whether the bound can be improved from O(w^2) to O(w). We answer this question in the affirmative. By generalizing the Column Construction Method, we show that if P is an (r+s)-free poset of width w, then First-Fit partitions P into at most 8(r-1)(s-1)w chains. This is joint work with Gwena\"el Joret.
Monday, March 7, 2011 - 14:05 , Location: Skiles 168 , Paul Wollan , School of Mathematics, Georgia Tech and University of Rome , Organizer: Robin Thomas
The k-disjoint paths problem takes as input a graph G and k pairs of vertices (s_1, t_1),..., (s_k, t_k) and determines if there exist internally disjoint paths P_1,..., P_k such that the endpoints of P_i are s_i and t_i for all i=1,2,...,k. While the problem is NP-complete when k is allowed to be part of the input, Robertson and Seymour showed that there exists a polynomial time algorithm for fixed values of k. The existence of such an algorithm is the major algorithmic result of the Graph Minors series. The original proof of Robertson and Seymour relies on the whole theory of graph minors, and consequently is both quite technical and involved. Recent results have dramatically simplified the proof to the point where it is now feasible to present the proof in its entirety. This seminar series will do just that, with the level of detail aimed at a graduate student level.
Monday, February 28, 2011 - 14:05 , Location: Skiles 168 , Paul Wollan , School of Mathematics, Georgia Tech and University of Rome , Organizer: Robin Thomas
The k-disjoint paths problem takes as input a graph G and k pairs of vertices (s_1, t_1),..., (s_k, t_k) and determines if there exist internally disjoint paths P_1,..., P_k such that the endpoints of P_i are s_i and t_i for all i=1,2,...,k. While the problem is NP-complete when k is allowed to be part of the input, Robertson and Seymour showed that there exists a polynomial time algorithm for fixed values of k. The existence of such an algorithm is the major algorithmic result of the Graph Minors series. The original proof of Robertson and Seymour relies on the whole theory of graph minors, and consequently is both quite technical and involved. Recent results have dramatically simplified the proof to the point where it is now feasible to present the proof in its entirety. This seminar series will do just that, with the level of detail aimed at a graduate student level.
Monday, February 21, 2011 - 14:05 , Location: Skiles 168 , Paul Wollan , Math, GT and University of Rome , Organizer: Robin Thomas
The k-disjoint paths problem takes as input a graph G and k pairs of vertices (s_1, t_1),..., (s_k, t_k) and determines if there exist internally disjoint paths P_1,..., P_k such that the endpoints of P_i are s_i and t_i for all i=1,2,...,k. While the problem is NP-complete when k is allowed to be part of the input, Robertson and Seymour showed that there exists a polynomial time algorithm for fixed values of k. The existence of such an algorithm is the major algorithmic result of the Graph Minors series. The original proof of Robertson and Seymour relies on the whole theory of graph minors, and consequently is both quite technical and involved. Recent results have dramatically simplified the proof to the point where it is now feasible to present the proof in its entirety. This seminar series will do just that, with the level of detail aimed at a graduate student level.