Fall 2024 schedule: Thursdays 4-5 pm, W303

Fall 2024 Schedule

• September 12, 2024, 4:00-5:00pm, W303 - Evelyne Smith-Roberge

Title: Correspondence Packings of Planar Graphs

Abstract: Suppose a graph G has list chromatic number k. It is easy to see that if L is a (k+1)-list assignment for G, then G admits two L-colourings f and g where f(v) =/= g(v) for every vertex v in the graph. But what if we want still more disjoint L-colourings without making our lists too big? In this talk, I will discuss progress towards determining the list packing number of various classes of planar graphs: that is, the smallest number k such that if L is a k-list assignment for an arbitrary graph G in the class under study, then L can be decomposed into k disjoint L-colourings. All results I will discuss also hold in the correspondence colouring framework. Joint work with Daniel Cranston.

• September  19 , 2024, 4:00-5:00pm, W303 - Sam Spiro

Title: The Random Tur\'an Problem

Abstract: Let $G_{n,p}$ denote the random $n$-vertex graph obtained by including each edge independently and with       probability $p$. Given a graph $F$, let $\mathrm{ex}(G_{n,p},F)$ denote the size of a largest $F$-free subgraph of $G_{n,p}$. When $F$ is non-bipartite, the asymptotic behavior of $\mathrm{ex}(G_{n,p},F)$ is determined by breakthrough work done independently by Conlon-Gowers and by Schacht, but the behavior for bipartite $F$ remains largely unknown. We will discuss some recent developments that have been made for bipartite $F$, as well as for the analogous problem on $r$-partite $r$-graphs which turns out to have a surprising connection to Sidorenko's conjecture.  Based on various joint works with Jiaxi Nie, Gwen McKinley, and Jacques Verstraete.

• October 4, 2024, 4:00-5:00pm, W303 - Marcelo Sales (not the unusal date - it is Friday)

Title: On the Ramsey number of daisies

Abstract: Daisies are a special type of hypergraph introduced by Bollob\'{a}s, Leader and Malvenuto. An $r$-daisy

determined by a pair of disjoint sets $K$ and $M$ is the $(r+|K|)$-uniform hypergraph $\{K\cup P:\: P\in M^{(r)}\}$. We 

discuss upper and lower bounds for the Ramsey number of $r$-daisies, which are natural generalizations of classical 

Ramsey numbers. This is joint work with Pavel Pudl\'{a}k and Vojt\v{e}ch R\"{o}dl.

• October 10, 2024, 4:00-5:00pm, W303  - James Davies 

Title: Non-measurable colourings avoiding large distances

Abstract: In 1983, Furstenberg, Katznelson, and Weiss proved that for every finite measurable colouring of the plane, there exists a $d_0$ such that for all $d\geq d_0$ there is a monochromatic pair of points at distance $d$. In contrast to this,  we show that there is a finite colouring avoiding arbitrarily large distances. This is joint work with Rutger Campbell.

• October 23, 2024, 4:00-5:00pm, W303 - Meike Hatzel (not the unusal date - it is Wednesday)

Title: Erdős-Pósa property of tripods in directed graphs

Abstract: Let $D$ be a directed graphs with distinguished sets of sources

$S\subseteq V(D)$ and sinks $T\subseteq V(D)$.

     A \emph{tripod} in $D$ is a subgraph consisting of the union of two

$S$-$T$-paths that have distinct start-vertices and the same end-vertex,

and are disjoint apart from sharing a suffix.

     We prove that tripods in directed graphs exhibit the Erdős-Pósa property.

     More precisely, there is a function $f\colon \mathds{N}\to \mathds{N}$

such that for every digraph $D$ with sources $S$ and sinks $T$, if $D$

does not contain $k$ vertex-disjoint tripods, then there is a set of at

most $f(k)$ vertices that meets all the tripods in $D$.

This is joint work with Marcin Briański, Karolina Okrasa, and Michał

Pilipczuk.

• October 31 , 2024, 4:00-5:00pm, W303  Jiaxi Nie 

Title: Off-diagonal Ramsey numbers  for slowly growing hypergraphs

Abstract: For a $k$-uniform hypergraph $F$ and a positive integer $n$, the Ramsey number $r(F,n)$ denotes the minimum $N$ such that every $N$-vertex $F$-free $k$-uniform hypergraph contains an independent set of $n$ vertices. A  hypergraph is  slowly growing if there is an ordering $e_1,e_2,\dots,e_t$ of its edges such that $|e_i \setminus \bigcup_{j = 1}^{i - 1}e_j| \leq  1$ for each $i \in \{2, \ldots, t\}$. We prove that if $k \geq 3$ is fixed and $F$ is any non $k$-partite slowly growing $k$-uniform hypergraph, then for $n\ge2$,  

\[ r(F,n) = \Omega\Bigl(\frac{n^k}{(\log n)^{2k - 2}}\Bigr).\]

In particular, we deduce that  the off-diagonal Ramsey number $r(F_5,n)$ is of order $n^{3}/\mbox{polylog}(n)$, where $F_5$ is the triple system $\{123, 124, 345\}$. This is the only 3-uniform Berge triangle for which the  polynomial power of its off-diagonal Ramsey number was not previously known. Our constructions use pseudorandom graphs,  martingales, and hypergraph containers.

• November 7, 2024, 4:00-5:30pm, W303 - Asaf Ferber, ACC meeting

Title: Quantum Algorithms on Graphs

Abstract: In this talk, I will provide a brief introduction to quantum computation and demonstrate its potential for accelerating classical graph algorithms. Specifically, I will present an asymptotically tight result for learning a Hamiltonian cycle using OR queries, as well as a significant polynomial improvement on the best-known quantum algorithm for (Δ+1)-coloring a graph with maximum degree Δ.

This work is based on joint research with Liam Hardiman (UCI) and Xiaonan Chen (UCI).

• November 14, 2024, 4:00-5:00pm, W303 - Maya Sankar

Title: The Turán Density of 4-Uniform Tight Cycles

Abstract: For any uniformity r and residue k modulo r, we give an exact characterization of the r-uniform hypergraphs that homomorphically avoid tight cycles of length k modulo r, in terms of colorings of (r-1)-tuples of vertices. This generalizes the result that a graph avoids all odd closed walks if and only if it is bipartite, as well as a result of Kam?ev, Letzter, and Pokrovskiy in uniformity 3. In fact, our characterization applies to a much larger class of families than those of the form C_k^(r)={r-uniform tight cycles of length k modulo r}. We also outline a general strategy to prove that, if C is a family of tight-cycle-like hypergraphs (including but not limited to the families C_k^(r)) for which the above characterization applies, then all sufficiently long cycles in C will have the same Turán density. We demonstrate an application of this framework, proving that there exists an integer L_0 such that for every L>L_0 not divisible by 4, the tight cycle C^(4)_L has Turán density 1/2.

• December 3, 2024, 4:00-5:00pm, E408 - Mathias Schacht

Title: Canonical Ramsey numbers for partite hypergraphs

Abstract: We consider quantitative aspects of the canonical Ramsey theorem of Rado

for k-partite k-uniform hypergraphs. For the complete bipartite graph

K_{t,t} it was recently shown by Dobak and Mulrenin that these numbers

grow exponential in t log(t) and considering random edge colourings

shows that this bound is asymptotically optimal. We extend this result

to k-uniform hypergraphs and obtain a bound exponential in poly(t). This

is joint work with Giovanne Santos and Matias Azocar.

• December 5, 2024, 4:00-5:00pm, W303 - Marton Naszodi

Title: Higher rank antipodality

Abstract:

Motivated by general probability theory, we say that the set $X$ in

$\mathbb{R}^d$ is \emph{antipodal of rank $k$}, if for any $k+1$

elements $q_1,\ldots q_{k+1}\in X$, there is an affine map from

$\mathrm{conv} X$ to the $k$-dimensional simplex $\Delta_k$ that maps

$q_1,\ldots q_{k+1}$ onto the $k+1$ vertices of $\Delta_k$. For $k=1$,

it coincides with the well-studied notion of (pairwise) antipodality

introduced by Klee.

We consider the following natural generalization of Klee's problem on

antipodal sets: What is the maximum size of an antipodal set of rank $k$

in $\mathbb{R}^d$? We present a geometric characterization of antipodal

sets of rank $k$ and adapting the argument of Danzer and Gr{\"u}nbaum

originally developed for the $k=1$ case, we prove an upper bound which

is exponential in the dimension. We point out that this problem can be

connected to a classical question in computer science on finding

\emph{perfect hashes}, and it provides a lower bound on the maximum

size, which is also exponential in the dimension. Joint work with

Zsombor Szil{\'a}gyi and Mih{\'a}ly Weiner.

Spring 2024 Schedule

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.

• February  16 , 2024, 4:00-5:00pm, W201 - ACC meeting, Mathias  Schacht
  Title: Canonical colourings in random graphs

Abstract: Rodl and Rucinski established Ramsey's theorem for random graphs. In particular, for fixed integers r, l \geq 2  they showed that n^{-2/(l+1)} is a threshold for the Ramsey property that every r-colouring of the edges of the binomial random graph G(n,p) yields a monochromatic copy of K_l. We investigate how this result extends to arbitrary colourings of G(n,p) with an unbounded number of colours. In this situation Erdos and Rado showed that canonically coloured copies of K_l can be ensured in the deterministic setting. We transfer the Erdos--Rado theorem to the random environment and show that for l\geq 4 both thresholds coincide. As a consequence the proof yields $K_{l+1}$-free graphs G for which every edge colouring yields a canonically coloured K_l. This is joint work with Nina Kamcev.

• March  4, 2024, 10:00-11:00am, W201 - Tibor Szabo

• March 26, 2024, 10:00-11:00am, W301 - Tung Nguyen

Title: A few steps towards the Erdős–Hajnal conjecture

Abstract: A cornerstone of Ramsey theory says that every graph contains a clique or independent set of logarithmic size, which is asymptotically optimal for almost all graphs. The Erdős–Hajnal conjecture from 1977 predicts a very different situation in graphs with forbidden induced subgraphs; more precisely, the conjecture asserts that for every graph $H$, there exists $c=c(H)>0$ such that every $n$-vertex graph with no induced copy of $H$ has a clique or independent set of size at least $n^c$. This conjecture remains open, and we will discuss recent progress on it in the talk.

• March 29, 2024, 4-5pm, W201 - Andrzej Rucinski

• April 11, 2024, 10:00-11:00am, E406 - Amzi Jeffs

Title: Are there sparse codes with large convex embedding dimension?

Abstract: How can you arrange a collection of convex sets in Euclidean space? This question underpins the study of "convex codes," a vein of research that began in 2013 motivated by the study of hippocampal place cells in neuroscience. Classifying convex codes is exceedingly difficult, even in the plane, and gives rise to a number of striking examples and neat geometric theorems. We will focus on a particular open question about how the sparsity of a code relates to its embedding dimension, and some recent partial progress.

• April 25, 2024, 4-5pm - Jacque Verstraete, ACC meeting (hosted by Georgia State University)

Title: Recent progress in Ramsey Theory

The Ramsey number $r(s,t)$ denotes the minimum $N$ such that in any red-blue coloring of the edges of the complete graph $K_N$, there exists a red $K_s$ or a blue $K_t$. While the study of these quantities goes back almost one hundred years, to early papers of Ramsey and Erd\H{o}s and Szekeres, the long-standing conjecture of Erd\H{o}s that $r(s,t)$ has order of magnitude close to $t^{s - 1}$ as $t \rightarrow \infty$ remains open in general.

It took roughly sixty years before the order of magnitude of $r(3,t)$ was determined by Jeong Han Kim, who showed $r(3,t)$ has order of magnitude $t^2/(\log t)$ as $t \rightarrow \infty$. In this talk, we discuss a variety of new techniques which lead to the lower bound in the following statement: for some constants $a,b > 0$ and $t \geq 2$,

\[ a\frac{t^3}{(\log t)^4} \leq r(4,t) \leq b\frac{t^3}{(\log t)^2}.\]

This solves a conjecture of Erd\H{o}s. We also come close to determining related quantities known as Erd\H{o}s-Rogers functions, as well as determine the current best bounds for other graph Ramsey numbers.

• April 26, 2024, 4-5pm, W201

Title: Erdos-Rogers Functions

Abstract: The Erdos-Rogers functions are generalizations of Ramsey numbers, introduced around fifty years ago. The general question given graphs $F$ and $H$ is to determine the maximum number of vertices $f(n,F,H)$ in an $F$-free induced subgraph of any $H$-free $n$-vertex graph. The case $F = K_2$ is equivalent to determining Ramsey numbers $r(H,t)$. 

The case $F$ and $H$ are cliques has received considerable attention. In this talk we give almost tight bounds, showing that for $s > 3$,  $$ f(n,K_s,K_{s-1}) = \sqrt{n}(\log n)^{\Theta(1)} $$, where the exponent of the logarithm is between $1/2 - o(1)$ and $1 + o(1)$. We also give new bounds on Ramsey numbers $r(F,t)$. 

In part joint work with David Conlon, Sam Mattheus and Dhruv Mubayi.

Fall  2023 Schedule

• August  30 , 2023, 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: : Everywhere unbalanced configurations

Abstract:  An old problem in discrete geometry, originating with Kupitz, asks whether there is a fixed natural number $k$ such that every finite set of points in the plane has a line through at least two of its points where the number of points on either side of this line differ by at most $k$. We give a negative answer to the pseudoline variant of this problem. Joint work with David Conlon.

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

Title: An exponential improvement for diagonal Ramsey

Abstract: The Ramsey number R(k) is the minimum n such that every red-blue colouring of the edges of the complete graph on n vertices 

contains a monochromatic copy of K_k. It has been known since the work of Erdos and Szekeres in 1935, and Erdos in 1947, that 2^{k/2} <       R(k) < 4^k, but in the decades since the only improvements have been by lower order terms. In this talk I will sketch the proof of a recent         result, which improves the upper bound of Erdos and Szekeres by a (small) exponential factor. 

Based on joint work with Marcelo Campos, Simon Griffiths and Julian Sahasrabudhe.

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

Title: The asymptotics of $r(4,t)$

Abstract: I will give an overview of recent work, joint with Jacques Verstraete, where we gave an improved lower bound for the off-diagonal Ramsey number $r(4,t)$, solving a long-standing conjecture of Erd\H{o}s. Our proof has a strong non-probabilistic component, in contrast to previous work. This approach was generalized in further work with David Conlon, Dhruv Mubayi and Jacques Verstraete to off-diagonal Ramsey numbers $r(H,t)$ for any fixed graph $H$. We will go over of the main ideas of these proofs and indicate some open problems.

• November 8, 2023, 4:00-5:00pm, E406 -  Richard Montgomery

Title: Packing the largest trees in the tree packing conjecture

Abstract: The well-known tree packing conjecture of Gyárfás from 1976

says that, given any sequence of n trees in which the ith tree has i

vertices, the trees can be packed edge-disjointly into the complete

n-vertex graph. Packing even just the largest trees in such a sequence

has proven difficult, with Bollobás drawing attention to this in 1995 by

conjecturing that, for each k, if n is sufficiently large then the

largest k trees in any such sequence can be packed. This has only been

shown for k at most 5, by Zak, despite many partial results and much

related work on the full tree packing conjecture.

I will discuss a result which proves Bollobás's conjecture by showing

that, moreover, a linear number of the largest trees can be packed in 

the tree packing conjecture. This is joint work with Barnabás Janzer.

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

Title: The Structural Szemerédi–Trotter problem

Abstract: The Szemerédi–Trotter theorem can be considered as the fundamental theorem of

geometric incidences. This combinatorial theorem has an unusually wide variety of

applications, in combinatorics, theoretical computer science, harmonic analysis, number theory, model       theory, and more. Surprisingly, hardly anything is known about the structural question - characterizing         the cases where the theorem is tight. 

In this talk, we will survey the status of the structural (or inverse) Szemerédi–Trotter problem, including      several recent results.       This is a basic survey talk and does not require previous knowledge of the     field. Joint works with Shival Dasu, and Olivine Silier. 

• November 29, 2023, 4:00-5:00pm, E406 - Alexey Pokrovskiy , as part of Atlanta Combinatorics Colloquium

Title: Ascending subgraph decompositions

Abstract: A graph G has a decomposition in to graphs H1...Hm, if the edges of G can be partitioned into edge-disjoint copies of each of H1...Hm. A typical theme for many well-known decomposition problems is to show that some obvious necessary conditions for decomposing a graph G into copies H1,…,Hm are also sufficient. One such problem was posed by Alavi, Boals, Chartrand, Erdős, and Oellerman. They conjectured that the edges of every graph with (m+1 choose 2) edges can be decomposed into subgraphs H1,…,Hm such that each Hi has i edges and is isomorphic to a subgraph of H_{i+1}. This talk will be about a proof of this for sufficiently large n.

Joint work with Kyriakos Katsamaktsis, Shoham Letzter, and Benny Sudakov.

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.