Minki Kim (김민기), Rainbow paths and rainbow matchings
Room B232 IBS (기초과학연구원)We prove that if $n \geq 3$, then any family of $3n-3$ sets of matchings of size $n$ in any graph has a rainbow matching of size $n$. This improves …
Loading view.
Kevin Hendrey, A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
Room B232 IBS (기초과학연구원)Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all …
Debsoumya Chakraborti, Some classical problems in graph saturation
Room B232 IBS (기초과학연구원)Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph $G$ is called $F$-saturated if $G$ does not contain a subgraph isomorphic to $F$, but …
Se-Young Yun (윤세영), Regret in Online Recommendation Systems
Room B232 IBS (기초과학연구원)We propose a theoretical analysis of recommendation systems in an online setting, where items are sequentially recommended to users over time. In each round, a user, randomly picked from a …
Yixin Cao (操宜新), Recognizing (unit) interval graphs by zigzag graph searches
Room B232 IBS (기초과학연구원)Corneil, Olariu, and Stewart presented a recognition algorithm for interval graphs by six graph searches. Li and Wu simplified it to only four. The great simplicity of the latter algorithm …
Hong Liu (刘鸿), Nested cycles with no geometric crossing
Room B232 IBS (기초과학연구원)In 1975, Erdős asked the following question: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$, …
Édouard Bonnet, Twin-width and ordered binary structures
Zoom ID: 869 4632 6610 (ibsdimag)The twin-width of a graph G can be defined as the least integer d such that there is a sequence of length |V(G)| of (strictly) coarser and coarser partitions of …
Casey Tompkins, 3-uniform hypergraphs avoiding a cycle of length four
Room B232 IBS (기초과학연구원)We show that that the maximum number of of edges in a $3$-uniform hypergraph without a Berge-cycle of length four is at most $(1+o(1)) \frac{n^{3/2}}{\sqrt{10}}$. This improves earlier estimates by …
Sophie Spirkl, Pure pairs in ordered graphs
Zoom ID: 869 4632 6610 (ibsdimag)A pure pair in a graph G is a pair of subsets A, B of the vertex set of G such that in G, either all of the edges or …
Rutger Campbell, Matroid orientability and representability
Room B232 IBS (기초과학연구원)In this talk we will have a brief introduction to oriented matroids and their relation to real-representability.