List of upcoming online seminars in discrete mathematics, combinatorics, and graph theory

Title: Tight Bound on Joints Problem and Partial Shadow Problem
by Ting-Wei Chao (Carnegie Mellon University) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B332, IBS.
Abstract: TBA

by Shengtong Zhang (Stanford University) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B332, IBS.
Abstract: TBA

by Shira Zerbib (Iowa State University) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B332, IBS.
Abstract: TBA

Title: Dedekind’s Problem and beyond
by Jinyoung Park (NYU) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B332, IBS.
Abstract: TBA

We present new min-max relations in digraphs between the number of paths satisfying certain conditions and the order of the corresponding cuts. We define these objects in order to capture, in the context of solving the half-integral linkage problem, the essential properties needed for reaching a large bramble of congestion two (or any other constant) from the terminal set. This strategy has been used ad-hoc in several articles, usually with lengthy technical proofs, and our objective is to abstract it to make it applicable in a simpler and unified way. We provide two proofs of the min-max relations, one consisting in applying Menger’s Theorem on appropriately defined auxiliary digraphs, and an alternative simpler one using matroids, however with worse polynomial running time.

As an application, we manage to simplify and improve several results of Edwards et al. [ESA 2017] and of Giannopoulou et al. [SODA 2022] about finding half-integral linkages in digraphs. Concerning the former, besides being simpler, our proof provides an almost optimal bound on the strong connectivity of a digraph for it to be half-integrally feasible under the presence of a large bramble of congestion two (or equivalently, if the directed tree-width is large, which is the hard case). Concerning the latter, our proof uses brambles as rerouting objects instead of cylindrical grids, hence yielding much better bounds and being somehow independent of a particular topology

by Ander Lamaison (IBS Extremal Combinatorics and Probability Group) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B332, IBS.
Abstract: TBA

An //orientation// $D$ of a graph $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of the two possible arcs with the same ends. An orientation $D$ of a graph $G$ is a //$k$-orientation// if the in-degree of each vertex in $D$ is at most $k$. An orientation $D$ of $G$ is //proper// if any two adjacent vertices have different in-degrees in $D$. The //proper orientation number// of a graph $G$, denoted by $po(G)$, is the minimum $k$ such that $G$ has a proper $k$-orientation.

A //weighted orientation// of a graph $G$ is a pair $(D,w)$, where $D$ is an orientation of $G$ and $w$ is an arc-weighting $A(D) \to \mathbb{N}\setminus\{0\}$. A //semi-proper orientation// of $G$ is a weighted orientation $(D,w)$ of $G$ such that for every two adjacent vertices $u$ and $v$ in $G$, we have that $S_{(D,w)}(v)
eq S_{(D,w)}(u) $, where
$S_{(D,w)}(v)$ is the sum of the weights of the arcs in $(D,w)$ with head $v$. For a positive integer $k$, a //semi-proper $k$-orientation// $(D,w)$ of a graph $G$ is a semi-proper orientation of $G$ such that $\max_{v\in V(G)} S_{(D,w)}(v) ≤ k$. The //semi-proper orientation number// of a graph $G$, denoted by $spo(G)$, is the least $k$ such that $G$ has a semi-proper $k$-orientation.

In this work, we first prove that $spo(G) \in \{ω(G)-1,ω(G)\}$ for every split graph $G$, and that, given a split graph $G$, deciding whether $spo(G) = ω(G)-1$ is an $NP$-complete problem. We also show that, for every $k$, there exists a (chordal) graph $G$ and a split subgraph $H$ of $G$ such that $po(G) ≤ k$ and $po(H) = 2k-2$. In the sequel, we show that, for every $n≥ p(p+1)$, $spo(P^{p}_n) = \left\lceil \frac{3}{2}p \right\rceil$, where $P^{p}_n$ is the $p^{th}$ power of the path on $n$ vertices. We investigate further unit interval graphs with no big clique: we show that $po(G) ≤ 3$ for any unit interval graph $G$ with $ω(G)=3$, and present a complete characterization of unit interval graphs with $po(G)=ω(G)=3$. Then, we show that deciding whether $spo(G)=ω(G)$ can be solved in polynomial time in the class of co-bipartite graphs. Finally, we prove that computing $spo(G)$ is FPT when parameterized by the minimum size of a vertex cover in $G$ or by the treewidth of $G$. We also prove that not only computing $spo(G)$, but also $po(G)$, admits a polynomial kernel when parameterized by the neighbourhood diversity plus the value of the solution. These results imply kernels of size $4^{{\cal O}(k^2)}$ and ${\cal O}(2^kk^2)$, in chordal graphs and split graphs, respectively, for the problem of deciding whether $spo(G)≤ k$ parameterized by $k$. We also present exponential kernels for computing both $po(G)$ and $spo(G)$ parameterized by the value of the solution when $G$ is a cograph. On the other hand, we show that computing $spo(G)$ does not admit a polynomial kernel parameterized by the value of the solution when $G$ is a chordal graph, unless NP $\subseteq$ coNP/poly.

Joint work with F. Havet, C. Linhares Sales, N. Nisse and K. Suchan.

Title: Convex polytopes in non-elongated point sets in $\mathbb{R}^d$
by Zichao Dong (IBS Extremal Combinatorics and Probability Group) as part of IBS/KAIST Discrete Math Seminar

View-only livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B332, IBS.
Abstract: TBA

We prove the existence of a computable function f : N → N such that for every integer k and every digraph D either contains a collection C of directed cycles of even length such that no vertex of D belongs to more than four cycles in C, or there exists a set S ⊆ V (D) of size at most f(k) such that D − S has no directed cycle of even length. Moreover, we provide an algorithm that finds one of the two outcomes of this statement in time $g(k)\cdot n^{O(1)}$ for some computable function g : N → N.
Our result unites two deep fields of research from the algorithmic theory for digraphs: The study of the Erdős-Pósa property of digraphs and the study of the Even Dicycle Problem. The latter is the decision problem which asks if a given digraph contains an even dicycle and can be traced back to a question of Pólya from 1913. It remained open until a polynomial time algorithm was finally found by Robertson, Seymour, and Thomas (Ann. of Math. (2) 1999) and, independently, McCuaig (Electron. J. Combin. 2004; announced jointly at STOC 1997). The Even Dicycle Problem is equivalent to the recognition problem of Pfaffian bipartite graphs and has applications even beyond discrete mathematics and theoretical computer science. On the other hand, Younger’s Conjecture (1973), states that dicycles have the Erdős-Pósa property. The conjecture was proven more than two decades later by Reed, Robertson, Seymour, and Thomas (Combinatorica 1996) and opened the path for structural digraph theory as well as the algorithmic study of the directed feedback vertex set problem. Our approach builds upon the techniques used to resolve both problems and combines them into a powerful structural theorem that yields further algorithmic applications for other prominent problems.

Joint work with Ken-ichi Kawarabayashi, Stephan Kreutzer, and
Sebastian Wiederrecht