While studying at Georgia Tech my primary research focus was the study of the combinatorics of partially ordered sets. I focused on answering some of the questions posed by Tanenbaum, Trenk, and Fishburn in their seminal manuscript on the linear discrepancy of posets and the combinatorial implications of the work on Herzog, Valdiou, and Zheng on Stanley depth.
The linear discrepancy of a can be thought of as a measure of fairness of a linear extension. For example, consider the situation of patients arriving at an emergency room; as they arrive the patients are triaged inducing partial order on the patients based on the severity of their injuries. The order in which patients are seen is essentially a linear extension of the "injury poset." To be fair to the patients, it would be reasonable to insist that patients with incomparable injuries are seen as close together as possible. The linear discrepancy can be thought of as minimal amount of "unfairness" necessary as a result of this process.
Although my work on Stanley depth ostensibly was about the Stanley depth of monomial ideals, in reality, we consider a class of poset partitioning problems with the commutative algebra applications as a pleasant side effect. In the simplest case, the question is how to partition a upwardly closed portion of the subset lattice into intervals so as to maximize the minimal size of the top of an interval. Although the motivation for these questions come from commutative algebra, the study of such partitions have resulted in novel combinatorial observations about the subset lattice. Most notably, the non-empty subset lattice on 2k+1 elements can be partitioned into intervals [A,B] so that A has 2s+1 elements and B has k+s+1 elements.
Since starting at UCSD my research focus has turned more towards the spectral analysis of a graphs, in particular, properties and consequences of the normalized Laplacian. The spectrum, and in particular the spectral gap, of the normalized Laplacian governs the expansion properties of the underlying graph and hence controls many algorithmic aspects of the graph. Some of my recent work has focused on understanding the spectrum in general situations. In particular, I have focused on understanding how the randomness influences the spectrum and generalizing the Alon-Boppana to bound the size of the spectral gap.
Additionally, I have been considering how the expansion properties of a network interact with a selfish routing on that network. One surprising consequence this work is that in a wide variety of real world situations the removal of connection can improve the performance of the network in selfish routing situations. More prosaically, if you believe that commuters in rush hour drive selfishly, my work indicates that closing certain (likely high speed) roads will shorten everyone's commute.
Although my research has been focused primarily on spectral graph
theory and the combinatorics of posets the underlying driving force
in my research is probably my love of the collaborative aspects of
mathematics. My favorite moments as a mathematician have come when I am sitting around with friends and collaborators throwing ideas out and watching the truth take shape before us. I would imagine that in chasing these moments, I will continue to collect miscellaneous results which are not easily classified as either spectral graph theory or the
combinatorics of posets.
Selected Current Projects
Cops and Robber In the game of cops and robber, the cops and the robber take turns moving along the edges of the graph with the robber having the obvious goal of avoiding capture. The primary open question is this field is Meyniel's conjecture which posits an upper bound on the number cops needed to capture a single robber. Recently, several different groups have made some progress on resolving this conjecture, based in part on a nominal expansion condition. Together with Fan Chung and some of her graduate students, I am looking at how spectral techniques could contribute to this upper bound.
Stanley Depth Recently it has been observed that if the Stanley depth of a monomial ideal is strictly greater than the Stanley depth of the associated quotient ideal, then there is a potential route to resolve Stanley's conjecture for all monomial ideals. With Mitch Keller, I am looking at exploiting the tools for combinatorially calculating Stanley depth (first applied here) to show this separation result.
Ascent Sequences and Semiorders The recent work of Bousquet-Melou, Claesson, Dukes, and Kiteav shows that there is a bijection between a particular class of sequences called ascent sequences and unlabelled interval orders. Working with Jeff Remmel, I have been considering the nature of this bijection when restricting to semi-orders (unit length interval orders). We have preliminary results which indicate a new characterization of the canonical representation of semi-orders.
Random Graphs and Spectral Graph Theory
- Random Dot Product Graphs: A Flexible Model for Complex Networks
Thesis Georgia Institute of Technology, December 2008
In my Ph.D. thesis I considered a general random graph model where the vertices are assigned a random vector in some high dimensional space and the probability of an edge between two vertices is proportional to the inner product between the vectors. I was able to provide sufficient conditions for this random graph to exhibit poly-logarithmic diameter, clustering, and developed a characterization of the degree sequence based on the initial distribution of vectors.
- Random Dot Product Graph Models for Social Networks (*)
Lecture Notes in Computer Science 4863, Proceedings of WAW 2007, 138-149.
(with E.R. Scheinerman)
We consider a directed generalization of the random dot product graph model and show that the resulting graph has positive clustering, constant diameter of the giant component and provide empirical evidence for a power-law degree distribution. In addition, we show that any "bad" cuts in such a model are inherently non-geometric.
- Directed Random Dot Product Graphs
Internet Mathematics 5, no. 1-2 (2008), 91-111.
(with E.R. Scheinerman)
This is an expanded version of the WAW 2007 paper. We additionally consider a spherical directed random dot product graphs, where the in- and out-vectors are scaled version of the same vector.
- Kernel Models for complex networks
(with Y. Amanatidis and M. Mihail)
A position paper arguing for the expanded use of kernel based methods in the analysis and development of random graphs models for complex networks.
- Braes's Paradox in Sparse Random Graphs (*)
Lecture Notes in Computer Science 6484, Proceedings of WINE 2010, 194-208.
(with F. Chung)
Braess's paradox is supposedly rare phenomenon by which removing links from a network can improve the overall selfish routing time for the entire network. Extending the results of Valiant and Roughgarden, we show Braess's paradox occurs with high probability in connected Erdos-Renyi random graphs with random linear latency functions.
- Braess's paradox in expanders
Random Structures and Algorithms 41 no. 4 (2012), 451-468
(with F. Chung and W. Zhao)
Extending the work which appeared in WINE 2010, we show that the paradox occurs in sufficiently good expanders where the latency functions are random convex functions.
- The weighted spectrum of the universal cover and an Alon-Boppana result for the normalized Laplacian
submitted October 2011
The Alon-Boppana theorem states that there is an lower bound on the second largest eigenvalue of the adjacency matrix for d-regular graph. I generalize this to an upper bound on the second smallest eigenvalue of the normalized Laplacian of a general graph based on the first and second order average degree.
- The Spectra of Multplicative Attribute Graphs
submitted February 2012
(with M. Radcliffe)
Stochastic Kronecker graphs are a recent model for complex networks such as the internet where each edge is independent, but the probability of occurence is based on the Kronecker product of a fixed matrix. Mulitplicative attribute graphs are the natural generalization of the stochastic Kronecker graphs formed by allowing duplication of vertices before randomly generating the edges. Using properties of the Kronecker product and matrix spectrum concetentration techniques we provide asymptotic control of the spectrum of the adjacency matrix and normalized Laplacian for both graph models.
- The diameter of random cubic sum graphs
submitted April 2012
The vertices of a cubic sum graph are binary words of a fixed length where u ~ v if and only if u + v is also a vertex. I consider the diameter of the random version of such a graph and show that for almost the entire range of connectivity this is concentrated on one of six values.
- Connectivity and giant Component of stochastic Kroencecker graphs
submitted September 2013
(with M. Radcliffe)
Stochastic Kronecker graphs are a recent model for complex networks such as the internet where each edge is independent, but the probability of occurence is based on the Kronecker product of a fixed matrix. We use a novel understanding of the adjancency structure of stochastic Kronecker graphs to completely characterize the emmergence of giant component and connectivity in terms of generating matrix.
- Dimensionality of Social Networks Using Motifs and Eigenvalues
PLOS One acceptted July 2014
(with A. Bonato, D. F. Gleich, M. Kim, D. Mitsche, P. Pralat, A. Tian)
The log-dimension hypothesis conjectures that social networks exist in some underlying, but hidden, geometric space that grows logarithmically with the size of the network. Using parameters derived from snapshots of the Facebook and LinkedIn networks, we use simulate a modificatin of the Geometric Protean Graphs with a variety of dimension parameters. The analysis of this simulation data provides some evidence for the log-dimension hypothesis.
- On the spectrum of inhomogeneous random graphs
(with M. Mihail)
We consider the spectrum of the normalized Laplacian for a general graph where the edge probability is non-uniform. We show that the spectrum can be determined from the spectrum of a deterministic matrix and a matrix which has zero expectation. We apply this reduction to improve the results of Chung, Lu, and Vu on the spectral gap of the expected degree sequence model. Additionally, we apply the results to a variation of the small world network model of Strogatz and Watts.
Combinatorics of Partially Ordered Sets
- A characterization of
partially ordered sets with linear discrepancy equal to 2 (*)
Order 24 no. 3 (2007), 139-153.
(with D.M. Howard and M.T. Keller)
The linear discrepancy of a poset is the least k such that there is a linear extension of the poset so that incomparable elements are at most k apart. We complete the characterization of posets with linear discrepancy at most three.
- Stanley depth of square-free monomial ideals
Journal of Algebra 322 no. 10 (2009), 3789-3792
(with M.T. Keller)
Using the correspondence between Stanley depth and poset partition discovered by Herzog, Vladiou, and Zheng we show that the Stanley depth of a monomial ideal in n indeterminates with 2k or 2k+1 generators is at least n-m.
- Degree bounds for Linear Discrepancy of Interval Orders and Disconnected Posets
Discrete Mathematics 310 no. 15-16 (2010), 2198-2203
(with M.T. Keller)
We prove a Brooks-type theorem for the linear discrepancy interval orders, showing that if every interval intersects at most Δ other intervals, then the linear discrepancy is at most Δ, with equality if and only if the interval order contains a antichain of size Δ+1.
- Interval partitions and Stanley Depth
Journal of Combinatorial Theory, Series A 117 no. 4 (2010), 475-482
(with Cs. Biró, D.M. Howard, M.T. Keller, and W.T. Trotter)
We resolve a conjecture of Herzog, Vladiou, and Zheng and prove that the Stanley depth of the maximal ideal over 2k-1 or 2k indeterminates is k. The proof uses a novel partition of the subset lattice and has become to the basis for several results in the combinatorial calculation of Stanley depth.
- On the Stanley depth of squarefree Veronese ideals
Journal of Algebraic Combinatorics 33 no. 2 (2011), 313-324.
(with M.T. Keller, Y. Shen, and N. Streib)
We build on the constructions of the previous paper, calculating the Stanley depth of the degree d squarefree Veronese ideals on n indeterminates when d ≤ n ≤ 5d+4.
- When Linear and Weak Discrepancy are Equal
Discrete Mathematics 311 no. 4 (2011), 252-257.
(with D.M. Howard)
A weak extension of a poset is a order preserving injection onto the natural numbers and thus the weak discrepancy of a poset is the least k such that there is a weak extension where incomparable elements are mapped to numbers of distance at most k. We show that determining whether the weak and linear discrepancy are equal is NP-complete and provide a complete characterization of when the weak and linear discrepancy are equal.
- Posets with cover graph of pathdwidth two have bounded dimeanion
submitted August 2013
(with Cs. Biro and M.T. Keller)
Joret, Micek, Milans, Trotter, Walczak, and Wang recently asked if there is a bound on the dimension of a poset whose cover graph has pathwidth at most two. We answer this question in the affirmative. We also show that any planar embedding of a large standard example has treewidth at least 3.
- Dimension and Structure for Poset of Graph Minors
(with N. Streib)
Inspired by the well-quasi-ordering property of the graph minor theorem, we consider the dimension of the poset formed by the poset of labeled minors of a fixed graph. We show that for trees this is approximately the number of vertices, while for the complete graph this is exponential in the number of vertices. Additionally, we show that if the graph is K2,3- or K2,4-minor free, then the dimension is polynomial in the number of vertices.
- A Major League Baseball Team Uses Operations Research to Improve Draft Preparation
Interfaces 42 no. 2 (2012), 119-130.
(with N. Streib and J. Sokol)
Every year approximately 1200 amateur baseball players are drafted in the Major League Baseball Draft. In order to determine which players to draft a major league team relies primarily on in-person scouting by their scouting department, however, because of cost constraints most scouts see only a small fraction of the players likely to be drafted. We helped a MLB team develop a tool to assist in aggregating the individual scouts evaluations to a consensus ordering of players.
- Towards a weighted version of the Hajnal-Szemeredi Theorem
Combinatorics, Probability, and Computing 22 no. 3 (2013), 346-350
(with J. Balogh, C. Lee, and G. Kemkes)
We considered the question of how large the weighted minimum degree of a complete graph must be to ensure that there was a partition of the graph into sets of size r such that every set contains at has weight at least t. We provide an upper and lower bound for this quantity. The linked version is an expanded version of the journal article.
- Improved Multicommodity Maximum Flow
submitted October 2011
(with F. Chung and W. Zhao)
We provide an improved algorithm for calculating the maximum distributed multicommdity flow using an iterated averaging scheme.