Georgia Institute of Technology College of Sciences

 When does a graph admit an orientation with some desired properties? This question has been studied extensively for many years and across many different properties. Specifically, I will talk about properties having to do with degree restrictions, and progress towards a conjecture of Akbari, Dalirrooyfard, Ehsani, Ozeki, and Sherkati dealing with a list-type of degree restriction. This is all joint work with my PhD advisor Jessica McDonald.

A matroid $M$ is a pair $(E, \mathcal{I})$ where $E$ is a finite set, called the {\em ground set} of $M$, and $\mathcal{I}$ is a non-empty collection of subsets of $E$, called {\em independent sets} of $M$, such that (1) a subset of an independent set is independent; and (2) if $I$ and $J$ are independent sets with $|I| < |J|$, then exists $x \in J \backslash I$ such that $I \cup \{x\}$ is independent. 

A graph $G$ gives rise to a matroid $M(G)$ where the ground set is $E(G)$ and a subset of $E(G)$ is independent if it spans a forest. Another example is a matroid that comes from a matrix over a field $F$: the ground set $E$ is the set of all columns and a subset of $E$ is independent if it is linearly independent over $F$. 

Tutte's Wheel and Whirl Theorem and Seymour's Splitter Theorem are two well-known inductive tools for proving results for 3-connected graphs and matroids. In this talk, we will give a survey on induction theorems for various versions of 4-connected matroids and graphs.   
 

For integers $k>\ell\ge0$, a graph $G$ is $(k,\ell)$-stable if  $\alpha(G-S)\geq \alpha(G)-\ell$ for every    
$S\subseteq V(G)$ with $|S|=k$. A recent result of Dong and Wu [SIAM J.
Discrete Math. 36 (2022) 229--240] shows that every $(k,\ell)$-stable 
graph $G$  satisfies $\alpha(G) \le  \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell$.  A $(k,\ell)$-stable graph $G$   is   tight if $\alpha(G) = \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell$; and  $q$-tight for some integer $q\ge0$ if $\alpha(G) = \lfloor ({|V(G)|-k+1})/{2}\rfloor+\ell-q$.
In this talk, we first prove  that for all $k\geq 24$, the only tight $(k, 0)$-stable graphs are $K_{k+1}$ and  $K_{k+2}$, answering a question of Dong and Luo [arXiv: 2401.16639]. We then prove that  for all nonnegative integers $k, \ell, q$ with $k\geq 3\ell+3$, every $q$-tight $(k,\ell)$-stable graph has at most  $k-3\ell-3+2^{3(\ell+2q+4)^2}$ vertices, answering a question of Dong and Luo in the negative.   \\  

This is joint work with Xiaonan Liu and Zhiyu Wang. 

Many problems in rigidity theory and matrix completion boil down to finding a nice combinatorial description of some matroid supported on the edge set of a complete (bipartite) graph. In this talk, I will give many such examples. My goal is to convince you that a general theory of matroids supported on graphs is needed and to give you a sense of what that could look like.