We prove that for $n>k\geq 3$, if $G$ is an $n$-vertex graph with chromatic number $k$ but any its proper subgraph has smaller chromatic number, then $G$ contains at most $n-k+3$ copies of cliques of size $k-1$. This answers a problem of Abbott and Zhou and provides a tight bound on a conjecture of Gallai. This is joint work with Jie Ma.

A temporal graph is a graph whose edges are available only at specific times. In this scenario, the only valid walks are the ones traversing adjacent edges respecting their availability, i.e. sequence of adjacent edges whose appearing times are non-decreasing. Given a graph G and vertices s and t of G, Menger’s Theorem states that the maximum number of (internally) vertex disjoint s,t-paths is equal to the minimum size of a subset X for which G-X contains no s,t-path. This is a classical result in Graph Theory, taught in most basic Graph Theory courses, and it holds also when G is directed and when edge disjoint paths and edge cuts are considered instead. A direct translation of Menger’s Theorem to the temporal context has been known not to hold since an example was shown in the seminal paper by Kempe, Kleinberg and Kumar (STOC’00). In this talk, an overview of possible temporal versions of Menger’s Theorem will be discussed, as well as the complexity of the related problems.

Property testers are probabilistic algorithms aiming to solve a decision problem efficiently in the context of big-data. A property tester for a property P has to decide (with high probability correctly) whether a given input graph has property P or is far from having property P while having local access to the graph. We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree model. We show that any FO property that is defined by a formula with quantifier prefix ∃*∀* is testable, while there exists an FO property that is expressible by a formula with quantifier prefix ∀*∃* that is not testable. In the dense graph model, a similar picture is long known (Alon, Fischer, Krivelevich, Szegedy, Combinatorica 2000), despite the very different nature of the two models. In particular, we obtain our lower bound by a first-order formula that defines a class of bounded-degree expanders, based on zig-zag products of graphs. This is joint work with Isolde Adler and Pan Peng.

We show a flow-augmentation algorithm in directed graphs: There exists a polynomial-time algorithm that, given a directed graph G, two integers $s,t\in V(G)$, and an integer $k$, adds (randomly) to $G$ a number of arcs such that for every minimal st-cut $Z$ in $G$ of size at most $k$, with probability $2^{−\operatorname{poly}(k)}$ the set $Z$ becomes a minimum $st$-cut in the resulting graph. The directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set, whose parameterized complexity status was repeatedly posed as open problems: (1) Chain SAT, defined by Chitnis, Egri, and Marx [ESA'13, Algorithmica'17], (2) a number of weighted variants of classic directed cut problems, such as Weighted st-Cut, Weighted Directed Feedback Vertex Set, or Weighted Almost 2-SAT. By proving that Chain SAT is FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph H, if the List H-Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable. Joint work with Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström.

We call an order type inscribable if it is realized by a point configuration where all extreme points are all on a circle. In this talk, we investigate inscribability of order types. We first show that every simple order type with at most 2 interior points is inscribable, and that the number of such order types is $\Theta(\frac{4^n}{n^{3/2}})$. We further construct an infinite family of minimally uninscribable order types. The proof of uninscribability mainly uses Möbius transformations. We also suggest open problems around inscribability. This is a joint work with Michael Gene Dobbins.

Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its “expectation-threshold,” which is a natural (and often easy to calculate) lower bound on the threshold. In the first talk on Monday, I will introduce the Kahn-Kalai Conjecture with some motivating examples and then briefly talk about the recent resolution of the Kahn-Kalai Conjecture due to Huy Pham and myself. In the second talk on Tuesday, I will discuss our proof of the conjecture in detail.

Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its “expectation-threshold,” which is a natural (and often easy to calculate) lower bound on the threshold. In the first talk on Monday, I will introduce the Kahn-Kalai Conjecture with some motivating examples and then briefly talk about the recent resolution of the Kahn-Kalai Conjecture due to Huy Pham and myself. In the second talk on Tuesday, I will discuss our proof of the conjecture in detail.

Reconstruction of gene regulatory networks (GRNs) is a powerful approach to capture a prioritized gene set controlling cellular processes. In our previous study, we developed TENET a GRN reconstructor from single cell RNA sequencing (scRNAseq). TENET has a superior capability to identify key regulators compared with other algorithms. However, accurate inference of gene regulation is still challenging. Here, we suggest an integrative strategy called TENET+ by combining single cell transcriptome and chromatin accessibility data. By applying TENET+ to a paired scRNAseq and scATACseq dataset of human peripheral blood mononuclear cells, we found critical regulators and their epigenetic regulations for the differentiations of CD4 T cells, CD8 T cells, B cells and monocytes. Interestingly, TENET+ predicted LRRFIP1 and ZBTB16 as top regulators of CD4 and CD8 T cells which were not predicted in a motif-based tool SCENIC. In sum, TENET+ is a tool predicting epigenetic gene regulatory programs in unbiased way, suggesting that novel epigenetic regulations can be identified by TENET+.

Reconstruction of gene regulatory networks (GRNs) is a powerful approach to capture a prioritized gene set controlling cellular processes. In our previous study, we developed TENET a GRN reconstructor from single cell RNA sequencing (scRNAseq). TENET has a superior capability to identify key regulators compared with other algorithms. However, accurate inference of gene regulation is still challenging. Here, we suggest an integrative strategy called TENET+ by combining single cell transcriptome and chromatin accessibility data. By applying TENET+ to a paired scRNAseq and scATACseq dataset of human peripheral blood mononuclear cells, we found critical regulators and their epigenetic regulations for the differentiations of CD4 T cells, CD8 T cells, B cells and monocytes. Interestingly, TENET+ predicted LRRFIP1 and ZBTB16 as top regulators of CD4 and CD8 T cells which were not predicted in a motif-based tool SCENIC. In sum, TENET+ is a tool predicting epigenetic gene regulatory programs in unbiased way, suggesting that novel epigenetic regulations can be identified by TENET+.

Reconstruction of gene regulatory networks (GRNs) is a powerful approach to capture a prioritized gene set controlling cellular processes. In our previous study, we developed TENET a GRN reconstructor from single cell RNA sequencing (scRNAseq). TENET has a superior capability to identify key regulators compared with other algorithms. However, accurate inference of gene regulation is still challenging. Here, we suggest an integrative strategy called TENET+ by combining single cell transcriptome and chromatin accessibility data. By applying TENET+ to a paired scRNAseq and scATACseq dataset of human peripheral blood mononuclear cells, we found critical regulators and their epigenetic regulations for the differentiations of CD4 T cells, CD8 T cells, B cells and monocytes. Interestingly, TENET+ predicted LRRFIP1 and ZBTB16 as top regulators of CD4 and CD8 T cells which were not predicted in a motif-based tool SCENIC. In sum, TENET+ is a tool predicting epigenetic gene regulatory programs in unbiased way, suggesting that novel epigenetic regulations can be identified by TENET+.

This talk will highlight recent results establishing a beautiful computational phase transition for approximate counting/sampling in (binary) undirected graphical models (such as the Ising model or on weighted independent sets). The computational problem is to sample from the equilibrium distribution of the model or equivalently approximate the corresponding normalizing factor known as the partition function. We show that when correlations die off on the infinite D-regular tree then the Gibbs sampler has optimal mixing time of O(n log n) on any graph of maximum degree D, whereas when the correlations persist (in the limit) then the sampling/counting problem are NP-hard to approximate. The Gibbs sampler is a simple Markov Chain Monte Carlo (MCMC) algorithm. Key to these mixing results are a new technique known as spectral independence which considers the pairwise influence of vertices. We show that spectral independence implies an optimal convergence rate for a variety of MCMC algorithms.