Georgia Institute of Technology College of Sciences

We shall discuss a recent paper of Wanless and Wood (arXiv:2008.00775), which proves a Lovász Local Lemma type result using inductive counting arguments.
For example, in the context of hypergraph colorings, under LLL-type assumptions their result typically gives exponentially many colorings (usually more than the textbook proof of LLL would give).
We will present a probabilistic proof of the Wanless-Wood result, and discuss some applications to k-SAT, Ramsey number lower bounds, and traversals, as time permits.

We consider rooted subgraphs in random graphs, i.e., extension counts such as (i) the number of triangles containing a given vertex or (ii) the number of paths of length three connecting two given vertices. 
In 1989, Joel Spencer gave sufficient conditions for the event that, with high probability, these extension counts are asymptotically equal for all choices of the root vertices.  
For the important strictly balanced case, Spencer also raised the fundamental question whether these conditions are necessary. 
We answer this question by a careful second moment argument, and discuss some intriguing problems that remain open. 

We study self-similar and fractal networks from the combinatorial perspective. We establish analogues of topological (Lebesgue) and fractal (Hausdorff) dimensions for graphs and demonstrate that they are naturally related to known graph-theoretical characteristics: rank dimension and product (or Prague or Nešetřil-Rödl) dimension. Our approach reveals how self-similarity and fractality of a network are defined by a pattern of overlaps between densely connected network communities. It allows us to identify fractal graphs, explore the relations between graph fractality, graph colorings and graph Kolmogorov complexity, and analyze the fractality of several classes of graphs and network models, as well as of a number of real-life networks. We demonstrate the application of our framework to evolutionary studies by revealing the growth of self-organization of heterogeneous viral populations over the course of their intra-host evolution, thus suggesting mechanisms of their gradual adaptation to the host's environment. As far as the authors know, the proposed approach is the first theoretical framework for study of network fractality within the combinatorial paradigm. The obtained results lay a foundation for studying fractal properties of complex networks using combinatorial methods and algorithms.

Based on joint work with Leonid Bunimovich

We  show  that  if  $P\neq NP$,  then  a  wide  class  of  TSP heuristics fail to approximate the length of the TSP to asymptotic 
optimality, even for random Euclidean instances.  Previously, this result was not even known for any heuristics (greedy, etc) used in practice.  As an application, we show that when  using  a  heuristic from  this  class,  a  natural  class  of  branch-and-bound algorithms takes exponential time to find an optimal tour (again, even on a random point-set),  regardless  of  the  particular  branching  strategy  or lower-bound algorithm used.