Graph Theory @ Georgia Tech http://hdl.handle.net/1853/44171 Clough Undergraduate Learning Commons, May 7-11, 2012 2021-05-11T22:45:26Z Tangles, 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:00Z 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. 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:00Z 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. 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:00Z 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. 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:00Z 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.