A FLEXIBLE MODEL FOR COMPLEX NETWORKS Approved by: (2009)
Professor Milena Mihail, William T. Trotter
to Naomi. iii ACKNOWLEDGEMENTS I would first of all like to thank the School of Mathematics and the ACO program for providing me this opportunity. I would especially like to thank Prof. Luca Dieci...
INTERVAL PARTITIONS AND STANLEY DEPTH (2009)
Csaba Biró, David M. Howard, Mitchel T. Keller, William T. Trotter, J. Young
Abstract. In this paper, we answer a question posed by Herzog, Vladoiu,
Bar k-Visibility Graphs (2008)
Alice M. Dean, William Evans, Ellen Gethner, Joshua D. Laison, Mohammad Ali Safari, William T. Trotter
Let S be a set of horizontal line segments, or bars, in the plane. We say that G is a bar visibility graph, and S its bar visibility repre-sentation, if there exists a one-to-one correspondence...
Intersection Graphs of Pseudosegments: Chordal Graphs (2008)
Dangelmayr, Cornelia, Felsner, Stefan, Trotter, William T.
We investigate which chordal graphs have a representation as intersection graphs of pseudosegments. For positive we have a construction which shows that all chordal graphs that can be represented as...
Bar k-Visibility Graphs: Bounds on the Number of Edges, Chromatic Number, and Thickness (2008)
Alice M. Dean, William Evans, Ellen Gethner, Joshuad. Laison, Mohammad Ali Safari, William T. Trotter
Abstract. Let S be a set of horizontal line segments, or bars, in the plane. We say that G is a bar visibility graph, and S its bar visibility representation, if there exists a one-to-one...
RAMSEY THEORY AND PARTIALLY ORDERED SETS (2008)
Abstract. Over the past 15 years, Ramsey theoretic techniques and concepts have been applied with great success to partially ordered sets. In the last year alone, four new applications of Ramsey...
Bar k-Visibility Graphs (2008)
Alice M. Dean, William Evans, Ellen Gethner, Joshua D. Laison, Mohammad Ali Safari, William T. Trotter
Let S be a set of horizontal line segments, or bars, in the plane. We say that G is a bar visibility graph, and S its bar visibility representation, if there exists a one-to-one correspondence...
Spanning Trees of Bounded Degree (2007)
Andrzej Czygrinow, Glenn Hurlbert, William T. Trotter, Genghua Fan, H. A. Kierstead
Dirac’s classic theorem asserts that if G is a graph on n vertices, and δ(G) ≥ n/2, then G has a hamilton cycle. As is well known, the proof also shows that if deg(x)+deg(y) ≥ (n − 1), for...
Spanning Trees of Bounded Degree (2007)
Andrzej Czygrinow, Genghua Fan, Glenn Hurlbert, H. A. Kierstead, William T. Trotter
Dirac's classic theorem asserts that if G is a graph on n vertices, and (G) n=2, then G has a hamilton cycle. As is well known, the proof also shows that if deg(x) + deg(y) (n 1), for every pair...
Spanning Trees of Bounded Degree (2007)
Andrzej Czygrinow, Genghua Fan, Glenn Hurlbert, H. A. Kierstead, William T. Trotter
Dirac's classic theorem asserts that if G is a graph on n vertices, and (G) n=2, then G has a hamilton cycle. As is well known, the proof also shows that if deg(x) + deg(y) (n 1), for every pair...
Bar k-Visibility Graphs: Bounds on the Number of Edges, Chromatic Number, and Thickness (2006)
Dean, Alice M., Evans, William, Gethner, Ellen, Laison, Joshua D., Safari, Mohammad Ali, Trotter, William T.
Let S be a set of horizontal line segments, or bars, in the plane. We say that G is a bar visibility graph, and S its bar visibility representation, if there exists a one-to-one correspondence...
Bar k-Visibility Graphs: Bounds on the Number of Edges, Chromatic Number, and Thickness (2006)
Dean, Alice M., Evans, William, Gethner, Ellen, Laison, Joshua D., Safari, Mohammad Ali, Trotter, William T.
Let S be a set of horizontal line segments, or bars, in the plane. We say that G is a bar visibility graph, and S its bar visibility representation, if there exists a one-to-one correspondence...
Bar k-Visibility Graphs: Bounds on the Number of Edges, Chromatic Number, and Thickness (2006)
Dean, Alice M., Evans, William, Gethner, Ellen, Laison, Joshua D., Safari, Mohammad Ali, Trotter, William T.
Let S be a set of horizontal line segments, or bars, in the plane. We say that G is a bar visibility graph, and S its bar visibility representation, if there exists a one-to-one correspondence...
On the poset of all posets on n elements (2005)
Richard A. Brualdi, Hyung Chan Jung, William T. Trotter
Abstract. We consider the poset of all posets on n elements where the partial order is that of inclusion of comparabilities. We discuss some properties of this poset concerning its height, width,...
Andrzej Czygrinow, Glenn Hurlbert, H. A. Kierstead, William T. Trotter
Abstract. We say that a graph G is Class 0 if its pebbling number is exactly equal to its number of vertices. For a positive integer d, let kðdÞ denote the least positive integer so that every...
Posets and planar graphs (2000)
Stefan Felsner, William T. Trotter
DOI 10.1002/jgt.20081 Abstract: Usually dimension should be an integer valued parameter. We introduce a refined version of dimension for graphs, which can assume a value t 1 l t Š, thought to be...
The Maximum Number of Edges in a Graph of Bounded Dimension, with Application to Ring Theory (1999)
Geir Agnarsson, Stefan Felsner, William T. Trotter
With a finite graph G = (V, E), we associate a partially ordered set P = (X, P) with X = V ∪ E and x < e in P if and only if x is an endpoint of e in G. This poset is called the incidence...
Stefan Felsner, William T. Trotter
Abstract. There is a natural way to associate with a poset P a hypergraph H P, called the hypergraph of incomparable pairs, so that the dimension of P is the chromatic number of H P. The ordinary...
The goal of the AFOSR DURIP Grant was to assist the Mathematics Program at ASU in acquiring equipment for an Advanced Graphics Computing Facility. Our computers have made possible a breakthrough in...
theory and sequences of random variables (1998)
William T. Trotter, Peter Winkler
We consider probability spaces which contain a family {EA: A ⊆{1,2,...,n}, |A | = k} of events indexed by the k-element subsets of {1, 2,...,n}. A pair (A, B) of k-element subsets of {1, 2,...,n}...
Finite Three Dimensional Partial Orders Which Are Not Sphere Orders (1998)
Stefan Felsner, Peter C. Fishburn, William T. Trotter
. Given a partially ordered set P = (X; P ), a function F which assigns to each x 2 X a set F (x) so that x y in P if and only if F (x) ` F (y) is called an inclusion representation. Every poset has...
© 1998 Kluwer Academic Publishers. Printed in the Netherlands. Dimensions of Split Semiorders (1997)
Peter C. Fishburn, William T. Trotter
Abstract. A poset P = (X,P) is a split semiorder when there exists a function I that assigns to each x ∈ X aclosedintervalI(x) =[ax,ax + 1] of the real line R and a set F ={fx: x ∈ X} of real...
This paper is dedicated to Paul Erdős with appreciation for his impact on mathematics and the lives of mathematicians all over the world. Abstract. There are two central themes to research involving...
Finite Three Dimensional Partial Orders Which Are Not Sphere Orders (1997)
Stefan Felsner, Peter C. Fishburn, WILLIAM T. TROTTER
. Given a partially ordered set P = (X; P ), a function F which assigns to each x 2 X a set F (x) so that x y in P if and only if F (x) ` F (y) is called an inclusion representation. Every poset has...
New perspectives on interval orders and interval graphs (1997)
Abstract. Interval orders and interval graphs are particularly natural examples of two widely studied classes of discrete structures: partially ordered sets and undirected graphs. So it is not...
Graphs and partially ordered sets: recent results and new directions, Congr. Numer (1996)
Abstract. We survey some recent research progress on topics linking graphs and finite partially ordered sets. Among these topics are planar graphs, hamiltonian cycles and paths, graph and hypergraph...
Ramsey Theory And Sequences Of Random Variables (1996)
William T. Trotter, Peter Winkler
. We consider probability spaces which contain a family fEA : A ` f1; 2; : : : ; ng; jAj = kg of events indexed by the k--element subsets of f1; 2; : : : ; ng. A pair (A; B) of k--element subsets of...
Colorings of Diagrams of Interval Orders and α-Sequences of Sets (1995)
Stefan Felsner, William T. Trotter
. We show that a proper coloring of the diagram of an interval order I may require 1 + dlog 2 height(I) e colors and that 2 + dlog 2 height(I) e colors always suffice. For the proof of the upper...
On the fractional dimension of partially ordered sets (1994)
Stefan Felsner, William T. Trotter
Abstract. We use a variety of combinatorial techniques to prove several theorems concerning fractional dimension of partially ordered sets. In particular, we settle a conjecture of Brightwell and...
On the fractional dimension of partially ordered sets (1994)
Stefan Felsner, William T. Trotter
Abstract. We use a variety of combinatorial techniques to prove several theorems concerning fractional dimension of partially ordered sets. In particular, we settle a conjecture of Brightwell and...