Graph Pebbling

Faculty: Glenn Hurlbert

Graph Pebbling is a network optimization model for the transportation of resources that are consumed in transit. Electricity, heat, or other energy may dissipate as it moves from one location to another, oil tankers may use up some of the oil it transports, information may be lost as it travels through its medium, or military troops may be lost while moving through a region. The central problem in this model asks whether discrete pebbles from one set of vertices can be moved to another while pebbles are lost in the process. A typical question asks how many pebbles are necessary to guarantee that, from any configuration of that many pebbles, one can move a pebble to (“solve”) any particular vertex. A fractional version asks for the limiting behavior of the average number of pebbles used per “solution”. Instead of placing the initial pebbles cleverly, if the original configuration is chosen at random then we can wonder what the probability is that every vertex can be solved, which gives rise to the notion of a threshold, which divides almost sure success and almost sure failure. One may also ask: how few pebbles can be used so that, from some configuration of that many pebbles, one can move a pebble to any particular vertex; how many pebbles are required to guarantee that, from any configuration of that many pebbles, some pebble can travel at least some fixed distance; and other questions. Various rules for pebbling steps have been studied for years and have found applications in a wide array of areas: computational complexity theory (time-space tradeoffs), optimal register allocation for compilers, pursuit and evasion games (e.g. combating computer viruses), graph searching, computational linear algebra (Cholesky factorization of large sparse matrices), computational geometry (rigidity of graphs, matroids,  and other structures), combinatorial number theory and combinatorial group theory (zero sum theory), and p-adic diophantine equations. Most of these rules give rise to computationally difficult problems. Currently I am working on conjectures related to structured graphs such as chordal graphs.  There are many, many open problems in this area for interested students to work on.

Universal Cycles

Faculty: Glenn Hurlbert

A deBruijn cycle of order n is a cyclic listing of 0s and 1s with every binary n-tuple appearing exactly once contiguously in  the cycle. A Gray code is a listing of all binary n-tuples so that adjacent n-tuples differ by just one bit.  Both of these are examples of Universal Cycles, listings of combinatorial objects that are efficient for various applications in Communications, Cryptography, Randomization, Computer Science, and elsewhere.  Recently there has been much work on these in the area of Combinatorial Designs, which are important in Statistics, in addition to the above.  There are a number of outstanding questions to answer, and a new book (Ordering Block Designs, by Dewar & Stevens) that outlines the current frontiers.

Intersection Theory

Faculty: Glenn Hurlbert

From a population of n people, how many committees can be formed so that every pair of committees share a common member?  What if the size of each committee is fixed, or is even (or is odd)?  What if each committee must share k members?  What if, instead of committees (subsets) of people (elements) we ask about other combinatorial structures such as partitions or permutations of a set, or subspaces of a vector space, etc?  These are all basic questions in intersection theory, a specialty within extremal set theory and combinatorics that has fundamental applications to wide ranging disciplines such as polynomial algebra, probability, group theory, circuit complexity, statistics, number theory, graph coloring, geometry, and more. Recently I have been pursuing questions regarding independent sets in graphs (especially in trees), as well as the following 1972 conjecture of Chvatal:  if F is a family of sets that is closed under taking subsets then the largest intersecting subfamily of F consists of those sets of F that contain some fixed element.

Algebraic Operations on Graphs

Faculty: Richard Hammack

My primary research interest is in graph theory, a highly visual branch of mathematics concerned with networks of interconnections between nodes. I am especially fascinated by algebraic operations on graphs. For example, there are various ways to multiply graphs together to get new graphs, or, conversely to factor a given graph into a product of smaller graphs. This leads to many questions: Do graphs factor uniquely into prime graphs, the way that numbers factor uniquely into prime numbers? If A × C = B × C for three graphs A, B and C, can we conclude A = B? Can you divide one graph into another? What would it look like? There are fascinating answers to such questions, as well as many, many unsolved mysteries.

The research that I have done with students has led to about 10 published papers so far.

Graph Coloring

Faculty: Dan Cranston
Collaborators: Landon Rabern

For a graph G, we write χ(G), Δ(G), and ω(G) for the chromatic number, maximum degree, and clique number of G. Brooks showed that χ(G) ≤ max{ω(G), Δ(G)}, when Δ(G) ≥ 3. Borodin and Kostochka conjectured that χ(G) ≤ max{ω(G), Δ(G)-1} when Δ(G) ≥ 9. If true, this is best possible. We have proved this conjecture for claw-free graphs (those with no induced K1,3). The contrapositive of the conjecture says that if Δ(G) ≥ 9 and χ(G) ≥ Δ(G), then ω(G) ≥ Δ(G). In this direction, we showed that if Δ(G) ≥ 13 and χ(G) ≥ Δ(G), then ω(G) ≥ Δ(G)-3.

Graph Brain Project

Faculty: Craig Larson

Craig Larson and Nico Van Cleemput (Ghent University) have developed the Conjecturing program which can produce conjectures in any area of mathematics. Graph Theory is defined in part by its published concepts (invariants and properties), examples and counterexamples, theorems, and open problems.

One goal of this project is to code all published concepts, examples and counterexamples, and theorems. This is a long-term, massive project, which will ultimately require the work of a community of interested researchers.

As we add published graph theory knowledge we will continually propose experiments and investigate how advancing knowledge allows our program to advance research on existing graph theory problems.

Some of our experiments have included generating invariant and property conjectures in a variety of mathematical domains, developing a conjecture-based sequence guessing program, a conjecture-based Chomp playing program, as well as a conjecture-based program for classification of objects from their features. The possible experiments are limited only by your imagination!

Here is a link for a 2107 Graph Brain summer research project:

Sensory Inputs and Fluctuations in Cortical Neural Networks

Faculty: Cheng Ly



Structure-Exploiting Approaches for Solving Stochastic Programs

Faculty: Yongjia Song

Collaborators: Jim Luedtke (University of Wisconsin-Madison), Simge Kucukyavuz (The Ohio State University) We study structure-exploiting approaches for solving stochastic programs using a scenario-based formulation, which may come from the sample average approximation of the original stochastic program. In particular, we study chance-constrained combinatorial optimization problems and two-stage stochastic programs with fixed recourse. For chance-constrained combinatorial optimization problems, we propose a formulation in their original spaces, without using additional binary variables. This formulation could be strengthened by taking advantage of the particular problem structure, for example, the network structure or the packing structure. For two-stage stochastic programs with fixed recourse, we propose a finitely converging algorithm by adaptively adjusting the partition until it yields an optimal solution. A solution guided refinement strategy is developed to exploit the relaxation solution that corresponds to this partition. We conduct extensive computational study to demonstrate the effectiveness of proposed approaches on stochastic optimization problems with a large number of scenarios.

Multi-Scale Modeling of Ventilator-Induced Lung Injury


Pollen Dispersal

Faculty: David Chan
Collaborators: Rodney Dyer (VCU)

We are studying pollen movement through insect dispersal in dogwood at the VCU Rice Center for Environmental Research.  In this project we are developing a variety of models and performing several experiments to better understand the behavior of insects in dispersing pollen.  Gene movement within a plant population in a complex process and also critical for sustaining species in not only forests but also in agricultural and urban environments.

Optimization Models of Cellular Metabolism

Faculty: Paul Brooks
Collaborators: Stephen Fong (VCU)

This work involves the design and analysis of algorithms for constructing models of cellular metabolism. This modeling paradigm embodies the principles of Systems Biology in that the interactions of the components of the entire cell can be analyzed simultaneously. These models can be used to predict the effects of metabolic engineering of cellular organisms. Specific examples including engineering bacteria for maximizing the production of ethanol for biofuels and predicting modifications that will kill disease-causing organisms.