KOMBINATORIKA SZEMINÁRIUM
2026/2027
ARCHÍVUM JELENLEGI TANÉV
2026. november 27. (10:15)
Riesz terem
Bérczi Kristóf
ELTE, MTA-ELTE Momentum Matroid Optimization Research Group

Fixed-Parameter Tractability and Hardness for Steiner Rooted and Locally Connected Orientations

Finding a Steiner strongly $k$-arc-connected orientation is particularly relevant in network design and reliability, as it guarantees robust communication between a designated set of critical nodes. We consider a rooted variant, called the Steiner Rooted Orientation problem, where one is given an undirected graph on $n$ vertices, a root vertex, and a set of $t$ terminals. The goal is to find an orientation of the graph such that the resulting directed graph is Steiner rooted $k$-arc-connected. This problem generalizes several classical connectivity results in graph theory, such as those on edge-disjoint paths and spanning-tree packings. While the maximum $k$ for which a Steiner strongly $k$-arc-connected orientation exists can be determined in polynomial time via Nash-Williams' orientation theorem, its rooted counterpart is significantly harder: the problem is NP-hard when both $k$ and $t$ are part of the input.

In this talk, we provide a complete understanding of the problem with respect to these two parameters, thereby resolving a long-standing open problem of Király and Lau (FOCS 2006). In particular, we give an algorithm that solves the problem in time $f(k,t)\cdot n^{O(1)}$, establishing fixed-parameter tractability with respect to the number of terminals $t$ and the target connectivity $k$. We further show that the problem remains NP-hard if either $k$ or $t$ is treated as part of the input, meaning that our algorithm is essentially optimal from a parameterized perspective. By a simple reduction, our results extend beyond the Steiner setting: the same framework applies to the more general orientation problem with local connectivity requirements, establishing fixed-parameter tractability when parameterized by the total demand. Joint work with Florian Hörsch, András Imolay, and Tamás Schwarcz.

2026. december 4. (10:30)
Riesz terem
Damásdi Gábor
Rényi Intézet

Rajzolás gyök páratlan hosszúságú élekkel és a négyszín-tétel

A doktori disszertációmban szerepel a következő, azóta sem publikált eredmény. Minden síkgráf lerajzolható a síkban úgy, hogy az éleit szakaszok reprezentálják, és minden ilyen szakasz hossza egy páratlan egész szám négyzetgyöke. Meglepő módon a bizonyítás felhasználja a négyszín-tételt. Kíváncsiságból megkértem a mesterséges intelligenciát, hogy adjon egy olyan bizonyítást, amely nem használja a négyszín-tételt. Még nagyobb meglepetésemre megmutatta, hogy a két állítás ekvivalens. Vagyis ha be tudnánk bizonyítani, hogy minden síkgráfnak létezik ilyen lerajzolása, akkor ebből következne a négyszín-tétel. Az előadásban ezeknek az eredményeknek a bizonyításait mutatom be. Sajnos a bizonyításból az derül ki, hogy a valódi kapcsolat mégsem igazán a négyszíntétellel van. Ehelyett a négyszínezhetőség egy algebrai átfogalmazását kapjuk a gráfok egy olyan tág osztályára, amely történetesen tartalmazza a síkgráfokat is.

2026. ??? (10:15)
Riesz terem
Nagy Gábor Péter
Bolyai Intézet

Carlet's cyclic-additive conjecture for the Kasami monomials

TBD