Here is a list of upcoming online seminars in combinatorics, automatically generated from researchseminars.org and a few other calendars available in the iCal format. Please let me know if you find any interesting iCal feed / Google Calendar of the seminars.
You can also find a list of upcoming workshops, conferences, and schools.
Timezone: Korea (KST), UTC/GMT+9.
December 2023
December 12
 4:30 pm – 5:30 pm

TingWei Chao (Carnegie Mellon University)
Title: Tight Bound on Joints Problem and Partial Shadow Problem
by TingWei Chao (Carnegie Mellon University) as part of IBS/KAIST Discrete Math SeminarViewonly livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B332, IBS.
Abstract: TBA
December 19
 4:30 pm – 5:30 pm

Shengtong Zhang (Stanford University)
by Shengtong Zhang (Stanford University) as part of IBS/KAIST Discrete Math Seminar
Viewonly livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B332, IBS.
Abstract: TBA
January 2024
January 2
 4:30 pm – 5:30 pm

Shira Zerbib (Iowa State University)
by Shira Zerbib (Iowa State University) as part of IBS/KAIST Discrete Math Seminar
Viewonly livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B332, IBS.
Abstract: TBA
January 11
 4:30 pm – 5:30 pm

Jinyoung Park (NYU)
Title: Dedekind’s Problem and beyond
by Jinyoung Park (NYU) as part of IBS/KAIST Discrete Math SeminarViewonly livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B332, IBS.
Abstract: TBA  6:00 pm – 7:00 pm

Raul Wayne Teixeira Lopes, «New Mengerlike dualities in digraphs and applications to halfintegral linkages»
We present new minmax 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 halfintegral 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 adhoc 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 minmax 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 halfintegral 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 halfintegrally feasible under the presence of a large bramble of congestion two (or equivalently, if the directed treewidth 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
January 16
 4:30 pm – 5:30 pm

Ander Lamaison (IBS Extremal Combinatorics and Probability Group)
by Ander Lamaison (IBS Extremal Combinatorics and Probability Group) as part of IBS/KAIST Discrete Math Seminar
Viewonly livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B332, IBS.
Abstract: TBA
January 18
 6:00 pm – 7:00 pm

Júlio Araújo, «Semiproper orientations of dense graphs»
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 indegree of each vertex in $D$ is at most $k$. An orientation $D$ of $G$ is //proper// if any two adjacent vertices have different indegrees 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 arcweighting $A(D) \to \mathbb{N}\setminus\{0\}$. A //semiproper 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 //semiproper $k$orientation// $(D,w)$ of a graph $G$ is a semiproper orientation of $G$ such that $\max_{v\in V(G)} S_{(D,w)}(v) ≤ k$. The //semiproper orientation number// of a graph $G$, denoted by $spo(G)$, is the least $k$ such that $G$ has a semiproper $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) = 2k2$. 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 cobipartite 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.
January 23
 4:30 pm – 5:30 pm

Zichao Dong (IBS Extremal Combinatorics and Probability Group)
Title: Convex polytopes in nonelongated point sets in $\mathbb{R}^d$
by Zichao Dong (IBS Extremal Combinatorics and Probability Group) as part of IBS/KAIST Discrete Math SeminarViewonly livestream: https://www.youtube.com/c/ibsdimag
Lecture held in Room B332, IBS.
Abstract: TBA
February 2024
February 1
 6:00 pm

Maximilian Gorsky, «Packing even directed circuits quarterintegrally»
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ősPó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ősPó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 Kenichi Kawarabayashi, Stephan Kreutzer, and
Sebastian Wiederrecht