Emory Combinatorics Seminar

# When: Wednesdays 4-5 pm, E406

Note that the time and the place are subject to change based on speaker's or attendees' availability, always double-check on a particular date.

Upcoming Seminars

Note that in parallel to Emory Discrete Maths seminar, together with Anton Bernsteyn and Yi Zhao , we are running Atlanta Combinatorics Colloquium, which is a series of lectures, hosted by Georgia Tech, Georgia State and Emory, happening once per month in Fall and Spring semesters.

August 30 , 2022, 4:00-5:00pm, E406 - Corinne Yap

Title: Reconstructing Random Pictures

Abstract: Reconstruction problems ask whether or not it is possible to uniquely build a discrete structure from the collection of its substructures of a fixed size. This question has been explored in a wide range of settings, most famously with graphs and the resulting Graph Reconstruction Conjecture due to Kelly and Ulam, but also including geometric sets, jigsaws, and abelian groups. In this talk, we'll consider the reconstruction of random pictures (n-by-n grids with binary entries) from the collection of its k-by-k subgrids and prove a nearly-sharp threshold for k = k(n). Our main proof technique is an adaptation of the Peierls contour method from statistical physics. Joint work with Bhargav Narayanan.

September 21, 2023, 4:00-5:00pm, at Georgia Tech - ACC meeting, Maria Chudnovskiy

Title: k-Blocks and forbidden induced subgraphs

Abstract: A k-block in a graph is a set of k vertices every two of which are joined by k vertex disjoint paths. By a result of Weissauer, graphs with no k-blocks admit tree-decompositions with especially useful structure. While several constructions show that it is probably very difficult to characterize induced subgraph obstructions to bounded tree width, a lot can be said about graphs with no k-blocks. On the other hand, forbidding induced subgraphs places significant restrictions on the structure of a k-block in a graph. We will discuss this phenomenon and its consequences on the study of tree-decompositions in classes of graphs defined by forbidden induced subgraphs.

September 27, 2023, 4:00-5:00pm, E406 - Natasha Morrison

Title: Maximising copies of H in K_{r+1}-free graphs

Abstract: Let H be a graph. We show that if r is large enough as a function of H, then the r-partite Turán graph maximizes the number of copies of H among all Kr+1-free graphs on a given number of vertices. This confirms a conjecture of Gerbner and Palmer. This is joint work with JD Nir, Sergey Norin, Pawel Rzazewski, Alexandra Wesolek.

October 4, 2023, 4:00-5:00pm, E406 - Ron Gould

Title: Have you Ever Meta-Conjectured?

Abstract: The study of cycles in graphs has a long history.

In 1971 A. Bondy noted a tie linking hamiltonian graphs and pancyclic graphs. He stated his famou meta- conjecture: Almost any nontrivial condition on a graph which implies the graph is hamiltonian also implies the graph is pancyclic. There may be some simple family of exceptional graphs. A cycle contains a chord if there exists an edge between two vertices of the cycle that is not an edge of the cycle. A cycle is said to be chorded if it has one or more chords. In this talk I will extend Bondy's meta-conjecture in several ways to a broader class of cycle problems in graphs, namely to finding conditions that imply the existence of chorded cycles in graphs. I will offer supporting evidence to these meta-conjectures.

October 11, 2023, 4:00-5:00pm, E406 - Jeck Lim

Title: TBD

Abstract: TBD

October 18, 2023, 4:00-5:00pm, at Georgia State, ACC meeting - Rob Morris

Title: TBD

Abstract: TBD

October 25, 2023, 4:00-5:00pm, E406 - Sam Mattheus

Title: TBD

Abstract: TBD

November 15, 2023, 4:00-5:00pm, E406 - Adam Sheffer

Title: TBD

Abstract: TBD

November 29, 2023, 4:00-5:00pm, E406 - Alexey Pokrovskiy

Title: TBD

Abstract: TBD

Combinatorics graduate reading seminar (Fall 2022 schedule)

September 9 , 2022, 3:30pm, E408 - Sean Longbrake on https://arxiv.org/abs/2208.10457

September 16 , 2022, 3:30pm, E408 - Sean Longbrake on https://arxiv.org/abs/2208.10457

September 23 , 2022, 3:30pm, E408 - Anton Molnar on https://arxiv.org/abs/2201.08204

September 30, 2022, 3:30pm, E408 - Griffin Johnston on https://arxiv.org/abs/2006.01062

October 7, 2022, 3:30pm, E408 - Griffin Johnston on https://arxiv.org/abs/2006.01062

October 18, 2022, 10:00am, E406 - Ayush Basu on https://arxiv.org/abs/1809.04716

October 25, 2022, 10:00am, E406 - Ayush Basu on https://arxiv.org/abs/1809.04716

November 4, 2022 - 3:30pm, E408- Sean Longbrake on https://arxiv.org/pdf/2208.10572.pdf

November 29, 2022 - 10:00am, E406 - Anton Molnar on https://homepages.math.uic.edu/~mubayi/papers/Pseudorandom.pdf

December 2, 2022 - 3:30pm, E408 - Ayush Basu on https://arxiv.org/abs/1404.5079

Past Seminars

March 28, Monday, 2023, 4:30-5:30pm - Mathias Schacht

March 17, Friday, 2023, 4-5pm, W201- Matija Bucic

January 31, 2023, Tuesday, 4-5pm - Cosmin Pohoata

Title: Convexity, color avoidance, and perfect hash codes

Abstract: In this (informal) talk, I will discuss some favorite open problems which are related in some way or another with the Erdős-Szekeres problem and the polynomial method.

February 9, 2023, Thursday, 4-5pm - Alp Müyesser

Title: Matchings in hypergraphs defined by groups

Abstract: When can we find perfect matchings in hypergraphs whose vertices represent group elements and edges represent solutions to systems of linear equations? A prototypical problem of this type is the Hall-Paige conjecture, which asks for a characterisation of the groups whose multiplication table (viewed as a Latin square) contains a transversal. Other problems expressible in this language include the toroidal n-queens problem, Graham-Sloane harmonious tree-labelling conjecture, Ringel's sequenceability conjecture, Snevily's subsquare conjecture, Tannenbaum's zero-sum conjecture, and many others. All of these problems have a similar flavour, yet until recently they have been approached in completely different ways, using algebraic tools ranging from the combinatorial Nullstellensatz to Fourier analysis. In this talk we discuss a unified approach to attack these problems, using tools from probabilistic combinatorics. In particular, we will see that a suitably randomised version of the Hall-Paige conjecture can be used as a black-box to settle many old problems in the area for sufficiently large groups. Joint work with Alexey Pokrosvkiy.

December 7, 2022 - 3-4 pm, W301 - David Conlon, Caltech (as part of ACC, Emory University)

Title: Sumset estimates in higher dimensions

Abstract: We will describe recent progress, in joint work with Jeck Lim, on the study of sumset estimates in higher dimensions. The basic question we discuss is the following: given a subset A of d-dimensional space and a linear transformation L, how large is the sumset A + LA?

November 18, 2022 - 3:30-4:30 pm, E408 - Tao Jiang, Miami University

Title: The Turán problem for bipartite graphs

Abstract: Extremal problems in graph theory, generally speaking, study the interaction

between the density of a graph and substructures occurring in it. A natural and central problem of this nature asks for how dense a grap can be when it is missing a particular subgraph. These problems are known as Turán problems. These problems have played a central role in the development of extremal graph theory.

While the celebrated he Erdős–Stone -Simonovits theorem essentially solves the problem when the missing subgraph H is non-bipartite, much less is known when H is bipartite. While there have been steady movements on the problem in the past, there has been an increased amount of progress in recent years due to fresh ideas and angles to approach these problems. In this talk, we will survey some of the recent progresses and techniques/ideas involved in them and suggest further problems to explore.

November 11, 2022, 4:00-5:00pm, 25 Park Place, Room 223 - Penny Haxell, University of Waterloo (as part of ACC, Georgia State)

Title: The Integrality Gap for the Santa Claus Problem

Abstract: In the max-min allocation problem, a set of players are to be allocated disjoint subsets of a set of indivisible resources, such that the minimum utility among all players is maximized. In the restricted variant, also known as the Santa Claus Problem, each resource ("toy") has an intrinsic positive value, and each player ("child") covets a subset of the resources. Thus Santa wants to distribute the toys amongst the children, while (to satisfy jealous parents?) wishing to maximize the minimum total value of toys received by each child. This problem turns out to have a natural reformulation in terms of hypergraph matching.

Bezakova and Dani showed that the Santa Claus problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. To date, the principal approach for obtaining approximation algorithms has been via the Configuration LP of Bansal and Sviridenko, and bounds on its integrality gap. The existing algorithms and integrality gap estimations tend to be based one way or another on a combinatorial local search argument for finding perfect matchings in certain hypergraphs.

Here we introduce a different approach, which in particular replaces the local search technique with the use of topological methods for finding hypergraph matchings. This yields substantial improvements in the integrality gap of the CLP, from the previously best known bound of 3.808 for the general problem to 3.534. We also address the well-studied special case in which resources can take only two values, and improve the integrality gap in most cases. This is based on joint work with Tibor Szabo.

October 28, 2022, 3:30-4:30pm, W306 - Matthew Jenssen, University of Birmingham

Title: Algorithmic and combinatorial applications of the cluster expansion

Abstract: The cluster expansion is a classical tool from statistical physics traditionally used to study the phase diagram of lattice spin models. Recently, the cluster expansion has enjoyed a number of applications in two new contexts: i) the design of efficient approximate counting and sampling algorithms for spin models on graphs and ii) classical enumeration problems in combinatorics. In this talk, I’ll give an introduction to the cluster expansion and discuss some of these recent developments.

October 21, 2022, 4:00-5:00pm, -Bharghav Narayanan , Rutgers University (as part of ACC, Georgia Tech, Instructional Center 105)

Title: Friendly Bisections of Random Graphs

Abstract: It is easy to partition the vertices of any graph into two sets where each vertex has at least as many neighbours across as on its own side; take any maximal cut! Can we do the opposite? This is not possible in general, but Füredi conjectured in 1988 that it should nevertheless be possible on a random graph. I shall talk about our recent proof of Füredi's conjecture: with high probability, the random graph G(n, 1/2) on an even number of vertices admits a partition of its vertex set into two parts of equal size in which n – o(n) vertices have more neighbours on their own side than across.

April 1, 2022, 4-5pm, W303 - Zilin Jiang, Arizona State University

Title: Forbidden subgraphs and spherical two distance sets

Abstract: Given a real number λ, what can we say about the family G(λ) of graphs with eigenvalues bounded from below by -λ? The Cauchy interlacing theorem implies that that the family G(λ) is closed under taking (induced) subgraphs. Similar to Wagner’s theorem, which describes the family of planar graphs by finite forbidden minors, it is natural to ask for which λ the family G(λ) has a finite forbidden subgraph characterization. In this talk, I will illustrate the key ideas in answering this question, and I will demonstrate a peculiar connection to spherical two distance sets — a set of unit vectors in a Euclidean space the pairwise inner products of which assume only two values. Joint work with Alexandr Polyanskii, Jonathan Tidor, Yuan Yao, Shengtong Zhang and Yufei Zhao.

March 16, 2022, E406 - Anton Bernshteyn, Georgia Tech

Title: Weak degeneracy of graphs

Abstract: Motivated by the study of greedy algorithms for graph coloring, we introduce a new graph parameter, which we call weak degeneracy. This notion formalizes a particularly simple way of "saving" colors while coloring a graph greedily. It turns out that many upper bounds on chromatic numbers follow from corresponding bounds on weak degeneracy. In this talk I will survey some of these bounds as well as state a number of open problems. This is joint work with Eugene Lee (Carnegie Mellon University).

February 23, 2022, W303 - Bharghav Narayanan , Rutgers University

Title: Probabilistic Bezout over finite fields, and some applications

Abstract: What is the distribution of the number of distinct roots of k random polynomials (of some fixed degree) in k variables? I will talk about a recently proved Bezout-like theorem that gives us a satisfactory answer over (large) finite fields. This result can be used to construct several interesting families of “extremal graphs”. I shall illustrate this method by 1) discussing the easiest applications in detail, reproving some well-known lower bounds in extremal graph theory, and 2) outlining how this method has recently found applications in establishing hardness results for a few basic computational problems.