Georgia Institute of Technology College of Sciences

The online matching problem has received significant attention in recent years because of its connections to allocation problems in internet advertising, crowd sourcing, etc. In these real-world applications, the typical goal is not to maximize the number of allocations; rather it is to maximize the number of “successful” allocations, where success of an allocation is governed by a stochastic event that comes after the allocation. These applications motivate us to introduce stochastic rewards in the online matching problem. In this talk, I will formally define this problem, point out its connections to previously studied allocation problems, give a deterministic algorithm that is close to optimal in its competitive ratio, and describe some directions of future research in this line of work. (Based on joint work with Aranyak Mehta.)

A (5,2)-configuration in a graph G is a function which maps the vertices of G into 2-element subsets of {1,2,3,4,5} in such a way that for every vertex u, the union of the 2-element subsets assigned to u and all its neighbors is {1,2,3,4,5}. This notion is motivated by a problem in robotics. Fujita, Yamashita and Kameda showed that every 3-regular graph has a (5,2)-configuration. In this talk, we will prove that except for four graphs, every graph of minimum degree at least two which does not contain K_{1,6} as an induced subgraph has a (5,2)-configuration. This is joint work with Waseem Abbas, Magnus Egerstedt, Robin Thomas, and Peter Whalen.

Fifty years ago Erdos asked to determine the minimum number of $k$-cliques in a graph on $n$ vertices with independence number less than $l$ (we will refer this as $(k,l)$-problem). He conjectured that this minimum is achieved by the disjoint union of $l-1$ complete graphs of size $\frac{n}{l-1}$. This conjecture was disproved by Nikiforov who showed that Erdos' conjecture can be true only for finite many pairs of $(k,l)$. For $(4,3)$-problem, Nikiforov further conjectured that the balanced blow-up of a $5$-cycle achieves the minimum number of $4$-cliques. We first sharpen Nikiforov's result and show that Erdos' conjecture is false whenever $k\ge 4$ or $k=3, l\ge 2074$. After introducing tools (including Flag Algebra) used in our proofs, we state our main theorems, which characterize the precise structure of extremal examples for $(3,4)$-problem and $(4,3)$-problem, confirming Erdos' conjecture for $(k,l)=(3,4)$ and Nikiforov's conjecture for $(k,l)=(4,3)$. We then focus on $(4,3)$-problem and sketch the proof how we use stability arguments to get the extremal graphs, the balanced blow-ups of $5$-cycle. Joint work with Shagnik Das, Hao Huang, Humberto Naves and Benny Sudakov.

A signed graph is a pair $(G,\Sigma)$ where $G$ is an undirected graph (in which parallel edges are permitted, but loops are not) and $\Sigma \subseteq E(G)$. The edges in $\Sigma$ are called odd and the other edges are called even. A cycle of $G$ is called odd if it has an odd number of odd edges. If $U\subseteq V(G)$, then re-signing $(G,\Sigma)$ on $U$ gives the signed graph $(G,\Sigma\Delta \delta(U))$. A signed graph is a minor of $(G,\Sigma)$ if it comes from $(G,\Sigma)$ by a series of re-signing, deletions of edges and isolated vertices, and contractions of even edges. If $(G,\Sigma)$ is a signed graph with $n$ vertices, $S(G,\Sigma)$ is the set of all symmetric $n\times n$ matrices $A=[a_{i,j}]$ with $a_{i,j} > 0$ if $i$ and $j$ are connected by only odd edges, $a_{i,j} < 0$ if $i$ and $j$ are connected by only even edges, $a_{i,j}\in \mathbb{R}$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $i$ and $j$ are not connected by any edges, and $a_{i,i} \in \mathbb{R}$ for all vertices $i$. The stable inertia set, $I_s(G,\Sigma)$, of a signed graph $(G,\Sigma)$ is the set of all pairs $(p,q)$ such that there exists a matrix $A\in S(G,\Sigma)$ that has the Strong Arnold Hypothesis, and $p$ positive and $q$ negative eigenvalues. The stable inertia set of a signed graph forms a generalization of $\mu(G)$, $\nu(G)$ (introduced by Colin de Verdi\`ere), and $\xi(G)$ (introduced by Barioli, Fallat, and Hogben). A specialization of $I_s(G,\Sigma)$ is $\nu(G,\Sigma)$, which is defined as the maximum of the nullities of positive definite matrices $A\in S(G,\Sigma)$ that have the Strong Arnold Hypothesis. This invariant is closed under taking minors, and characterizes signed graphs with no odd cycles 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 $I_s(G,\Sigma)$, $\nu(G,\Sigma)$ and these characterizations. Joint work with Marina Arav, Frank Hall, and Zhongshan Li.