Discrete Mathematics Group

Jie Ma (马杰), Non-repeated cycle lengths and Sidon sequences
2021-02-10 16:30 - 17:30 (Asia/Seoul) | Zoom ID: 869 4632 6610 (ibsdimag)
We prove a conjecture of Boros, Caro, Furedi and Yuster on the maximum number of edges in a 2-connected graph without repeated cycle lengths, which is a restricted version of a longstanding problem of Erdos. Our proof together with the matched lower bound construction of Boros, Caro, Furedi and Yuster show that this problem can be conceptually reduced to the seminal problem of finding the maximum Sidon sequences in number theory. Joint work with Tianchi Yang.

Doowon Koh (고두원), On the cone restriction conjecture in four dimensions and applications in incidence geometry
2021-02-09 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Main purpose of this talk is to introduce a connection between restriction estimates for cones and point-sphere incidence theorems in the finite field setting. First, we review the finite field restriction problem for cones and address new results on the conical restriction problems. In particular, we establish the restriction conjecture for the cone in four dimensions. Second, we study how to apply the conical restriction results to the point-sphere incidence bounds. As a consequence, we obtain sharp point-sphere incidence bounds when sphere sets are not too big.

Ron Aharoni, Colorful KKM and multiple cakes division
2021-02-03 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
In the “cake partition” problem n players have each a list of preferred parts for any partition of the [0,1] interval (“cake”) into n sub-intervals. Woodall, Stromquist and Gale proved independently that under mild conditions on the list of preferences (like continuity) there is always a partition and assignment of parts to the players, in which every player gets a piece belonging to her list of preferred parts. In fact, Gale proved a colorful version of the famous KKM theorem, not realizing that this is the same problem, but on the other hand, proved the problem its proper setting. I will discuss the case of partitioning more than one cake – how many players can you make happy, when there is a general number of cakes, and general number of players.
Joint work with Eli Berger, Joseph Briggs, Erel Segal-Halevi and Shira Zerbib.

Dong Yeap Kang (강동엽), A proof of the Erdős-Faber-Lovász conjecture
2021-01-27 10:00 - 11:00 | Zoom ID: 869 4632 6610 (ibsdimag)
A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdős, Faber, and Lovász in 1972, states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$.
In this talk, I will present the ideas to prove the conjecture for all large $n$. This is joint work with Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.

Tuan Tran, Minimum saturated families of sets
2021-01-26 04:30 - 17:30 | Room B232, IBS (기초과학연구원)
A family $mathcal F$ of subsets of [n] is called s-saturated if it contains no s pairwise disjoint sets, and moreover, no set can be added to $mathcal F$ while preserving this property. More than 40 years ago, Erdős and Kleitman conjectured that an s-saturated family of subsets of [n] has size at least $(1 – 2^{-(s-1)})2^n$. It is a simple exercise to show that every s-saturated family has size at least $2^{n-1}$, but, as was mentioned by Frankl and Tokushige, even obtaining a slightly better bound of $(1/2 + varepsilon)2^n$, for some fixed $varepsilon > 0$, seems difficult. We prove such a result, showing that every s-saturated family of subsets of [n] has size at least $(1 – 1/s)2^n$. In this talk, I will present two short proofs. This is joint work with M. Bucic, S. Letzter and B. Sudakov.

Yusuke Kobayashi (小林 佑輔), An FPT Algorithm for Minimum Additive Spanner Problem
2021-01-20 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
For a positive integer t and a graph G, an additive t-spanner of G is a spanning subgraph in which the distance between every pair of vertices is at most the original distance plus t. Minimum Additive t-Spanner Problem is to find an additive t-spanner with the minimum number of edges in a given graph, which is known to be NP-hard. Since we need to care about global properties of graphs when we deal with additive t-spanners, Minimum Additive t-Spanner Problem is hard to handle, and hence only few results are known for it. In this talk, we study Minimum Additive t-Spanner Problem from the viewpoint of parameterized complexity. We formulate a parameterized version of the problem in which the number of removed edges is regarded as a parameter, and give a fixed-parameter algorithm for it. We also extend our result to (α,β)-spanners.

Ben Lund, Perfect matchings and derangements on graphs
2021-01-19 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
We show that each perfect matching in a bipartite graph G intersects at least half of the perfect matchings in G. This result has equivalent formulations in terms of the permanent of the adjacency matrix of a graph, and in terms of derangements and permutations on graphs. We give several related results and open questions. This is joint work with Matija Bucic, Pat Devlin, Mo Hendon, and Dru Horne.

Rose McCarty, Vertex-minors and flooding immersions
2021-01-13 10:00 - 11:00 | Zoom ID: 869 4632 6610 (ibsdimag)
An immersion of a graph H into a graph G sends edges of H into edge-disjoint trails of G. We say the immersion is flooding if every edge of G is in one of the trails. Flooding immersions are interesting for Eulerian group-labelled graphs; in this context they behave quite differently from regular immersions. Moreover, understanding such flooding immersions is a vital step towards understanding the structure of graphs with a forbidden vertex-minor.
I will focus on explaining the connection to vertex-minors, and on recent progress in this direction from ongoing joint work with Jim Geelen and Paul Wollan.

Andreas Holmsen, Discrete geometry in convexity spaces
2021-01-12 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
The notion of convexity spaces provides a purely combinatorial framework for certain problems in discrete geometry. In the last ten years, we have seen some progress on several open problems in the area, and in this talk, I will focus on the recent results relating to Tverberg’s theorem and the Alon-Kleitman (p,q) theorem.

O-joung Kwon (권오정), Directed tangles and applications
2021-01-05 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
The canonical tree-decomposition theorem, proved by Robertson and Seymour in their seminal graph minors series, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper, we prove the analogous result for digraphs, the directed tangle tree-decomposition theorem. More precisely, we introduce directed tangles and provide a directed tree-decomposition of digraphs $G$ that distinguishes all maximal directed tangles in $G$. Furthermore, for any integer $k$, we construct a directed tree-decomposition that distinguishes all directed tangles of order $k$, for any integer $k$.
By relaxing the bound slightly, we can make the previous result algorithmic: for fixed $k$, we design a polynomial-time algorithm that finds a directed tree-decomposition distinguishing all directed tangles of order $3k$ separated by some separation of order less than $k$.
We provide two direct applications of this tangle tree-decomposition theorem. First, we show that the family of directed odd cycles has the half-integral Erdős-Pósa property, that is, there is a function $f:mathbb{N}rightarrow mathbb{R}$ such that for every digraph $G$ and every integer $k$, either $G$ contains a family of $k$ directed odd cycles where every vertex of $G$ is contained at most two cycles, or a vertex subset of size at most $f(k)$ hitting all directed odd cycles. This extends the half-integral Erdős-Pósa property for undirected odd cycles, shown by Reed [Mangoes and blueberries. Combinatorica 1999].
Second, for every fixed $k$ we show that there is a polynomial-time algorithm which, on input $G$, and source and sink vertices $(s_1, t_1), dots, (s_k, t_k)$, either finds a family of paths $P_1, dots, P_k$ such that each $P_i$ links $s_i$ to $t_i$ and every vertex of $G$ is contained in at most two paths, or determines that there is no set of pairwise vertex-disjoint paths each connecting $s_i$ to $t_i$. This result improves previous results (with “two” replaced by “three”), and given known hardness results, our result is best possible in a sense that we cannot hope for fixed parameter tractability or fully vertex-disjoint directed paths.
This is joint work with Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, and Qiqin Xie.

Paul Seymour, The Erdős-Hajnal conjecture is true for excluding a five-cycle
2020-12-30 10:00 - 11:00 | Zoom ID: 869 4632 6610 (ibsdimag)
In an n-vertex graph, there must be a clique or stable set of size at least $Clog n$, and there are graphs where this bound is attained. But if we look at graphs not containing a fixed graph H as an induced subgraph, the largest clique or stable set is bigger.
Erdős and Hajnal conjectured in 1977 that for every graph H, there exists c>0 such that every H-free graph has a clique or stable set of size at least $|G|^c$ (“H-free” means not containing H as an induced subgraph, and |G| means the number of vertices of G). This is still open, even for some five-vertex graphs H; and the case that has attracted most attention is when H is a cycle of length five.
It is true in that case. We will give a sketch of the proof, which is via applying a lemma about bipartite graphs, a variant of a theorem of I. Tomon.
This lemma has several other applications to the Erdős-Hajnal conjecture. For instance, it implies that for every cycle C and forest T, there exists c>0 such that every graph that is both C-free and T’-free (where T’ is the complement of T) has a clique or stable set of size $|G|^c$. (Until now this was open when C has length five and T is a 5-vertex path.)
Joint work with Maria Chudnovsky, Alex Scott and Sophie Spirkl.

Jinha Kim (김진하), On a conjecture by Kalai and Meshulam - the Betti number of the independence complex of ternary graphs
2020-12-22 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Given a graph G=(V,E), the independence complex of G is the abstract simplicial complex I(G) on V whose faces are the independent sets of G. A graph is ternary if it does not contain an induced cycle of length divisible by three. Kalai and Meshulam conjectured that if G is ternary then the sum of the Betti numbers of I(G) is either 0 or 1. In this talk, I will introduce a result by Zhang and Wu, which proves the Kalai-Meshulam conjecture.

Jaiung Jun (전재웅), On the Hopf algebra of multi-complexes
2020-12-17 10:00 - 11:00 | Zoom ID: 869 4632 6610 (ibsdimag)
In combinatorics, Hopf algebras appear naturally when studying various classes of combinatorial objects, such as graphs, matroids, posets or symmetric functions. Given such a class of combinatorial objects, basic information on these objects regarding assembly and disassembly operations are encoded in the algebraic structure of a Hopf algebra. One then hopes to use algebraic identities of a Hopf algebra to return to combinatorial identities of combinatorial objects of interest.
In this talk, I introduce a general class of combinatorial objects, which we call multi-complexes, which simultaneously generalizes graphs, hypergraphs and simplicial and delta complexes. I also introduce a combinatorial Hopf algebra obtained from multi-complexes. Then, I describe the structure of the Hopf algebra of multi-complexes by finding an explicit basis of the space of primitives, which is of combinatorial relevance. If time permits, I will illustrate some potential applications.
This is joint work with Miodrag Iovanov.

Karl Heuer, Even Circuits in Oriented Matroids
2020-12-09 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
In this talk I will state a generalisation of the even directed cycle problem, which asks whether a given digraph contains a directed cycle of even length, to orientations of regular matroids. Motivated by this problem, I will define non-even oriented matroids generalising non-even digraphs, which played a central role in resolving the computational complexity of the even dicycle problem. Then I will present and discuss our two results regarding these notions:
First we shall see that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids.
Second and with the main focus for this talk, we shall characterise the class of non-even oriented bond matroids in terms of forbidden minors, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen. The second result makes use of a new concept of minors for oriented matroids, which generalises butterfly minors for digraphs to oriented matroids.
The part of this talk regarding the second result will be mostly graph theoretical and does not require much knowledge about Matroid Theory.
This talk is about joint work [1] with Raphael Steiner and Sebastian Wiederrecht.
[1] K. Heuer, R. Steiner and S. Wiederrecht, Even Circuits in Oriented Matroids, arxiv:2010.08988

Hong Liu (刘鸿), A solution to Erdős and Hajnal's odd cycle problem
2020-12-08 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
I will go over the history on the study of the set of cycle lengths of graphs with large average degree or chromatic number, and discuss recent work with Richard Montgomery on this topic. In particular, we will see the divergence of harmonic sum of odd cycle lengths in graphs with large chromatic number and the appearance of cycle lengths in very sparse sequences (such as powers of 2). The methods developed in this work allows also us to embed equally divided clique subdivisions, which was conjectured by Thomassen.

Deniz Sarikaya, What means Hamiltonicity for infinite graphs and how to force it via forbidden induced subgraphs
2020-12-03 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
The study of Hamiltonian graphs, i.e. finite graphs having a cycle that contains all vertices of the graph, is a central theme of finite graph theory. For infinite graphs such a definition cannot work, since cycles are finite. We shall debate possible concepts of Hamiltonicity for infinite graphs and eventually follow the topological approach by Diestel and Kühn [2,3], which allows to generalize several results about being a Hamiltonian graph to locally finite graphs, i.e. graphs where each vertex has finite degree. An infinite cycle of a locally finite connected graph G is defined as a homeomorphic image of the unit circle $S^1$ in the Freudenthal compactification |G| of G. Now we call G Hamiltonian if there is an infinite cycle in |G| containing all vertices of G. For an introduction see [1].
We examine how to force Hamiltonicity via forbidden induced subgraphs and present recent extensions of results for Hamiltonicity in finite claw-free graphs to locally finite ones. The first two results are about claw- and net-free graphs, claw- and bull-free graphs, the last also about further graph classes being structurally richer, where we focus on paws as relevant subgraphs, but relax the condition of forbidding them as induced subgraphs.
The goal of the talk is twofold: (1) We introduce the history of the topological viewpoint and argue that there are some merits to it (2) sketch the proofs for the results mentioned above in some details.
This is based on joint work [4,5] with Karl Heuer.
Bibliography
[1] R. Diestel (2017) Infinite Graphs. In: Graph Theory. Graduate Texts in Mathematics, vol 173. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-53622-3_8
[2] R. Diestel and D. Kühn, On infinite cycles I, Combinatorica 24 (2004), pp. 69-89.
[3] R. Diestel and D. Kühn, On infinite cycles II, Combinatorica 24 (2004), pp. 91-116.
[4] K. Heuer and D. Sarikaya, Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs I: nets and bulls, arXiv:2006.09160
[5] K. Heuer and D. Sarikaya, Forcing Hamiltonicity in locally finite graphs via forbidden induced subgraphs II: paws, arXiv:2006.09166

Joonkyung Lee (이준경), On common graphs
2020-12-02 17:00 - 18:00 | Zoom ID:8628398170 (123450)
A graph $H$ is common if the number of monochromatic copies of $H$ in a 2-edge-colouring of the complete graph $K_n$ is minimised by the random colouring. Burr and Rosta, extending a famous conjecture by Erdős, conjectured that every graph is common. The conjectures by Erdős and by Burr and Rosta were disproved by Thomason and by Sidorenko, respectively, in the late 1980s.
Despite its importance, the full classification of common graphs is still a wide open problem and has not seen much progress since the early 1990s. In this lecture, I will present some old and new techniques to prove whether a graph is common or not.

Debsoumya Chakraborti, Rainbow matchings in edge-colored simple graphs
2020-12-01 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
There has been much research on finding a large rainbow matching in a properly edge-colored graph, where a proper edge coloring is a coloring of the edge set such that no same-colored edges are incident. Barát, Gyárfás, and Sárközy conjectured that in every proper edge coloring of a multigraph (with parallel edges allowed, but not loops) with $2q$ colors where each color appears at least $q$ times, there is always a rainbow matching of size $q$. We prove that $2q + o(q)$ colors are enough if the graph is simple, confirming the conjecture asymptotically for simple graphs. We also make progress in the lower bound on the required number of colors for simple graphs, which disproves a conjecture of Aharoni and Berger. We use a randomized algorithm to obtain a large rainbow matching, and the analysis of the algorithm is based on differential equations method. We will also briefly comment on the limitations of using our probabilistic approach for the problem. This talk will be based on a joint work with Po-Shen Loh.

Joonkyung Lee (이준경), On Ramsey multiplicity
2020-11-30 17:00 - 18:00 | Zoom ID:8628398170 (123450)
Ramsey’s theorem states that, for a fixed graph $H$, every 2-edge-colouring of $K_n$ contains a monochromatic copy of $H$ whenever $n$ is large enough. Perhaps one of the most natural questions after Ramsey’s theorem is then how many copies of monochromatic $H$ can be guaranteed to exist. To formalise this question, let the Ramsey multiplicity $M(H;n)$ be the minimum number of labelled copies of monochromatic $H$ over all 2-edge-colouring of $K_n$. We define the Ramsey multiplicity constant $C(H)$ is defined by $C(H):=lim_{nrightarrowinfty}frac{M(H,n)}{n(n-1)cdots(n-v+1)}$. I will discuss various bounds for C(H) that are known so far.

Da Qi Chen, Bipartite Saturation
2020-11-26 10:00 - 11:00 | Zoom ID: 869 4632 6610 (ibsdimag)
In extremal graph theory, a graph G is H-saturated if G does not contain a copy of H but adding any missing edge to G creates a copy of H. The saturation number, sat(n, H), is the minimum number of edges in an n-vertex H-saturated graph. This class of problems was first studied by Zykov and Erdős, Hajnal, and Moon. They also determined the saturation number when H is a clique and classified the extremal structures.
In this talk, we will focus mainly on the bipartite saturation problem (which was also first introduced by Erdős, Hajnal, and Moon). Here, we always assume that both G and H are bipartite graphs. Then, G is H-saturated if G does not contain H but adding any missing edge across the bipartition creates a copy of H. We can then similarly define sat(n, H) as the minimum number of edges of an n-by-n bipartite graph that is also H-saturated. One of the most interesting and natural questions here is to determine the saturation number for the complete bipartite graph $K_{s, t}$. When s=t, the saturation number and its extremal structures were determined long ago but nothing else is known for the general case. Half a decade ago, Gan, Korandi, and Sudakov gave an asymptotically tight bound that was only off by an additive constant. We will highlight the main ideas behind that proof and show, with some additional techniques, how the bound can be improved to achieve tightness for the case when s=t-1.
This talk is based on collaborative work with Debsoumya Chakraborti and Mihir Hasabnis. See arXiv: https://arxiv.org/abs/2009.07651 for the full paper.

Duksang Lee (이덕상), Characterizing matroids whose bases form graphic delta-matroids
2020-11-24 16:30 - 17:30 | 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 the class of delta-graphic matroids has at most 48 elements. This is joint work with Sang-il Oum.

Yijia Chen (陈翌佳), Graphs of bounded shrub-depth, through a logic lens
2020-11-19 16:30 - 17:30 | 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 depth only depends on the
shrub-depth of input graphs.
Graphs of bounded shrub-depth can be characterized by
a finite set of forbidden induced subgraphs [Ganian et al. 2015].

Central to the first result is the definability in first-order logic of
tree-models for graphs of bounded shrub-depth. For the second
result, we observe that shrub-depth can be easily generalized
to infinite graphs, and thus some classical tools, i.e., Craig’s
Interpolation and Łoś-Tarski Theorem, in model theory are
applicable to graphs of bounded shrub-depth.
This is joint work with Jörg Flum.

Meike Hatzel, Constant congestion bramble
2020-11-11 16:30 - 17:30 | 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 V(H_2)
eq emptyset$ or there is an edge of $G$ with one endpoint in $V(H_1)$ and the second endpoint in $V(H_2)$. The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble.
Brambles are objects dual to treewidth: As shown by Seymour and Thomas, the maximum order of a bramble in an undirected graph $G$ equals one plus the treewidth of $G$. However, as shown by Grohe and Marx, brambles of high order may necessarily be of exponential size: In a constant-degree $n$-vertex expander a bramble of order $Omega(n^{1/2+delta})$ requires size exponential in $Omega(n^{2delta})$ for any fixed $delta in (0,frac{1}{2}]$. On the other hand, the combination of results of Grohe and Marx, and Chekuri and Chuzhoy shows that a graph of treewidth $k$ admits a bramble of order $widetilde{Omega}(k^{1/2})$ and size $widetilde{O}(k^{3/2})$. ($widetilde{Omega}$ and $widetilde{O}$ hide polylogarithmic factors and divisors, respectively.)
We first sharpen the second bound by proving that every graph $G$ of treewidth at least $k$ contains a bramble of order $widetilde{Omega}(k^{1/2})$ and congestion $2$, i.e., every vertex of $G$ is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second, we provide a tight upper bound for the lower bound of Grohe and Marx: For every $delta in (0,frac{1}{2}]$, every graph $G$ of treewidth at least $k$ contains a bramble of order $widetilde{Omega}(k^{1/2+delta})$ and size $2^{widetilde{O}(k^{2delta})}$.

Casey Tompkins, Extremal forbidden poset problems in Boolean and linear lattices
2020-11-10 16:30 - 17:30 | 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 $[n]$ which does not contain a given poset $P$ among its containment relations. In this talk, I will discuss what is known about the behavior of $La(n,P)$ and its natural extension to the lattice of subspaces of a vector space over a finite field. In particular, I will highlight some recent joint work with Jimeng Xiao. Many open problems will also be discussed.

Daniel Cranston, Vertex Partitions into an Independent Set and a Forest with Each Component Small
2020-11-05 10:00 - 11:00 | Zoom ID: 869 4632 6610 (ibsdimag)
For each integer $kge 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 possible. Hendrey, Norin, and Wood asked for the largest function $g(a,b)$ such that if $operatorname{mad}(G) < g(a,b)$ then $V(G)$ has a partition into sets $A$ and $B$ such that $operatorname{mad}(G[A]) < a$ and $operatorname{mad}(G[B]) < b$. They specifically asked for the value of $g(1,b)$, which corresponds to the case that $A$ is an independent set. Previously, the only values known were $g(1,4/3)$ and $g(1,2)$. We find the value of $g(1,b)$ whenever $4/3 < b < 2$. This is joint work with Matthew Yancey.

Jaeseong Oh (오재성), A 2-isomorphism theorem for delta-matroids
2020-11-03 16:30 - 17:30 | 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.

Jeong Ok Choi (최정옥), Various game-theoretic models on graphs
2020-10-27 16:30 - 17:30 | 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 advantageous to be epidemic considering the whole class of infinite regular graphs.
A network creation game model, on the other hand, tries to explain the dynamics on forming a network structure when each vertex plays independently and selfishly. An important question is how costly a formation can be made without any central coordination, and the concept of Price of Anarchy (PoA) is introduced. In the model originally suggested by Fabrikant et al., PoA measures how bad the forming cost can be at Nash equilibria compared to absolute minimum, and they conjectured that this inefficiency can happen only when some tree structures are formed (Tree Conjecture). We will introduce recent progress on this tree conjecture, remaining open problems, and possible variations.
This talk includes part of joint work with Unjong Yu.

Chun-Hung Liu (劉俊宏), Asymptotic dimension of minor-closed families and beyond
2020-10-22 10:10 - 11:10 | 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 dimension of classes of finite weighted graphs. We prove that the asymptotic dimension of any minor-closed family of weighted graphs, any class of weighted graphs of bounded tree-width, and any class of graphs of bounded layered tree-width are at most 2, 1, and 2, respectively. The first result solves a question of Fujiwara and Papasoglu; the second and third results solve a number of questions of Bonamy, Bousquet, Esperet, Groenland, Pirot and Scott. These bounds for asymptotic dimension are optimal and generalize and improve some results in the literature, including results for Riemannian surfaces and Cayley graphs of groups with a forbidden minor.

Joonkyung Lee (이준경), On graph norms for complex-valued functions
2020-10-21 16:30 - 17:30 | 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 $|.|_{H,alpha}$) is a norm on the vector space of real-valued (resp. complex-valued) functions. This generalises Gowers norms, a widely used tool in extremal combinatorics to quantify quasirandomness.
We unify these two seemingly different notions of graph norms in real- and complex-valued settings, by proving that $H$ is complex-norming if and only if it is real-norming. Our proof does not explicitly construct a suitable $2$-edge-colouring $alpha$ but obtain its existence and uniqueness, which may be of independent interest.
As an application, we give various example graphs that are not norming. In particular, we show that hypercubes are not norming, which answers the only question appeared in Hatami’s pioneering work in the area that remained untouched. This is joint work with Alexander Sidorenko.

Hong Liu (刘鸿), Cycles and trees in graphs (8/8)
2020-10-15 17:00 - 18:00 | Zoom ID:8628398170 (123450)
This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.
