Seminars and Colloquia by Series

On a conjecture of Graham on the p-divisibility of central binomial coefficients

Series
Combinatorics Seminar
Time
Friday, September 16, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Ernie CrootGeorgia Institute of Technology

I will discuss an old conjecture of Ron Graham on whether there are infinitely many integers $n$ so that $\mathrm{gcd}({{2n} \choose n}, 105)=1$, as well as recent progress on a version of this problem where 105 is replaced with a product of $r$ distinct primes. This is joint work with Hamed Mousavi and Maxie Schmidt.

The cluster expansion and combinatorics

Series
Combinatorics Seminar
Time
Friday, September 9, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Will PerkinsGeorgia Institute of Technology

The cluster expansion is a classical tool from statistical physics used to understand systems of weakly interacting particles in the high temperature regime of statistical physics models.  It can also be a very useful tool in probabilistic, extremal, and enumerative combinatorics and in the study of large deviations in probability theory.  I will give an introduction to the cluster expansion, present some examples of combinatorial applications, and try to provide some intuition about when the cluster expansion should or should not be a useful tool for a particular problem.

Arc-Intersection Queries Amid Triangles in Three Dimensions and Related Problems

Series
Combinatorics Seminar
Time
Tuesday, July 26, 2022 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 202
Speaker
Esther EzraBar Ilan University

Let T be a set of n triangles in 3-space, and let \Gamma be a family of
algebraic arcs of constant complexity in 3-space. We show how to preprocess T
into a data structure that supports various "intersection queries" for
query arcs \gamma \in \Gamma, such as detecting whether \gamma intersects any
triangle of T, reporting all such triangles, counting the number of
intersection points between \gamma and the triangles of T, or returning the
first triangle intersected by a directed arc \gamma, if any (i.e., answering
arc-shooting queries). Our technique is based on polynomial partitioning and
other tools from real algebraic geometry, among which is the cylindrical
algebraic decomposition.

Our approach can be extended to many other intersection-searching problems in
three and higher dimensions. We exemplify this versatility by giving an
efficient data structure for answering segment-intersection queries amid a set
of spherical caps in 3-space, and we lay a roadmap for extending our approach
to other intersection-searching problems.

Joint work with Pankaj Agarwal, Boris Aronov, Matya Katz, and Micha Sharir.

Two conjectures on the spread of graphs

Series
Combinatorics Seminar
Time
Friday, April 29, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Michael TaitVillanova University

Given a graph $G$ let $\lambda_1$ and $\lambda_n$ be the maximum and minimum eigenvalues of its adjacency matrix and define the spread of $G$ to be $\lambda_1 - \lambda_n$. In this talk we discuss solutions to a pair of 20-year-old conjectures of Gregory, Hershkowitz, and Kirkland regarding the spread of graphs.
   
The first, referred to as the spread conjecture, states that over all graphs on $n$ vertices the join of a clique of order $\lfloor 2n/3 \rfloor$ and an independent set of order $\lceil n/3 \rceil$ is the unique graph with maximum spread. The second, referred to as the bipartite spread conjecture, says that for any fixed $e\leq n^2/4$, if $G$ has maximum spread over all $n$-vertex graphs with $e$ edges, then $G$ must be bipartite.

We show that the spread conjecture is true for all sufficiently large $n$, and we prove an asymptotic version of the bipartite spread conjecture. Furthermore, we exhibit an infinite family of counterexamples to the bipartite spread conjecture which shows that our asymptotic solution is tight up to a multiplicative factor in the error term. This is joint work with Jane Breen, Alex Riasanovsky, and John Urschel.

Partitioning cubic graphs into isomorphic linear forests

Series
Combinatorics Seminar
Time
Friday, April 22, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Liana YepremyanEmory University

A cubic graph is one where every vertex has degree three. A linear forest is a disjoint union of paths. It is known that the edge set of every cubic graph can be partitioned into two linear forests where each path is short (of constant size). A conjecture of Wormald asks for such a partition where the two forests are isomorphic (we no longer insist on having short paths, although that is also an open question). Note that this also can be phrased as an edge-colouring question. Is it possible to colour the edge set of a cubic graph by red and blue such that the two monochromatic components induce isomorphic linear forests? Recently we proved this for all connected graphs on a sufficiently large number of vertices. I will talk about the result and give some idea of the proof method. This is joint work with Gal Kronenberg, Shoham Letzter and Alexey Pokrovskiy.

Exponential decay of intersection volume and applications

Series
Combinatorics Seminar
Time
Friday, April 15, 2022 - 09:00 for 1 hour (actually 50 minutes)
Location
Zoom
Speaker
Hong LiuECOPRO, IBS

Please Note: Note the unusual time!

When do two balls in a metric space have small intersection? We give some natural conditions to guarantee an exponential decay on the volume of such intersections. Our proof is conceptually simple, making use of concentration of measure on a "slice." We will discuss a couple of applications of this volume estimate in coding theory. This is joint work with Jaehoon Kim and Tuan Tran.

Incest and infanticide: a branching process with deletions and mergers that matches the threshold for hypercube percolation

Series
Combinatorics Seminar
Time
Friday, April 8, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Fiona SkermanUppsala University / Simon's Institute

We define a graph process based on a discrete branching process with deletions and mergers, which is inspired by the 4-cycle structure of the hypercube $\mathcal{Q}_d$ for large $d$. We prove survival and extinction under certain conditions on $p$ and $q$ that heuristically match the known expansions of the critical probabilities for bond percolation on the hypercube. Joint work with Laura Eslava and Sarah Penington. Based on https://arxiv.org/abs/2104.04407.

Discrete vs. definable combinatorics of Schreier graphs

Series
Combinatorics Seminar
Time
Friday, April 1, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Felix WeilacherCarnegie Mellon University

We discuss the relationship between the Borel/Baire measurable/measurable combinatorics of the action of a finitely generated group on its Bernoulli shift and the discrete combinatorics of the multiplication action of that group on itself. Our focus is on various chromatic numbers of graphs generated by these actions. We show that marked groups with isomorphic Cayley graphs can have Borel/Baire measurable/measurable chromatic numbers which differ by arbitrarily much. In the Borel two-ended, Baire measurable, and measurable hyperfinite settings, we show our constructions are nearly best possible (up to only a single additional color). Along the way, we get tightness of some bounds of Conley and Miller on Baire measurable and measurable chromatic numbers of locally finite Borel graphs.

Definable combinatorics in hyperfinite graphs

Series
Combinatorics Seminar
Time
Friday, March 18, 2022 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Matthew BowenMcGill University

We discuss a few new results concerning the descriptive combinatorics of bounded degree hyperfinite Borel graphs. In particular, we show that the Baire measurable edge chromatic number of $G$ is at most $\lceil\frac{3}{2}\Delta(G)\rceil+6$ when G is a multigraph, and for bipartite graphs we improve this bound to $\Delta(G)+1$ and show that degree regular one-ended bipartite graphs have Borel perfect matchings generically. Similar results hold in the measure setting assuming some hyperfiniteness conditions. This talk is based on joint work with Kun and Sabok, Weilacher, and upcoming work with Poulin and Zomback.

Vertex-minors and structure for dense graphs

Series
Combinatorics Seminar
Time
Friday, December 3, 2021 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Rose McCartyUniversity of Waterloo

Structural graph theory has usually focused on classes of graphs that are 'sparse' rather than 'dense' (that is, have few edges rather than many edges). We discuss this paradigm, focusing on classes with a forbidden vertex-minor. In particular, we discuss progress on a conjecture of Geelen that would totally characterize classes with a forbidden vertex-minor. This is joint work with Jim Geelen and Paul Wollan.

Pages