Discrete Mathematics Group

Ahmed Ghazy and Tim Hartmann, Continuous Graphs – An Overview and a Coloring Problem
2025-11-04 16:30 - 17:30 (Asia/Seoul) | Room B332, IBS (기초과학연구원)
We consider a continuous model of graphs, introduced by Dearing and Francis in 1974, where each edge of G to be a unit interval, giving rise to an infinite metric space that contains not only the vertices of G but all points on all edges of G. Several standard graph problems can be defined and studied on continuous graphs, yielding many surprising algorithmic results and combinatorial connections.
The motivation can be exemplified by the well-known Independent Set problem on graphs. Given a graph G, we want to place k facilities that are pairwise at least a distance 2 edge lengths apart. In some applications, such as when the underlying graph represents a street network, it is reasonable to allow placing a facility not only at a crossroad but also somewhere within a street, that is, not only at a vertex but also at any point on an edge between two vertices. This motivates the study of the Independent Set problem on continuous graphs. In such a setting, for example, the problem corresponds to requiring pairwise distance r=2 for the placed facilities. However, we may also study the problem where we fix r to any positive integer, rational, or even irrational number. Other problems studied in the continuous model include Dominating Set, TSP, and Coloring.
In the first part of this talk, we will give a general overview of research on continuous graphs and computational problems in this setting.
In the second part, we explore, as part of recent work, a coloring problem on continuous graphs akin to the well-known Hadwiger-Nelson Problem.
Based on joint work with Fabian Frei, Florian Hörsch, Tom Janßen, Stefan Lendl, Dániel Marx, Prahlad Narasimhan, and Gerhard Woeginger.

Simón Piga, Turán problem in hypergraphs with quasirandom links
2025-11-11 16:30 - 17:30
Given a $k$-uniform hypergraph $F$, its Turán density $pi(F)$ is the infimum over all $din [0,1]$ such that any $n$-vertex $k$-uniform hypergraph $H$ with at least $dbinom{n}{k}+o(n^k)$ edges contains a copy of $F$. While Turán densities are generally well understood for graphs ($k=2$), the problem becomes notoriously difficult for $kgeq 3$, even for small hypergraphs.
We study two well-known variants of this Turán problem for hypergraphs: first, under minimum codegree conditions and, second, with a quasirandom edge distribution. Each variant defines a distinct extremal parameter, generalising the classical Turán density. Here we present recent results in both settings, with a particular emphasis on the case of hypergraphs where every link is itself quasirandom. Our results include exact solutions for key hypergraphs and general results about the behaviour of the Turán density functions.

Fedor Noskov, Polynomial dependencies in hypergraph Turan-type problems
2025-11-18 16:30 - 17:30
Consider a general Turan-type problem on hypergraphs. Let $mathcal{F}$ be a family of $k$-subsets of $[n]$ that does not contain sets $F_1, ldots, F_s$ satisfying some property $P$. We show that if $P$ is low-dimensional in some sense (e.g., is defined by intersections of bounded size) then, under polynomial dependencies between $n, k$ and the parameters of $P$, one can reduce the problem of maximizing the size of the family $|mathcal{F}|$ to a finite extremal set theory problem independent of $n$ and $k$. We show that our technique implies new bounds in a number of Turan-type problems including the Erdős-Sós forbidden intersection problem, the Duke-Erdős forbidden sunflower problem, forbidden $(t, d)$-simplex problem and the forbidden hypergraph problem. Furthermore, we also briefly discuss the connection between the aforementioned reduction and the measure boosting argument based on the action of a certain semigroup on the Boolean cube. This connection turns out to be fruitful when extending extremal set theory problems to domains different from $binom{[n]}{k}$.
Joint work with Liza Iarovikova, Andrey Kupavskii, Georgy Sokolov and Nikolai Terekhov

Péter Pál Pach, Product representation of perfect cubes
2025-11-25 16:30 - 17:30
Let $F_{k,d}(n)$ be the maximal size of a set ${A}subseteq [n]$ such that the equation has no solution with $a_1,a_2,ldots,a_kin A$ and integer $x$. Erdős, Sárközy and T. Sós studied $F_{k,2}$, and gave bounds when $k=2,3,4,6$ and also in the general case. We study the problem for $d=3$, and provide bounds for $k=2,3,4,6$ and $9$, furthermore, in the general case, as well. In particular, we refute an 18-year-old conjecture of Verstraëte.
We also introduce another function $f_{k,d}$ closely related to $F_{k,d}$: While the original problem requires $a_1, ldots , a_k$ to all be distinct, we can relax this and only require that the multiset of the $a_i$’s cannot be partitioned into $d$-tuples where each $d$-tuple consists of $d$ copies of the same number.
Joint work with Fleiner, Juhász, Kövér and Sándor.

Matthew Kwan, Exponential anticoncentration of the permanent
2025-12-08 16:30 - 17:30
Let A be a random n×n matrix with independent entries, and suppose that the entries are “uniformly anticoncentrated” (for example, A could be a uniformly random n×n matrix with ±1 entries). We prove that the permanent of A is exponentially anticoncentrated, significantly improving previous bounds of Tao and Vu. Our proof also works for the determinant, giving an alternative proof of a classical theorem of Kahn, Komlós and Szemerédi. Joint work with Zach Hunter and Lisa Sauermann.

Tuukka Korhonen, Dynamic Treewidth in Logarithmic Time
2025-12-09 16:30 - 17:30
We present a dynamic data structure that maintains a tree decomposition of width at most 9k+8 of a dynamic graph with treewidth at most k, which is updated by edge insertions and deletions. The amortized update time of our data structure is $2^{O(k)} log n$, where n is the number of vertices. The data structure also supports maintaining any “dynamic programming scheme” on the tree decomposition, providing, for example, a dynamic version of Courcelle’s theorem with $O_k(log n)$ amortized update time; the $O_k(⋅)$ notation hides factors that depend on k. This improves upon a result of Korhonen, Majewski, Nadara, Pilipczuk, and Sokołowski [FOCS 2023], who gave a similar data structure but with amortized update time $2^{k^{O(1)}} n^{o(1)}$. Furthermore, our data structure is arguably simpler. Our main novel idea is to maintain a tree decomposition that is “downwards well-linked”, which allows us to implement local rotations and analysis similar to those for splay trees.
This talk is based on arXiv:2504.02790.

Chi Hoi Yip, Cliques in Paley graphs and cyclotomic graphs
2025-12-16 16:30 - 17:30
Given a prime power $q equiv 1 pmod 4$, the Paley graph of order $q$ is the graph defined over $mathbb{F}_q$ (the finite field with $q$ elements), such that two vertices are adjacent if and only if their difference is a square in $mathbb{F}_q$. In this talk, I will present some recent progress on the clique number of Paley graphs of non-square order, the characterization of maximum cliques in Paley graphs of square order, as well as their extensions to cyclotomic graphs. In particular, I will highlight a new proof of the Van Lint–MacWilliams’ conjecture using ideas from arithmetic combinatorics.

Donggyu Kim (김동규), Grassmann-Plücker functions for orthogonal matroids
2025-12-26 16:30 - 17:30
We present a new cryptomorphic definition of orthogonal matroids with coefficients using Grassmann-Plücker functions. The equivalence is motivated by Cayley’s identities expressing principal and almost-principal minors of a skew-symmetric matrix in terms of its pfaffians. As a corollary of the new cryptomorphism, we deduce that each component of the orthogonal Grassmannian is parameterized by certain part of the Plücker coordinates.
This is joint work with Changxin Ding.

Yunbum Kook (국윤범), Sampling and volume computation
2025-12-30 16:30 - 17:30
Since the development of the first randomized polynomial-time algorithm for volume computation by Dyer, Frieze, and Kannan in 1989, convex-body sampling has been a central problem at the intersection of algorithms, geometry, and probability. A major milestone came in 1997, when Kannan, Lovász, and Simonovits analyzed the Ball Walk and formulated the influential KLS conjecture. This was extended to log-concave distributions by Lovász and Vempala in 2006, and further accelerated by Cousins and Vempala in 2015 through warm-start generation techniques.
In this talk, I will present a gentle introduction to these milestones and how they have been streamlined and improved in the past few years. The talk is based on joint work with Santosh Vempala.

Daniel Mock, A Simple for the Dominating Set Problem and More
2026-01-06 16:30 - 17:30
In [1], Fabianski et. al. developed a simple, yet surprisingly powerful algorithmic framework to develop efficient parameterized graph algorithms. Notably they derive a simple parameterized algorithm for the dominating set problem on a variety of graph classes, including powers of nowhere dense classes and biclique-free classes. These results encompass a wide range of previously known results and often improve the best known running times. Similar results follow for the distance-r variation of dominating set and for independent set. The running time of the algorithm is closely tied to model-theoretic properties, i.e. stability and the Helly property.
We build upon these results and develop a similar algorithm which only relies on the strong Helly property and does not need stability. For the dominating set problem, we get a parameterized algorithm that works (additionally to biclique-free classes and powers of nowhere dense classes) weakly gamma-closed classes while being simpler and faster than previously known results.
In this talk, we introduce the basic framework, results by Fabianski et. al and connections to other areas. We discuss our new insights and possible research directions.
[1] Grzegorz Fabianski, Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk: Progressive Algorithms for Domination and Independence. STACS 2019

Ferdinand Ihringer, Boolean Functions Analysis in the Grassmann Graph
2026-01-13 16:30 - 17:30
Boolean function analysis for the hypercube ${ 0, 1 }^n$ is a well-developed field and has many famous results such as the FKN Theorem or Nisan-Szegedy Theorem. One easy example is the classification of Boolean degree $1$ functions: If $f$ is a real, $n$-variate affine function which is Boolean on the $n$-dimensional hypercube (that is, $f(x) in { 0, 1 }$ for $x in { 0, 1 }^n$), then $f(x) = 0$, $f(x) = 1$, $f(x) = x_i$ or $f(x) = 1 – x_i$. The same classification (essentially) holds if we restrict ${ 0, 1}^n$ to elements with Hamming weight $k$ if $n-k, k geq 2$. If we replace $k$-sets of ${ 1, ldots, n }$ by $k$-spaces in $V(n, q)$, the $n$-dimensional vector space over the field with $q$ elements, then suddenly even the simple question of classifying Boolean degree $1$ functions, here traditionally known as Cameron-Liebler classes, becomes seemingly hard to solve.
We will discuss some results on low-degree Boolean functions in the vector space setting. Most notably, we will discuss how vector space Ramsey numbers, so extremal combinatorics, can be utilized in this finite geometrical setting.

Tomáš Masařík, Separator Theorem for Minor-free Graphs in Linear Time
2026-01-20 16:30 - 17:30
The planar separator theorem by Lipton and Tarjan [FOCS ’77, SIAM Journal on Applied Mathematics ’79] states that any planar graph with $n$ vertices has a balanced separator of size $O(sqrt{n})$ that can be found in linear time. This landmark result kicked off decades of research on designing linear or nearly linear-time algorithms on planar graphs. In an attempt to generalize Lipton-Tarjan’s theorem to nonplanar graphs, Alon, Seymour, and Thomas [STOC ’90, Journal of the AMS ’90] showed that any minor-free graph admits a balanced separator of size $O(sqrt{n})$ that can be found in $O(n^{3/2})$ time. The superlinear running time in their separator theorem is a key bottleneck for generalizing algorithmic results from planar to minor-free graphs. Despite extensive research for more than two decades, finding a balanced separator of size $O(sqrt{n})$ in (linear) $O(n)$ time for minor-free graphs remains a major open problem. Known algorithms either give a separator of size much larger than $O(sqrt{n})$ or have superlinear running time, or both.
In this paper, we answer the open problem affirmatively. Our algorithm is very simple: it runs a vertex-weighted variant of breadth-first search (BFS) a constant number of times on the input graph. Our key technical contribution is a weighting scheme on the vertices to guide the search for a balanced separator, offering a new connection between the size of a balanced separator and the existence of a clique-minor model. We believe that our weighting scheme may be of independent interest.
This is a joint work with Édouard Bonnet, Tuukka Korhonen, Hung Le, and Jason Li.

Daniel Dadush, TBA
2026-01-27 16:30 - 17:30

Seonghun Park (박성훈), TBA
2026-02-10 16:30 - 17:30

Marek Sokołowski, TBA
2026-02-24 16:30 - 17:30

Chính T. Hoàng, TBA
2026-03-03 16:30 - 17:30

Dario Cavallaro, TBA
2026-03-10 16:30 - 17:30

Hidde Koerts, TBA
2026-03-24 16:30 - 17:30

Tung H. Nguyen, TBA
2026-03-31 16:30 - 17:30

Xavier Goaoc, TBA
2026-05-19 16:30 - 17:30

Maria Chudnovsky, TBA
2026-05-26 16:30 - 17:30
