Hong Liu (刘鸿), Cycles and trees in graphs (8/8)
Zoom ID:8628398170 (123450)This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
Loading view.
Joonkyung Lee (이준경), On graph norms for complex-valued functions
Room B232 IBS (기초과학연구원)For any given graph $H$, one may define a natural corresponding functional $\|.\|_H$ for real-valued functions by using homomorphism density. One may also extend this to complex-valued functions, once $H$ is paired with a $2$-edge-colouring $\alpha$ to assign conjugates. We say that $H$ is real-norming (resp. complex-norming) if $\|.\|_H$ (resp. there is $\alpha$ such that …
Chun-Hung Liu (劉俊宏), Asymptotic dimension of minor-closed families and beyond
Zoom ID:95464969835 (356260)The asymptotic dimension of metric spaces is an important notion in geometric group theory. The metric spaces considered in this talk are the ones whose underlying spaces are the vertex-sets of (edge-)weighted graphs and whose metrics are the distance functions in weighted graphs. A standard compactness argument shows that it suffices to consider the asymptotic …
Jeong Ok Choi (최정옥), Various game-theoretic models on graphs
Room B232 IBS (기초과학연구원)We introduce some of well-known game-theoretic graph models and related problems. A contagion game model explains how an innovation diffuses over a given network structure and focuses on finding conditions on which structure an innovation becomes epidemic. Regular infinite graphs are interesting examples to explore. We show that regular infinite trees make an innovation least …
Jaeseong Oh (오재성), A 2-isomorphism theorem for delta-matroids
Room B232 IBS (기초과학연구원)Whitney’s 2-Isomorphism Theorem characterises when two graphs have isomorphic cycle matroids. In this talk, we present an analogue of this theorem for graphs embedded in surfaces by characterising when two graphs in surface have isomorphic delta-matroids. This is based on the joint work with Iain Moffatt.
Daniel Cranston, Vertex Partitions into an Independent Set and a Forest with Each Component Small
Zoom ID: 869 4632 6610 (ibsdimag)For each integer $k\ge 2$, we determine a sharp bound on $\operatorname{mad}(G)$ such that $V(G)$ can be partitioned into sets $I$ and $F_k$, where $I$ is an independent set and $G$ is a forest in which each component has at most k vertices. For each $k$ we construct an infinite family of examples showing our result is best …
Casey Tompkins, Extremal forbidden poset problems in Boolean and linear lattices
Room B232 IBS (기초과학연구원)Extending the classical theorem of Sperner on the maximum size of an antichain in the Boolean lattice, Katona and Tarján introduced a general extremal function $La(n,P)$, defined to be the maximum size of a family of subsets of $$ which does not contain a given poset $P$ among its containment relations. In this talk, I …
Meike Hatzel, Constant congestion bramble
Zoom ID: 869 4632 6610 (ibsdimag)In this talk I will present a small result we achieved during a workshop in February this year. My coauthors on this are Marcin Pilipczuk, Paweł Komosa and Manuel Sorge. A bramble in an undirected graph $G$ is a family of connected subgraphs of $G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either $V(H_1) \cap …
Yijia Chen (陈翌佳), Graphs of bounded shrub-depth, through a logic lens
Zoom ID: 869 4632 6610 (ibsdimag)Shrub-depth is a graph invariant often considered as an extension of tree-depth to dense graphs. In this talk I will explain our recent proofs of two results about graphs of bounded shrub-depth. Every graph property definable in monadic-second order logic, e.g., 3-colorability, can be evaluated by Boolean circuits of constant depth and polynomial size, whose …
Duksang Lee (이덕상), Characterizing matroids whose bases form graphic delta-matroids
Room B232 IBS (기초과학연구원)We introduce delta-graphic matroids, which are matroids whose bases form graphic delta-matroids. The class of delta-graphic matroids contains graphic matroids as well as cographic matroids and is a proper subclass of the class of regular matroids. We give a structural characterization of the class of delta-graphic matroids. We also show that every forbidden minor for …