기초과학연구원 이산수학그룹
Directed graphs prove to be very hard to tame in contrast to undirected graphs. In particular, they are not well-quasi-ordered by any known relevant inclusion relation, and are lacking fruitful structure theorems. This motivates the search for structurally rich subclasses of directed graphs that are well behaved. Eulerian directed graphs are a particularly prominent example, …
Two related papers will be discussed: 1. In 1966, Erdős, Goodman, and Pósa showed that if $G$ is an $n$-vertex graph, then at most $\lfloor n^2/4 \rfloor$ cliques of $G$ are needed to cover the edges of $G$, and the bound is best possible as witnessed by the balanced complete bipartite graph. This was generalized …
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 …
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 …
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 …