### TBA by Jeffrey Rosenthal

- Series
- Combinatorics Seminar
- Time
- Friday, April 17, 2020 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Jeffrey Rosenthal – University of Toronto

TBA (joint with Stochastics Seminar)

- You are here:
- GT Home
- Home
- News & Events

- Series
- Combinatorics Seminar
- Time
- Friday, April 17, 2020 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Jeffrey Rosenthal – University of Toronto

TBA (joint with Stochastics Seminar)

- Series
- Combinatorics Seminar
- Time
- Friday, March 27, 2020 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Lutz Warnke – Georgia Tech

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.

- Series
- Combinatorics Seminar
- Time
- Friday, March 13, 2020 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Mihai Ciucu – Indiana University Bloomington

Cancelled due to COVID-19

- Series
- Combinatorics Seminar
- Time
- Friday, March 6, 2020 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Pavel Skums – Georgia State University – pskums@gsu.edu

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

- Series
- Combinatorics Seminar
- Time
- Friday, February 28, 2020 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles atrium
- Speaker

No seminar due to the "Special tea" fro the Admitted Student Day, which is 3-4 pm in the Skiles atrium.

- Series
- Combinatorics Seminar
- Time
- Friday, February 7, 2020 - 15:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Wesley Pegden – Carnegie Mellon University

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.

- Series
- Combinatorics Seminar
- Time
- Friday, January 31, 2020 - 15:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Andrei (Cosmin) Pohoata – California Inst. of Technology, Pasadena, CA – apohoata@caltech.edu

It is a classical theorem of Roth that every dense subset of $\left\{1,\ldots,N\right\}$ contains a nontrivial three-term arithmetic progression. Quantitatively, results of Sanders, Bloom, and Bloom-Sisask tell us that subsets of relative density at least $1/(\log N)^{1-\epsilon}$ already have this property. In this talk, we will discuss some sets of $N$ integers which unlike $\left\{1,\ldots,N\right\}$ do not contain nontrivial four-term arithmetic progressions, but which still have the property that all of their subsets of density at least $1/(\log N)^{1-\epsilon}$ must contain a three-term arithmetic progression. Perhaps a bit surprisingly, these sets turn out not to have as many three-term progressions as one might be inclined to guess, so we will also address the question of how many three-term progressions can a four-term progression free set may have. Finally, we will also discuss about some related results over $\mathbb{F}_{q}^n$. Based on joint works with Jacob Fox and Oliver Roche-Newton.

- Series
- Combinatorics Seminar
- Time
- Friday, January 24, 2020 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Andrii Arman – Emory University – andrii.arman@emory.edu

In this talk I will discuss algorithms for a uniform generation of random graphs with a given degree sequence. Let $M$ be the sum of all degrees and $\Delta$ be the maximum degree of a given degree sequence. McKay and Wormald described a switching based algorithm for the generation of graphs with given degrees that had expected runtime $O(M^2\Delta^2)$, under the assumption $\Delta^4=O(M)$. I will present a modification of the McKay-Wormald algorithm that incorporates a new rejection scheme and uses the same switching operation. A new algorithm has expected running time linear in $M$, under the same assumptions.

I will also describe how a new rejection scheme can be integrated into other graph generation algorithms to significantly reduce expected runtime, as well as how it can be used to generate contingency tables with given marginals uniformly at random.

This talk is based on the joint work with Jane Gao and Nick Wormald.

- Series
- Combinatorics Seminar
- Time
- Friday, January 10, 2020 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 202
- Speaker
- Lutz Warnke

We shall discuss the recent breakthrough of Annika Heckel on the chromatic number of the binomial random graph G(n,1/2), showing that it is not concentrated on any sequence of intervals of length n^{1/4-o(1)}.

To put this into context, in 1992 Erdos (and also Bollobás in 2004) asked for any non-trivial results asserting a lack of concentration, pointing out that even the weakest such results would be of interest.

Until recently this seemed completely out of reach, in part because there seemed to be no obvious approach/strategy how to get one's foot in the door.

Annika Heckel has now found such an approach, based on a clever coupling idea that compares the chromatic number of G(n,1/2) for different n.

In this informal talk we shall try to say a few words about her insightful proof approach from https://arxiv.org/abs/1906.11808

Please note the unusual room (Skiles 202)

- Series
- Combinatorics Seminar
- Time
- Friday, December 6, 2019 - 13:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Jinyoung Park – Rutgers University

(This is a joint event of the Combinatorics Seminar Series and the ACO Student Seminar.)

In this talk we will prove a conjecture of Talagrand, which is a fractional version of the “expectation-threshold” conjecture of Kalai and Kahn. This easily implies various difficult results in probabilistic combinatorics, e.g. thresholds for perfect hypergraph matchings (Johansson-Kahn-Vu) and bounded-degree spanning trees (Montgomery). Our approach builds on recent breakthrough work of Alweiss, Lovett, Wu, and Zhang on the Erdos-Rado “Sunflower Conjecture.”

This is joint work with Keith Frankston, Jeff Kahn, and Bhargav Narayanan.

- Offices & Departments
- News Center
- Campus Calendar
- Special Events
- GreenBuzz
- Institute Communications
- Visitor Resources
- Campus Visits
- Directions to Campus
- Visitor Parking Information
- GTvisitor Wireless Network Information
- Georgia Tech Global Learning Center
- Georgia Tech Hotel & Conference Center
- Barnes & Noble at Georgia Tech
- Ferst Center for the Arts
- Robert C. Williams Paper Museum