Graph Theory @ Georgia Tech
http://hdl.handle.net/1853/44171
Clough Undergraduate Learning Commons, May 7-11, 20122021-05-11T22:45:26ZTangles, Trees and Flowers
http://hdl.handle.net/1853/44229
Tangles, Trees and Flowers
Whittle, Geoff
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 cross the structure in a non-trivial way relative to the tangle has order k. It turns out that, modulo a natural notion of equivalence, such k-separations do not behave arbitrarily. Indeed there is a tree that describes, up to equivalence, all such k-separations. This tree generalises known tree decompositions for 2- and 3-separations in connected and 3-connected matroids and graphs. This is joint work with Ben Clark.
Proceedings of Graph Theory@Georgia Tech, a conference honoring the 50th Birthday of Robin Thomas, May 7-11, 2012 in the Clough Undergraduate Learning Commons.
2012-05-01T00:00:00ZWhittle, GeoffTangles 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 cross the structure in a non-trivial way relative to the tangle has order k. It turns out that, modulo a natural notion of equivalence, such k-separations do not behave arbitrarily. Indeed there is a tree that describes, up to equivalence, all such k-separations. This tree generalises known tree decompositions for 2- and 3-separations in connected and 3-connected matroids and graphs. This is joint work with Ben Clark.A Colin de Verdiere-Type Invariant and Odd-K_4- and Odd-K^2_3-Free Signed Graphs
http://hdl.handle.net/1853/44228
A Colin de Verdiere-Type Invariant and Odd-K_4- and Odd-K^2_3-Free Signed Graphs
Van der Holst, Hein
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 \nu(G,\Sigma)\leq 1, and signed graphs with no odd-K_4- and no odd-K^2_3-minor as those signed graphs (G,\Sigma) with \nu(G,\Sigma)\leq 2. In this talk we will discuss this invariant and these results. Joint work with Marina Arav, Frank Hall, and Zhongshan Li.
Proceedings of Graph Theory@Georgia Tech, a conference honoring the 50th Birthday of Robin Thomas, May 7-11, 2012 in the Clough Undergraduate Learning Commons.
2012-05-01T00:00:00ZVan der Holst, HeinWe 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 \nu(G,\Sigma)\leq 1, and signed graphs with no odd-K_4- and no odd-K^2_3-minor as those signed graphs (G,\Sigma) with \nu(G,\Sigma)\leq 2. In this talk we will discuss this invariant and these results. Joint work with Marina Arav, Frank Hall, and Zhongshan Li.Braces and Pfaffian Orientations
http://hdl.handle.net/1853/44227
Braces and Pfaffian Orientations
Whalen, Peter
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 determinant of the modified matrix? When is a hypergraph with n vertices and n hyperedges minimally nonbipartite? When does a bipartite graph have a Pfaffian orientation? Given a digraph, does it have an even directed circuit? When is a square matrix sign non-singular? We provide a much shorter proof using elementary methods for their theorem. This is joint work with Robin Thomas.
Proceedings of Graph Theory@Georgia Tech, a conference honoring the 50th Birthday of Robin Thomas, May 7-11, 2012 in the Clough Undergraduate Learning Commons.
2012-05-01T00:00:00ZWhalen, PeterRobertson, 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 determinant of the modified matrix? When is a hypergraph with n vertices and n hyperedges minimally nonbipartite? When does a bipartite graph have a Pfaffian orientation? Given a digraph, does it have an even directed circuit? When is a square matrix sign non-singular? We provide a much shorter proof using elementary methods for their theorem. This is joint work with Robin Thomas.Planarity and Dimension for Graphs and Posets
http://hdl.handle.net/1853/44226
Planarity and Dimension for Graphs and Posets
Trotter, William T
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 only if they have dimension at most 2. Planar posets with a zero (or a one) have dimension at most 3, but Kelly showed that there are planar posets of arbitrarily large dimension. Subsequently, Schnyder proved that a graph is planar if and only if the dimension of its incidence poset is at most 3. Quite recently, Felsner, Wiechert and Trotter have shown that the dimension of a poset with a planar comparability graph is at most 4, while Streib and Trotter have shown that the dimension of a poset with a planar cover graph is bounded as a function of its height.
Proceedings of Graph Theory@Georgia Tech, a conference honoring the 50th Birthday of Robin Thomas, May 7-11, 2012 in the Clough Undergraduate Learning Commons.
2012-05-01T00:00:00ZTrotter, William TThere 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 only if they have dimension at most 2. Planar posets with a zero (or a one) have dimension at most 3, but Kelly showed that there are planar posets of arbitrarily large dimension. Subsequently, Schnyder proved that a graph is planar if and only if the dimension of its incidence poset is at most 3. Quite recently, Felsner, Wiechert and Trotter have shown that the dimension of a poset with a planar comparability graph is at most 4, while Streib and Trotter have shown that the dimension of a poset with a planar cover graph is bounded as a function of its height.