Aug 29 - Introduce yourself
Sep 5 - Nicholas Sieger
Title: Random Clustering Graphs and Graph Bootstrap Percolation
Abstract: Many real-world networks exhibit rather different properties than G(n,p), such as power-law degree sequences and clustering coefficients. In prior work, Fan Chung and I introduced random clustering graphs a random graph model which possesses several features of a real-world network without using geometric assumptions common in previous models of real-world graphs. In this talk. I will define random clustering graphs, show how to how to compute the subgraph counts needed for clustering, and highlight some connections to Graph Bootstrap Percolation.
Sep 12 - Grace McCourt
Title: A hypergraph analog of Dirac's Theorem for long cycles in 2-connected graphs
Abstract: Dirac proved that an n-vertex graph with minimum degree k \geq 2 contains a cycle of length at least k+1, and furthermore if the graph is 2-connected then it contains a cycle of length at least \min\{2k, n\}. We prove a hypergraph version of this result: for n \geq k \geq r+2 \geq 5, every 2-connected, r-uniform, n-vertex hypergraph with minimum degree at least {k-1 \choose r-1} + 1 contains a Berge cycle of length at least \min\{2k, n\}. The bound is exact. We also prove new bounds for 3 \leq k \leq r+1, which are exact for k=r+1 and differ from the exact by at most 1 when 3 \leq k \leq r. This is joint work with Alexandr Kostochka and Ruth Luo.
Sep 19 - Bernard Lidicky
Title: Almost all k-sat functions are unate
Abstract: We prove that 1-o(1) fraction of all k-SAT functions on n Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer k and as n goes to infinity. This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003. Dong, Mani, and Zhao reduced the conjecture to a Turán problem on partially directed hypergraphs. We solve this Turán problem.
This is joint work with József Balogh, Dingding Dong, Nitya Mani, and Yufei Zhao.
Sep 26 - Nick Veldt
Title: Saturation Bounds for the poset 2C2
Abstract: The extremal number of a graph G is the maximum number of edges that can exist on n vertices without containing a subgraph isomorphic to G. The dual problem of this is the saturation number, the minimum number of edges such that the graph does not contain G, but where adding any edge forces G to exist as a subgraph. We can extend this concept to the environment of partially ordered sets, and various results exist for both extremal and saturation numbers for certain poset structures. In this talk, I will discuss the induced saturation number of the poset 2C2, which is the poset consisting of four elements {A, B, C, D} which have the relations A < B and C < D, and no others.
Oct 3 - Anna Halfpap
Title: Positive co-degree density: properties and values
Abstract: Given an r-graph H, the co-degree of a set S of (r-1) vertices in H is the number of r-edges containing S. The co-degree Turán number of an r-graph F is the largest possible minimum co-degree in an n-vertex r-graph which doesn't contain F as a subgraph. With Lemons and Palmer, we recently introduced the following variation. The minimum positive co-degree of H is the largest integer k such that if a set S of (r-1) vertices in H is contained in some r-edge, then S is contained in at least k r-edges. The positive co-degree Turán number of an r-graph F is the largest possible minimum positive co-degree in an n-vertex r-graph which doesn't contain F as a subgraph. In this talk, we will motivate the positive co-degree Turán number and discuss some recent results on the values which the positive co-degree Turán number can (and cannot) achieve. Joint work with József Balogh, Nathan Lemons, Bernard Lidický, and Cory Palmer.
Oct 10 - Lina Li
Title: Lipschitz functions on weak expanders.
Abstract: Given a connected finite graph $G$, an integer-valued function $f$ on $V(G)$ is called $M$-Lipschitz if the value of $f$ changes by at most $M$ along the edges of $G$. In 2013, Peled, Samotij, and Yehudayoff showed that random $M$-Lipschitz functions on graphs with sufficiently good expansion typically exhibit small fluctuations, giving sharp bounds on the typical range of such functions, assuming $M$ is not too large. We prove that the same conclusion holds under a relaxed expansion condition and for larger $M$, (partially) answering questions of Peled et al.
This is joint work with Robert A. Krueger and Jinyoung Park.
Oct 17 -
Ilkyoo Choi (travel postponed)
Title: An improved lower bound on the number of edges in list critical graphs via DP-coloring.
Abstract: A graph $G$ is (list, DP) $k$-critical if the (list, DP) chromatic number is $k$ but for every proper subgraph $G'$ of $G$, the (list) chromatic number of $G'$ is less than $k$. For $k\geq 4$, we show a bound on the minimum number of edges in a DP $k$-critical graph, and our bound is the first bound that is asymptotically better than the corresponding bound for proper $k$-critical graphs by Gallai from 1963. Our result also improves the best bound on the list chromatic number.
Oct 24 - Ce Chen
Title: On the maximum F-free induced subgraphs in K_t-free graphs
Abstract: For graphs F and H, let f_{F,H}(n) be the minimum possible size of a maximum F-free induced subgraph in an n-vertex H-free graph, which is a generalization of both the Ramsey function and the Erd\H{o}s--Rogers function. Assuming the existence of certain locally dense H-free graphs, we give a general upper bound on f_{F,H}(n) by establishing a container lemma for the F-free subgraphs. In particular, we improve the upper bound on f_{F,H}(n) when H is K_4 and F is an even cycle. This is joint work with J\'{o}zsef Balogh and Haoran Luo.
Oct 31 - Sanket Wagle
Title: Exact diameters for cluster-based phylogenetic costs
Abstract: Quantitatively comparing binary trees is crucial in many fields, from phylogenetics to machine learning. Consequently, developing efficient and accurate tree comparison costs is a mature and highly active research area. We introduce two new costs - the Asymmetric Cluster Affinity cost and the Cluster Support cost based on comparing the elementary cluster representations of trees. We further describe the diameter of these costs and analyze the performance of these costs in simulated scenarios. This is a joint work with Oliver Eulenstein, Alexey Markin, Tavis Anderson and Paweł Górecki.
Nov 7 - Diane Puges
Title: Flag algebras for limits of dense trees
Abstract: While trees are usually considered sparse objects, they turn dense when considering only the leaves to be the "vertices" of a tree. In this framework, an induced subtree is defined as the smallest tree containing a given subset of leaves, where inner vertices of degree 2 are contracted. We can then introduce notions of densities for these trees, in both finite and infinite trees. We define as well the inducibility of a tree as its maximum density over all possible trees of size growing to infinity. We apply Razborov's flag algebra theory to the setting of leaf-labeled rooted binary trees, which allows us to use polynomial optimization techniques to efficiently obtain new bounds on the inducibilities of trees. We obtain as well the first approximations of profiles of trees, representing the possible simultaneous densities of a pair of trees. Moreover, we are able to prove several points on the boundary of some of these these profiles and prove their non-convexity .
Nov 14 - Songling Shan (zoom)
Title: Linear arboricity of graphs with large minimum degree
Abstract: In 1980, Akiyama, Exoo, and Harary conjectured that any graph $G$ can be decomposed into at most $\lceil(\Delta(G)+1)/2\rceil$ linear forests. We confirm the conjecture for sufficiently large graphs with large minimum degree. Precisely, we show that for any given $0<\varepsilon <1$, there exists $n_0 \in \mathbb{N}$ for which the following statement holds:
If $G$ is a graph on $n\ge n_0$ vertices of minimum degree at least $(1+\ve)n/2$, then $G$ can be decomposed into at most $\lceil(\Delta(G)+1)/2\rceil$ linear forests.
This is joint work with Yuping Gao.
Nov 21 - Sean English
Title: Rational Exponents for Generalized Turan Numbers
Abstract: The extremal number of the graph F, denoted ex(n, F), is the maximum number of edges in an F-free graph on n vertices. The inverse rational exponent conjecture (perhaps first posed by Erdos and Simonovits in ’81) postulates that for each rational number r in [1, 2], there exists some graph F such that ex(n, F) grows on the order of magnitude of n^r.
Recently, Bukh and Conlon proved a slightly weaker version of this conjecture - if one allows for finite families of forbidden graphs, then such a family does exist for each rational r. We will show that a generalization of this conjecture also holds. Given two graphs F and H, the generalized extremal number ex(n, H, F) is the maximum number of copies of H in an F-free graph on n vertices (note that ex(n, F) = ex(n, K_2, F)). We will explore which rational exponents are realizable for some different graphs H, and in particular show that every reasonable rational number is realizable for all cliques K_s . Upper bounds will be derived from a particular counting scheme, while lower bounds will stem from a random algebraic construction.
This is joint work with Anastasia Halfpap and Bob Krueger
Dec 5 - Spring 2024 RTG
Title: Proper Rainbow Saturation for Cycles, Paths, and Cliques
Abstract: Given a graph $H$, we say that a graph $G$ is properly rainbow $H$-saturated if there exists some proper edge-coloring of $G$ which has no rainbow copy of $H$, yet the addition of any edge $e$ to $G$ forces any proper edge-coloring of $G + e$ to have a rainbow copy of $H$. We denote the minimum number of edges in a properly rainbow $H$-saturated graph on $n$ vertices by $\text{sat}^*(n,H)$. In this talk, we discuss new bounds on the proper rainbow saturation number for odd cycles, paths, and cliques.
Dec 12 - Enrique Alvarado
Title: Parameter Selection for Mapper
Abstract: Mapper is a popular Topological Data Analysis tool that is used to investigate the shape and features of point cloud data. Other than the data, the Mapper algorithm needs a few more parameters. It needs a topological space Y, an open cover of Y, and a function (called a filter function) that maps your data into Y. In the context of the application, sometimes there is a natural choice for the filter function, and hence Y. However, it is rarely the case that there is a natural choice for the open cover of Y. In this talk, we will investigate recent work concerning optimally choosing the open cover for Y, related inverse Mapper/Reeb Space problems, and relationships between Mapper and intersection patterns of convex sets.