If you have any queries, please contact Allan Lo.
(CANCELLED) Cycle partitions of directed and oriented graphs
- Viresh Patel (QMUL)
- Thursday 18 January 2024, 15:00, Physics West SR1 (103)
A conjecture of Jackson from 1981 states that every n -vertex d -regular oriented graph where n ≤ 4d + 1 has a Hamilton cycle. In the talk I will discuss a proof of this conjecture (for large n ). In fact, I’ll discuss a more general result that establishes, for each fixed k , the degree threshold guaranteeing that a regular directed/oriented graph can be covered with k vertex-disjoint cycles. This is joint work with Allan Lo and Mehmet Akif Yildiz.
Random Turán and counting results for general position sets over finite fields
- Yaobin Chen (Fudan University)
- Thursday 25 January 2024, 15:00, Physics West SR1 (103)
Let α(𝔽qd,p) denote the maximum size of a general position set in a p -random subset of 𝔽qd . We determine the order of magnitude of α(𝔽q2,p) up to polylogarithmic factors for all possible values of p , improving the previous best upper bounds obtained by Roche-Newton–Warren and Bhowmick–Roche-Newton. For d ≥ 3 we prove upper bounds for α(𝔽qd,p) that are essentially tight within certain intervals of p .
We establish the upper bound 2(1+o(1))q for the number of general position sets in 𝔽qd , which matches the trivial lower bound 2q asymptotically in the exponent. We also refine this counting result by proving an asymptotically tight (in the exponent) upper bound for the number of general position sets with fixed size. The latter result for d = 2 improves a result of Roche-Newton–Warren.
Our proofs are grounded in the hypergraph container method, and additionally, for d = 2 we also leverage the pseudorandomness of the point-line incidence bipartite graph of 𝔽q2 . This is a joint work with Xizhi Liu, Jiaxi Nie, Ji Zeng.
On the (k+2,k)-problem of Brown, Erdos and Sos for k=5,6,7
- Shumin Sun (Warwick)
- Thursday 1 February 2024, 15:00, Physics West SR1 (103)
Let f(r)(n;s,k) denote the maximum number of edges in an n-vertex r-uniform hypergraph containing no subgraph with k edges and at most s vertices. In 1973, Brown, Erdős and Sos conjectured that the limit limn → ∞n−2f(3)(n;k+2,k) exists for all k. The value of the limit was previously determined for k = 2 in the original paper of Brown, Erdős and Sos, for k = 3 by Glock and for k = 4 by Glock, Joos, Kim, Kuhn, Lichev and Pikhurko while Delcourt and Postle proved the conjecture (without determining the limiting value).
We determine the value of the limit in the Brown-Erdős-Sos problem for k = 5, 6, 7. More generally, we obtain the value of limn → ∞n−2f(r)(n;rk−2k+2,k) for all r ≥ 3 and k = 5, 6, 7.
This is joint work with Stefan Glock, Jaehoon Kim, Lyuben Lichev and Oleg Pikhurko.
Rigid partitions
- Peleg Michaeli (Oxford)
- Thursday 8 February 2024, 15:00, Physics West SR1 (103)
A graph is called d-rigid if there exists a "generic" embedding of its vertex set into R^d such that every continuous motion of the vertices that preserves the lengths of all edges actually preserves the distances between all pairs of vertices. In this talk, I will present new sufficient conditions for the d-rigidity of a graph in terms of the existence of "rigid partitions" - partitions of the graph that satisfy certain connectivity properties. Following this, I will outline several broadly applicable conditions for the existence of rigid partitions and discuss a few applications, among which are new results on the rigidity of highly connected, (pseudo)random graphs, and dense graphs.
The talk is based on joint work with Michael Krivelevich and Alan Lew.
Optimal Hamilton covers and linear arboricity for random graphs
- Stefan Glock (Passau)
- Thursday 15 February 2024, 15:00, Physics West SR1 (103)
We discuss the following recent result: for p ≥ Clog n/n, with high probability, the edges of the binomial random graph G ∼ G(n,p) can be covered by ⌈Δ(G)/2⌉ Hamilton cycles. This resolves a problem of Glebov, Krivelevich and Szabó, and improves upon previous work of Hefetz, Kühn, Lapinskas and Osthus, and of Ferber, Kronenberg and Long.
The talk is based on joint work with Nemanja Draganic, David Munha Correia and Benny Sudakov.
Weighted intersecting families
- Allan Flower (Birmingham)
- Thursday 22 February 2024, 15:00, Physics West SR1 (103)
Given natural numbers k and n, a k-uniform intersecting family is a subfamily of $[n]^{(k)}$ such that any two elements have non-empty intersection. In this talk, we will discuss the technique of left-compression (shifting) and explore a theory of generating elements for maximally left-compressed intersecting families (MLCIFs). We present an extension of the much-celebrated Erdős-Ko-Rado Theorem, showing that only the k `canonical' k-uniform MLCIFs can be made uniquely optimal under an increasing weight function.
Min-cut Preserving Decompositions in Graphs and Hypergraphs
- Sagnik Mukhopadhyay (Sheffield)
- Thursday 14 March 2024, 15:00, Physics West SR1 (103)
I will discuss the recent advances in graph and hypergraph decompositions that maintain minimum cuts in them. Such decompositions, such as the Kawarabayashi-Thorup decomposition, the expander decomposition and contraction-based decompositions, have seen several implications in fast algorithm design in various models of computation. I will survey these recent results and briefly present our contributions to this end. The talk will borrow materials from a number of works that appeared in STOC, FOCS and SODA in recent years as well as our FOCS 2022 and IPCO 2022 papers.
The Quantitative Helly Theorem
- Nóra Frankl (Open)
- Thursday 21 March 2024, 15:00, **ARTS LR7**
Helly's theorem states that if the intersection of any d+1 members of a finite family F of convex sets in R^d is nonempty, then the intersection of the whole family is nonempty. The Fractional Helly theorem of Katchalski and Liu, and the Quantitative Helly theorem of Bárány, Katchalski, and Pach are two famous extensions of this result. Improving on several recent works, we prove an optimal combination of these two extensions. We show that if a positive fraction of the (d+1)-tuples of F intersect in large volume, then a positive fraction of F intersects in large volume as well. Joint work with Attila Jung and Istvan Tomon.
Previous seminars: Autumn 2006, Spring 2007, Autumn 2007, Spring 2008, Autumn 2008, Spring 2009, Autumn 2009, Spring 2010, 2010-2016, 2016/17, 2017/18, 2018/19, 2019/20, 2020/21, 2021/22, 2022/23, 2023/24