기초과학연구원 이산수학그룹
A backedge graph of a tournament $T$ with respect to a total ordering $\prec$ of the vertices of $T$ is a graph on $V(T)$ where $uv$ is an edge if and only if $uv \in A(T)$ and $v \prec u$. In 2023, Aboulker, Aubian, Charbit and Lopes introduced the clique number of tournaments based on …
We overview the recent resolution of a 1985 open problem of Gyárfás, that chromatic number is polynomially bounded by clique number for graphs with no induced five-vertex path. The proof introduces a chromatic density framework involving chromatic quasirandomness and chromatic density increment, which allows us to deduce the desired statement from the Erdős–Hajnal result for …
Strong flip-flatness appears to be the analogue of uniform almost-wideness in the setting of dense classes of graphs. Almost-wideness is a notion that was central in different characterisations of nowhere dense classes of graphs, and in particular the game-theoretic one. In this talk I will present the flip-flatness notions and conjectures about the characterization of …
Separating hash families are useful combinatorial structures that generalize several well-studied objects in cryptography and coding theory. Let $p_t(N, q)$ denote the maximum size of the universe for a $t$-perfect hash family of length $N$ over an alphabet of size $q$. We show that $q^{2 - o(1)} < p_t(t, q) = o(q^2)$ for all $t …
In this talk we discuss recent work to that establishes that the bounds of the Vital Linkage Function is single-exponential. This has immediate impacts on the complexity of the k-Disjoint Paths Problem, Minor Checking, and more generally, the Folio-Problem. We in fact prove something even stronger: It turns out that it is not in fact …
We give an induced counterpart of the Forest Minor theorem: for any t ≥ 2, the $K_{t,t}$-subgraph-free H-induced-minor-free graphs have bounded pathwidth if and only if H belongs to a class F of forests, which we describe as the induced minors of two (very similar) infinite parameterized families. This constitutes a significant step toward classifying …
We consider an arc-capacitated directed graph $D=(V,A)$, where each node $v$ is associated with a rational balance value $b(v)$. Nodes with negative balance values are referred to as sources, while those with positive balance values are called sinks. A feasible $b$-transshipment is a flow $f : A \to \mathbb{R}_{\ge 0}$ that routes the total supply …