The School of Mathematics recognized Professor Robin Thomas for his work on Graph Theory with a conference honoring his 50th birthday
May 7-11, 2012
Clough Undergraduate Learning Commons

Recent Submissions

  • Tangles, Trees and Flowers 

    Whittle, Geoff (Georgia Institute of Technology, 2012-05)
    Tangles provide a means of identifying highly connected components of a graph, matroid or, more generally, a connectivity function. For a tangle of order k in such a structure, the smallest order of a separation that can ...
  • A Colin de Verdiere-Type Invariant and Odd-K_4- and Odd-K^2_3-Free Signed Graphs 

    Van der Holst, Hein (Georgia Institute of Technology, 2012-05)
    We introduced a new Colin de Verdiere-type invariant \nu(G,\Sigma) for signed graphs. This invariant is closed under taking minors, and characterizes bipartite signed graphs as those signed graphs (G,\Sigma) with ...
  • Intersection Theorems for Finite Sets 

    Mubayi, Dhruv (Georgia Institute of Technology, 2012-05)
    Finite extremal set theory is concerned with the following general problem: Suppose we have a collection F of subsets of an n-element set and we have some restriction on the possible intersection sizes of pairs of sets in ...
  • Large Clique Minors in Vertex Transitive Graphs 

    Mohar, Bojan (Georgia Institute of Technology, 2012-05)
    An important (yet unpublished) theorem of Babai states that there exists a function f: N -> N so that every finite vertex transitive graph without K_n as a minor is either (f(n),f(n))-ring-like or is a vertex transitive ...
  • Clique Immersion in Digraphs 

    McDonald, Jessica (Georgia Institute of Technology, 2012-05)
    Immersion is a containment relation between graphs (or digraphs) which is defined similarly to the more familiar notion of minors, but is incomparable to it. In this talk we focus on immersing a bidirected clique \vec{K}_t ...
  • Discrepancy, Bansal's Algorithm and the Determinant Bound 

    Matousek, Jiri (Georgia Institute of Technology, 2012-05)
    Recently Nikhil Bansal found a polynomial-time algorithm for computing low-discrepancy colorings, based on semidefinite programming. It makes several existential bounds for the discrepancy of certain set systems, such as ...
  • Extremal Problems in Eulerian Digraphs 

    Ma, Jie (Georgia Institute of Technology, 2012-05)
    Graphs and digraphs behave quite differently and many natural results for graphs are often trivially false for general digraphs. It is usually necessary to consider restricted families of digraphs to obtain meaningful ...
  • Extending Polynomials in Combinatorics 

    Loebl, Martin (Georgia Institute of Technology, 2012-05)
    Tutte polynomial is an extension of the chromatic polynomial. Fruitful source of extensions is q-commutation and determinant: q-MacMahon Master theorem is an important example. I will describe the basic setting and show ...
  • An Upper Bound on the Fractional Chromatic Number 

    Liu, Chun-Hung (Georgia Institute of Technology, 2012-05)
    An (a:b)-coloring of a graph G is a function f which maps the vertices of G into b-element subsets of some set of size a in such a way that f(u) is disjoint from f(v) for every two adjacent vertices u and v in G. The ...
  • Linkless Embeddings in 3-space 

    Kreutzer, Stephan (Georgia Institute of Technology, 2012-05)
    We consider piecewise linear embeddings of graphs in the 3-space R^3. Such an embedding is "linkless" if every pair of disjoint cycles forms a trivial link (in the sense of knot theory). Robertson, Seymour and Thomas ...
  • Deciding Properties in Sparse Combinatorial Structures 

    Kral, Daniel (Georgia Institute of Technology, 2012-05)
    Algorithmic metatheorems guarantee that certain types of problems have efficient algorithms. A classical example is the result of Courcelle asserting that every MSOL property can be tested in linear time for graphs with ...
  • Braces and Pfaffian Orientations 

    Whalen, Peter (Georgia Institute of Technology, 2012-05)
    Robertson, Seymour, Thomas and simultaneously McCuaig answered several equivalent questions. Specifically, when can some of the 1's of a 0-1 square matrix, A, be changed to -1's so that the permanent of A equals the ...
  • Planarity and Dimension for Graphs and Posets 

    Trotter, William T (Georgia Institute of Technology, 2012-05)
    There is a rich history of research relating planarity for graphs and diagrams with the dimension of posets, starting with the elegant characterization of planarity for posets with a zero and a one: they are planar if and ...
  • On Some Chi-Bounded Classes of Graphs 

    Thomasse, Stephan (Georgia Institute of Technology, 2012-05)
  • Tutte's Three-Edge-Colouring Conjecture 

    Seymour, Paul (Georgia Institute of Technology, 2012-05)
    The four-colour theorem is equivalent to the statement that every planar cubic graph with no cut-edge is 3-edge-colourable. What about non-planar cubic graphs? The Petersen graph is not 3-edge-colourable, and in 1966 Tutte ...
  • Induced Subgraphs and Subtournaments 

    Seymour, Paul (Georgia Institute of Technology, 2012-05)
    Let H be a graph and let I be the set of all graphs that do not contain H as a minor. Then H is planar if and only if there is an upper bound on the treewidth of the members of I; and there are many other similar theorems ...
  • Embeddability of Infinite Graphs 

    Salazar, Gelasio (Georgia Institute of Technology, 2012-05)
  • On Subgraphs of Large Girth 

    Rodl, Vojtech (Georgia Institute of Technology, 2012-05)
  • Separators, Brambles, Tree Decompositions and Excluding Clique Minors 

    Reed, Bruce (Georgia Institute of Technology, 2012-05)
    The talk surveys the relationships between these topics highlighting the fundamental contributions of Robin Thomas.
  • 5-List-Coloring Graphs on Surfaces 

    Postle, Luke (Georgia Institute of Technology, 2012-05)
    Thomassen proved that there are only finitely many 6-critical graphs embeddable on a fixed surface. He also showed that planar graphs are 5-list-colorable. We develop new techniques to prove a general theorem for 5-list-coloring ...

View more