• home

Aaron will speak on the paper "An introduction to the discharging method via graph coloring” by Dan Cranston and Doug West.

Abstract: In this talk, we will investigate the extensions of the cycle matroid of a complete graph. I will show that the number of these extensions is surprisingly large.

Please contact the organizer for the Zoom link.

Abstract:
In 1975, Pippenger and Golumbic instigated the study of the maximum number of induced copies of a small graph H which can be contained in an n-vertex graph G. This problem has received considerable attention over the years, yet there remain many small graphs H for which the maximum is not known asymptotically, including the path on four vertices and many graphs on five vertices. The case where H is a cycle is of particular interest and was solved for 5-cycles for large enough n by Balogh, Hu, Lidický, and Pfender in 2016.

In this talk we will discuss recent progress on the analogous problem in the setting where the graphs G and H are planar. In particular, for sufficiently large n we determine exactly the maximum numbers of induced 4-, 5-, and 6-cycles that can be contained in a planar graph on n vertices and we classify the graphs which achieve these maxima.

Please contact the organizer if you need the Zoom link.

Aaron will talk about the (classic) paper "Domination in Graphs with Minimum Degree Two" by William McCuaig and Bruce Shepherd (Journal of Graph Theory, 1989).

Abstract: Generating functions are an invaluable tool in many areas of discrete mathematics. In this talk we view generating functions as a data structure for combinatorial sequences and ask how efficiently we can determine properties such as asymptotics. This naturally leads us to consider the new field of analytic combinatorics in several variables (ACSV). The methods of ACSV rely on advanced results from complex analysis in several variables, topology, and algebraic and differential geometry -- giving the field a reputation for powerful methods which can be difficult for new researchers to get a firm grasp on. This talk aims to "demystify" ACSV by surveying some of its main results, software implementations, and recent applications of the theory.

Please contact the organizer for the Zoom link.

Abstract:

It was shown recently by Delcourt and Postle that any sufficiently large graph G of order n with minimum degree at least 0.827n has a fractional triangle decomposition, i.e. an assignment of weights to the triangles in G such that for every edge e, the total of all weights of triangles containing e is exactly one.

In this talk, I will consider a variant on this problem for 3-partite host graphs. This setting is a bit trickier, because triangle weights are typically moved around in the dense setting using cliques of order 4 or 5, and these are unavailable in 3-partite graphs. Using a different method, an analogous minimum degree threshold is computed for a balanced 3-partite graph to admit a fractional triangle decomposition.

One motivation is that the problem of completing partial Latin squares can be cast in terms of triangle-decomposition of 3-partite graphs. Applying a result of Barber, Kühn, Lo, Osthus and Taylor, our fractional threshold implies an honest-to-goodness threshold, and hence a result on completing sparse partial Latin squares of large order.

This is based on joint work with Flora Bowditch.

Abstract: In this talk, I will discuss several Turán-type results for point-line incidences. It will be based on joint works with Istvan Tomon and Mozhgan Mirzaei.

This is part of the Round the World Relay in Combinatorics.