Now showing items 1-20 of 33

    • 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 ...