For a given graph $H$, we say that a graph $G$ has a perfect $H$-subdivision tiling if $G$ contains a collection of vertex-disjoint subdivisions of $H$ covering all vertices of $G.$ Let $\delta_{sub}(n, H)$ be the smallest integer $k$ such that any $n$-vertex graph $G$ with minimum degree at least $k$ has a perfect $H$-subdivision tiling. For every graph $H$, we asymptotically determined the value of $\delta_{sub}(n, H)$. More precisely, for every graph $H$ with at least one edge, there is a constant $1 < \xi^*(H)\leq 2$ such that $\delta_{sub}(n, H) = \left(1 - \frac{1}{\xi^*(H)} + o(1) \right)n$ if $H$ has a bipartite subdivision with two parts having different parities. Otherwise, the threshold depends on the parity of $n$.

Pivot-minors can be thought of as a dense analogue of graph minors. We shall discuss pivot-minors and two recent results for proper pivot-minor-closed classes of graphs. In particular, that for every graph H, the class of graphs containing no H-pivot-minor is 𝜒-bounded, and also satisfies the (strong) Erdős-Hajnal property.

Configurations of axis-parallel boxes in $\mathbb{R}^d$ are extensively studied in combinatorial geometry. Despite their perceived simplicity, there are many problems involving their structure that are not well understood. I will talk about a construction that shows that their structure might be more complicated than people conjectured.

In this talk, we will discuss the problem of determining the maximum number of edges in an n-vertex k-critical graph. A graph is considered k-critical if its chromatic number is k, but any proper subgraph has a chromatic number less than k. The problem remains open for any integer k ≥ 4. Our presentation will showcase an improvement on previous results achieved by employing a combination of extremal graph theory and structural analysis. We will introduce a key lemma, which may be of independent interest, as it sheds light on the partial structure of dense k-critical graphs. This is joint work with Cong Luo and Jie Ma.

We give a summary on the work of the last months related to Frankl's Union-Closed conjecture and its offsprings. The initial conjecture is stated as a theorem in extremal set theory; when a family F is union-closed (the union of sets of F is itself a set of $\mathcal F$), then $\mathcal F$ contains an (abundant) element that belongs to at least half of the sets. Meanwhile, there are many related versions of the conjecture due to Frankl. For example, graph theorists may prefer the equivalent statement that every bipartite graph has a vertex that belongs to no more than half of the maximal independent sets. While even proving the ε-Union-Closed Sets Conjecture was out of reach, Poonen and Cui & Hu conjectured already stronger forms. At the end of last year, progress was made on many of these conjectures. Gilmer proved the ε-Union-Closed Sets Conjecture using an elegant entropy-based method which was sharpened by many others. Despite a sharp approximate form of the union-closed conjecture as stated by Chase and Lovett, a further improvement was possible. In a different direction, Kabela, Polak and Teska constructed union-closed family sets with large sets and few abundant elements. This talk will keep the audience up-to-date and give them insight in the main ideas. People who would like more details, can join the Ecopro-reading session on the 7th of March (10 o'clock, B332) as well. Here we go deeper in the core of the proofs and discuss possible directions for the full resolution.

Given an undirected planar graph $G$ with $n$ vertices and a set $T$ of $k$ pairs $(s_i,t_i)_{i=1}^k$ of vertices, the goal of the planar disjoint paths problem is to find a set $\mathcal P$ of $k$ pairwise vertex-disjoint paths connecting $s_i$ and $t_i$ for all indices $i\in\{1,\ldots,k\}$. This problem has been studied extensively due to its numerous applications such as VLSI layout and circuit routing. However, this problem is NP-complete even for grid graphs. This motivates the study of this problem from the viewpoint of parameterized algorithms. In this talk, I will present a $2^{O(k^2)}n$-time algorithm for the planar disjoint paths problem. This improves the two previously best-known algorithms: $2^{2^{O(k)}}n$-time algorithm [Discrete Applied Mathematics 1995] and $2^{O(k^2)}n^6$-time algorithm [STOC 2020]. This is joint work with Kyungjin Cho and Seunghyeok Oh.