Mihyun Kang (강미현), The genus of a random graph and the fragile genus property
2019-08-20 16:30 - 17:30 (Asia/Seoul) | Room B232, IBS (기초과학연구원)
In this talk we shall discuss how quickly the genus of the Erdős-Rényi random graph grows as the number of edges increases and how dramatically a small number of random edges can increase the genus of a randomly perturbed graph. (Joint work with Chris Dowden and Michael Krivelevich)

Kevin Hendrey, The minimum connectivity forcing forest minors in large graphs
2019-09-10 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Given a graph $G$, we define $textrm{ex}_c(G)$ to be the minimum value of $t$ for which there exists a constant $N(t,G)$ such that every $t$-connected graph with at least $N(t,G)$ vertices contains $G$ as a minor. The value of $textrm{ex}_c(G)$ is known to be tied to the vertex cover number $tau(G)$, and in fact $tau(G)leq textrm{ex}_c(G)leq frac{31}{2}(tau(G)+1)$. We give the precise value of $textrm{ex}_c(G)$ when $G$ is a forest. In particular we find that $textrm{ex}_c(G)leq tau(G)+2$ in this setting, which is tight for infinitely many forests.

Cory Palmer, A survey of Turán-type subgraph counting problems
2019-09-19 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Let $F$ and $H$ be graphs. The subgraph counting function $operatorname{ex}(n,H,F)$ is defined as the maximum possible number of subgraphs $H$ in an $n$-vertex $F$-free graph. This function is a direct generalization of the Turán function as $operatorname{ex}(n,F)=operatorname{ex}(n,K_2,F)$. The systematic study of $operatorname{ex}(n,H,F)$ was initiated by Alon and Shikhelman in 2016 who generalized several classical results in extremal graph theory to the subgraph counting setting. Prior to their paper, a number of individual cases were investigated; a well-known example is the question to determine the maximum number of pentagons in a triangle-free graph. In this talk we will survey results on the function $operatorname{ex}(n,H,F)$ including a number of recent papers. We will also discuss this function’s connection to hypergraph Turán problems.

Casey Tompkins, Extremal problems for Berge hypergraphs
2019-10-01 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Given a graph $G$, there are several natural hypergraph families one can define. Among the least restrictive is the family $BG$ of so-called Berge copies of the graph $G$. In this talk, we discuss Turán problems for families $BG$ in $r$-uniform hypergraphs for various graphs $G$. In particular, we are interested in general results in two settings: the case when $r$ is large and $G$ is any graph where this Turán number is shown to be eventually subquadratic, as well as the case when $G$ is a tree where several exact results can be obtained. The results in the first part are joint with Grósz and Methuku, and the second part with Győri, Salia and Zamora.

Alexandr V. Kostochka, On Ramsey-type problems for paths and cycles in dense graphs
2019-10-08 16:30 - 17:30 | Room 1501, Bldg. E6-1, KAIST
A well-known Ramsey-type puzzle for children is to prove that among any 6 people either there are 3 who know each other or there are 3 who do not know each other. More generally, a graph $G$ arrows a graph $H$ if for any coloring of the edges of $G$ with two colors, there is a monochromatic copy of $H$. In these terms, the above puzzle claims that the complete $6$-vertex graph $K_6$ arrows the complete $3$-vertex graph $K_3$.
We consider sufficient conditions on the dense host graphs $G$ to arrow long paths and even cycles. In particular, for large $n$ we describe all multipartite graphs that arrow paths and cycles with $2n$ edges. This implies a conjecture by Gyárfás, Ruszinkó, Sárkőzy and Szemerédi from 2007 for such $n$. Also for large $n$ we find which minimum degree in a $(3n-1)$-vertex graph $G$ guarantees that $G$ arrows the $2n$-vertex path. This yields a more recent conjecture of Schelp.
This is joint work with Jozsef Balogh, Mikhail Lavrov and Xujun Liu.

Alexandr V. Kostochka, Reconstructing graphs from smaller subgraphs
2019-10-10 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A graph or graph property is $ell$-reconstructible if it is determined by the multiset of all subgraphs obtained by deleting $ell$ vertices. Apart from the famous Graph Reconstruction Conjecture, Kelly conjectured in 1957 that for each $ellinmathbb N$, there is an integer $n=n(ell)$ such that every graph with at least $n$ vertices is $ell$-reconstructible.
We show that for each $nge7$ and every $n$-vertex graph $G$, the degree list and connectedness of $G$ are $3$-reconstructible, and the threshold $ngeq 7$ is sharp for both properties.‌ We also show that all $3$-regular graphs are $2$-reconstructible.

Zi-Xia Song (宋梓霞), Ramsey numbers of cycles under Gallai colorings
2019-10-15 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
For a graph $H$ and an integer $kge1$, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $mge4 $ vertices. For odd cycles, Bondy and ErdH{o}s in 1973 conjectured that for all $kge1$ and $nge2$, $R_k(C_{2n+1})=ncdot 2^k+1$. Recently, this conjecture has been verified to be true for all fixed $k$ and all $n$ sufficiently large by Jenssen and Skokan; and false for all fixed $n$ and all $k$ sufficiently large by Day and Johnson. Even cycles behave rather differently in this context. Little is known about the behavior of $R_k(C_{2n})$ in general. In this talk we will present our recent results on Ramsey numbers of cycles under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. We prove that the aforementioned conjecture holds for all $k$ and all $n$ under Gallai colorings. We also completely determine the Ramsey number of even cycles under Gallai colorings.
Joint work with Dylan Bruce, Christian Bosse, Yaojun Chen and Fangfang Zhang.

Joonkyung Lee (이준경), On some properties of graph norms
2019-10-22 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
For a graph $H$, its homomorphism density in graphs naturally extends to the space of two-variable symmetric functions $W$ in $L^p$, $pgeq e(H)$, denoted by $t_H(W)$. One may then define corresponding functionals $|W|_{H}:=|t_H(W)|^{1/e(H)}$ and $|W|_{r(H)}:=t_H(|W|)^{1/e(H)}$ and say that $H$ is (semi-)norming if $|.|_{H}$ is a (semi-)norm and that $H$ is weakly norming if $|.|_{r(H)}$ is a norm.
We obtain some results that contribute to the theory of (weakly) norming graphs. Firstly, we show that ‘twisted’ blow-ups of cycles, which include $K_{5,5}setminus C_{10}$ and $C_6square K_2$, are not weakly norming. This answers two questions of Hatami, who asked whether the two graphs are weakly norming. Secondly, we prove that $|.|_{r(H)}$ is not uniformly convex nor uniformly smooth, provided that $H$ is weakly norming. This answers another question of Hatami, who estimated the modulus of convexity and smoothness of $|.|_{H}$. We also prove that every graph $H$ without isolated vertices is (weakly) norming if and only if each component is an isomorphic copy of a (weakly) norming graph. This strong factorisation result allows us to assume connectivity of $H$ when studying graph norms. Based on joint work with Frederik Garbe, Jan Hladký, and Bjarne Schülke.

Pascal Gollin, A Cantor-Bernstein-type theorem for spanning trees in infinite graphs
2019-10-29 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Given a cardinal $lambda$, a $lambda$-packing of a graph $G$ is a family of $lambda$ many edge-disjoint spanning trees of $G$, and a $lambda$-covering of $G$ is a family of spanning trees covering $E(G)$.
We show that if a graph admits a $lambda$-packing and a $lambda$-covering then the graph also admits a decomposition into $lambda$ many spanning trees. In this talk, we concentrate on the case of $lambda$ being an infinite cardinal. Moreover, we will provide a new and simple proof for a theorem of Laviolette characterising the existence of a $lambda$-packing, as well as for a theorem of Erdős and Hajnal characterising the existence of a $lambda$-covering.
Joint work with Joshua Erde, Attila Joó, Paul Knappe and Max Pitz.

Sun Kim (김선), Two identities in Ramanujan’s Lost Notebook with Bessel function series
2019-11-05 16:30 - 17:30 | Room 1401, Bldg. E6-1, KAIST
On page 335 in his lost notebook, Ramanujan recorded without proofs two identities involving finite trigonometric sums and doubly infinite series of Bessel functions. We proved each of these identities under three different interpretations for the double series, and showed that they are intimately connected with the classical circle and divisor problems in number theory. Furthermore, we established many analogues and generalizations of them. This is joint work with Bruce C. Berndt and Alexandru Zaharescu.

Tony Huynh, Stable sets in graphs with bounded odd cycle packing number
2019-11-12 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
It is a classic result that the maximum weight stable set problem is efficiently solvable for bipartite graphs. The recent bimodular algorithm of Artmann, Weismantel and Zenklusen shows that it is also efficiently solvable for graphs without two disjoint odd cycles. The complexity of the stable set problem for graphs without $k$ disjoint odd cycles is a long-standing open problem for all other values of $k$. We prove that under the additional assumption that the input graph is embedded in a surface of bounded genus, there is a polynomial-time algorithm for each fixed $k$. Moreover, we obtain polynomial-size extended formulations for the respective stable set polytopes.
To this end, we show that 2-sided odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed surface. This result may be of independent interest and extends a theorem of Kawarabayashi and Nakamoto asserting that odd cycles satisfy the Erdős-Pósa property in graphs embedded in a fixed orientable surface.
Eventually, our findings allow us to reduce the original problem to the problem of finding a minimum-cost non-negative integer circulation of a certain homology class, which we prove to be efficiently solvable in our case.
This is joint work with Michele Conforti, Samuel Fiorini, Gwenaël Joret, and Stefan Weltge.

Ruth Luo, Induced Turán problems for hypergraphs
2019-11-19 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Let $F$ be a graph. We say that a hypergraph $mathcal H$ is an induced Berge $F$ if there exists a bijective mapping $f$ from the edges of $F$ to the hyperedges of $mathcal H$ such that for all $xy in E(F)$, $f(xy) cap V(F) = {x,y}$. In this talk, we show asymptotics for the maximum number of edges in $r$-uniform hypergraphs with no induced Berge $F$. In particular, this function is strongly related to the generalized Turán function $ex(n,K_r, F)$, i.e., the maximum number of cliques of size $r$ in $n$-vertex, $F$-free graphs. Joint work with Zoltan Füredi.

Frédéric Meunier, Topological bounds for graph representations over any field
2019-11-21 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Haviv (European Journal of Combinatorics, 2019) has recently proved that some topological lower bounds on the chromatic number of graphs are also lower bounds on their orthogonality dimension over $mathbb {R}$. We show that this holds actually for all known topological lower bounds and all fields. We also improve the topological bound he obtained for the minrank parameter over $mathbb {R}$ – an important graph invariant from coding theory – and show that this bound is actually valid for all fields as well. The notion of independent representation over a matroid is introduced and used in a general theorem having these results as corollaries. Related complexity results are also discussed.
This is joint work with Meysam Alishahi.

Jakub Gajarský, First-order interpretations of bounded expansion classes
2019-12-10 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth decompositions, replacing treedepth by its dense analogue called shrubdepth.

Hong Liu, A proof of Mader's conjecture on large clique subdivisions in $C_4$-free graphs
2019-12-12 16:30 - 17:30 | Room 1401, Bldg. E6-1, KAIST
Given any integers $s,tgeq 2$, we show there exists some $c=c(s,t)>0$ such that any $K_{s,t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $cd^{frac{1}{2}frac{s}{s-1}}$ vertices. In particular, when $s=2$ this resolves in a strong sense the conjecture of Mader in 1999 that every $C_4$-free graph has a subdivision of a clique with order linear in the average degree of the original graph. In general, the widely conjectured asymptotic behaviour of the extremal density of $K_{s,t}$-free graphs suggests our result is tight up to the constant $c(s,t)$. This is joint work with Richard Montgomery.

Attila Joó, Base partition for finitary-cofinitary matroid families
2019-12-19 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Let ${mathcal{M} = (M_i colon iin K)}$ be a finite or infinite family consisting of finitary and cofinitary matroids on a common ground set $E$.
We prove the following Cantor-Bernstein-type result: if $E$ can be covered by sets ${(B_i colon iin K)}$ which are bases in the corresponding matroids and there are also pairwise disjoint bases of the matroids $M_i$ then $E$ can be partitioned into bases with respect to $mathcal{M}$.

Jaiung Jun (전재웅), The Hall algebra of the category of matroids
2019-12-26 16:30 - 17:30 | Room 1401, Bldg. E6-1, KAIST
To an abelian category A satisfying certain finiteness conditions, one can associate an algebra H_A (the Hall algebra of A) which encodes the structures of the space of extensions between objects in A. For a non-additive setting, Dyckerhoff and Kapranov introduced the notion of proto-exact categories, as a non-additive generalization of an exact category, which is shown to suffice for the construction of an associative Hall algebra. In this talk, I will discuss the category of matroids in this perspective.

Sanjeeb Dash, Boolean decision rules via column generation
2020-01-14 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
In many applications of machine learning, interpretable or explainable models for binary classification, such as decision trees or decision lists, are preferred over potentially more accurate but less interpretable models such as random forests or support vector machines. In this talk, we consider boolean decision rule sets (equivalent to boolean functions in disjunctive normal form) as interpretable models for binary classification. We define the complexity of a rule set to be the number of rules (clauses) plus the number of conditions (literals) across all clauses, and assume that simpler or less complex models are more interpretable. We discuss an integer programming formulation for such models that trades off classification accuracy against rule simplicity, and obtain high-quality classifiers of this type using column generation techniques. Compared to some recent alternatives, our algorithm dominates the accuracy-simplicity trade-off in 8 out of 16 datasets, and also produced the winning entry in the 2018 FICO explainable machine learning challenge. When compared to rule learning methods designed for accuracy, our algorithm sometimes finds significantly simpler solutions that are no less accurate.

Ben Lund, Furstenberg sets over finite fields
2020-01-15 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
An important family of incidence problems are discrete analogs of deep questions in geometric measure theory. Perhaps the most famous example of this is the finite field Kakeya conjecture, proved by Dvir in 2008. Dvir’s proof introduced the polynomial method to incidence geometry, which led to the solution to many long-standing problems in the area.
I will talk about a generalization of the Kakeya conjecture posed by Ellenberg, Oberlin, and Tao. A $(k,m)$-Furstenberg set S in $mathbb F_q^n$ has the property that, parallel to every affine $k$-plane V, there is a k-plane W such that $|W cap S| > m$. Using sophisticated ideas from algebraic geometry, Ellenberg and Erman showed that if S is a $(k,m)$-Furstenberg set, then $|S| > c m^{n/k}$, for a constant c depending on n and k. In recent joint work with Manik Dhar and Zeev Dvir, we give simpler proofs of stronger bounds. For example, if $m>2^{n+7}q$, then $|S|=(1-o(1))mq^{n-k}$, which is tight up to the $o(1)$ term.

Adam Zsolt Wagner, The largest projective cube-free subsets of $Z_{2^n}$
2020-01-20 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
What is the largest subset of $Z_{2^n}$ that doesn’t contain a projective d-cube? In the Boolean lattice, Sperner’s, Erdos’s, Kleitman’s and Samotij’s theorems state that families that do not contain many chains must have a very specific layered structure. We show that if instead of $Z_2^n$ we work in $Z_{2^n}$, analogous statements hold if one replaces the word k-chain by projective cube of dimension $2^{k-1}$. The largest d-cube-free subset of $Z_{2^n}$, if d is not a power of two, exhibits a much more interesting behaviour.
This is joint work with Jason Long.

Dillon Mayhew, Courcelle's Theorem for hypergraphs
2020-01-28 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Courcelle’s Theorem is an influential meta-theorem published in 1990. It tells us that a property of graph can be tested in polynomial time, as long as the property can expressed in the monadic second-order logic of graphs, and as long as the input is restricted to a class of graphs with bounded tree-width. There are several properties that are NP-complete in general, but which can be expressed in monadic logic (3-colourability, Hamiltonicity…), so Courcelle’s Theorem implies that these difficult properties can be tested in polynomial time when the structural complexity of the input is limited.
Matroids can be considered as a special class of hypergraphs. Any finite set of vectors over a field leads to a matroid, and such a matroid is said to be representable over that field. Hlineny produced a matroid analogue of Courcelle’s Theorem for input classes with bounded branch-width that are representable over a finite field.
We have now identified the structural properties of hypergraph classes that allow a proof of Hliněný’s Theorem to go through. This means that we are able to extend his theorem to several other natural classes of matroids.
This talk will contain an introduction to matroids, monadic logic, and tree-automata.
This is joint work with Daryl Funk, Mike Newman, and Geoff Whittle.

Dong Yeap Kang (강동엽), Fragile minor-monotone parameters under random edge perturbation
2020-02-18 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph $H$. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, and the size of a largest complete minor become very large regardless of the shape of $H$. Our results are close to best possible for various cases. We also discuss analogous results for randomly perturbed bipartite graphs as well as the size of a largest complete odd minor in randomly perturbed graphs.

Xin Zhang (张欣), On the equitable tree-coloring of graphs with low degeneracy
2020-02-25 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A (vertex) $k$-coloring of a graph $G$ is a tree-coloring if each color class induces a forest, and is equitable if the sizes of any two color classes differ by at most 1. The first relative result concerning the equitable tree-coloring of graphs is due to H. Fan, H. A. Kierstead, G. Liu, T. Molla, J.-L. Wu, and X. Zhang (2011), who proved that any graph with maximum degree at most $Delta$ has a $Delta$-coloring so that each color class induces a graph with maximum degree at most 1. After that, many results on this topic were published in the literature. For example, L. Esperet, L. Lemoine, and F. Maffray (2015) showed that any planar graph admits an equitable tree-$k$-coloring for every integer $kge 4$，and G. Chen, Y. Gao, S. Shan, G. Wang, and J.-L. Wu (2017) proved that any 5-degenerate graph with maximum degree at most $Delta$ admits an equitable tree-$k$-coloring for every $kgeq lceilfrac{Delta+1}{2}rceil$.
In this talk, we review part of the known results and the conjectures on the equitable tree-coloring of graphs, and then show the sketch proofs of our three new results as follows:
(a) the vertex set of any graph $G$ can be equitably partitioned into $k$ subsets for any integer $kgeqmax{lceilfrac{Delta(G)+1}{2}rceil,lceilfrac{|G|}{4}rceil}$ so that each of them induces a linear forest;
(b) any plane graph with independent crossings admits an equitable tree-$k$-coloring for every integer $kge 8$;
(c) any $d$-degenerate graph with maximum degree at most $Delta$ admits an equitable tree-$k$-coloring for every integer $kgeq (Delta+1)/2$ provided that $Deltageq 10d$.
This is a joint work with Yuping Gao, Bi Li, Yan Li, and Bei Niu.

Eun-Kyung Cho (조은경), Decomposition of a planar graph into a $d$-degenerate graph and a graph with maximum degree at most $h$
2020-03-03 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Given a graph $G$, a decomposition of $G$ is a collection of spanning subgraphs $H_1, ldots, H_t$ of $G$ such that each edge of $G$ is an edge of $H_i$ for exactly one $i in {1, ldots, t}$. Given a positive integer $d$, a graph is said to be $d$-degenerate if every subgraph of it has a vertex of degree at most $d$. Given a non-negative integer $h$, we say that a graph $G$ is $(d,h)$-decomposable if there is a decomposition of $G$ into two spanning subgraphs, where one is a $d$-degenerate graph, and the other is a graph with maximum degree at most $h$.
It is known that a planar graph is $5$-degenerate, but not always $4$-degenerate. This implies that a planar graph is $(5,0)$-decomposable, but not always $(4,0)$-decomposable. Moreover, by related previous results, it is known that a planar graph is $(3,4)$- and $(2,8)$-decomposable.
In this talk, we improve these results by showing that every planar graph is $(4,1)$-, $(3,2)$-, and $(2,6)$-decomposable. The $(4,1)$- and $(3,2)$-decomposabilities are sharp in the sense that the maximum degree condition cannot be reduced more.
This is joint work with Ilkyoo Choi, Ringi Kim, Boram Park, Tingting Shan, and Xuding Zhu.

Dabeen Lee (이다빈), On a generalization of the Chvátal-Gomory closure
2020-03-17 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Integer programming is the problem of optimizing a linear function over the set of integer solutions satisfying a system of inequalities. The most successful technique in practice is the so-called “cutting-plane” algorithm in combination with branch-and-bound enumeration. Cutting-planes for an integer linear program are linear inequalities that are valid for all integer feasible solutions but cut off intermediate fractional solutions.
The Chvátal-Gomory cuts, introduced by Gomory in 1958 and further studied by Chvátal in 1973 in relation to their applications in combinatorial optimization, are the first class of general-purpose cutting-planes in the literature. The split cuts, whose name was coined by Cook, Kannan, and Schrijver in 1980, are another class of important cutting-planes in modern integer programming. Although there are infinitely many cuts in each class, it is known that only finitely many of them are nonredundant, which is related to designing a finite-convergent cutting-plane algorithm. In this talk, we introduce a new class of cutting-planes that generalizes the Chvátal-Gomory cuts and generalizes a special case of the split cuts. As the two classic classes of cutting-planes, we show that only a finite number of cuts can be redundant.
This talk is based on a joint work with Sanjeeb Dash and Oktay Günlük.

Kevin Hendrey, Covering radius in the Hamming permutation space
2020-03-24 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Our problem can be described in terms of a two player game, played with the set $mathcal{S}_n$ of permutations on ${1,2,dots,n}$. First, Player 1 selects a subset $S$ of $mathcal{S}_n$ and shows it to Player 2. Next, Player 2 selects a permutation $p$ from $mathcal{S}_n$ as different as possible from the permutations in $S$, and shows it to Player 1. Finally, Player 1 selects a permutation $q$ from $S$, and they compare $p$ and $q$. The aim of Player 1 is to ensure that $p$ and $q$ differ in few positions, while keeping the size of $S$ small. The function $f(n,s)$ can be defined as the minimum size of a set $Ssubseteq mathcal{S}_n$ that Player 1 can select in order to gaurantee that $p$ and $q$ will differ in at most $s$ positions.
I will present some recent results on the function $f(n,s)$. We are particularly interested in determining the value $f(n,2)$, which would resolve a conjecture of Kézdy and Snevily that implies several famous conjectures for Latin squares. Here we improve the best known lower bound, showing that $f(n,2)geqslant 3n/4$. This talk is based on joint work with Ian M. Wanless.

Ringi Kim (김린기), The strong clique number of graphs with forbidden cycles
2020-03-31 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
The strong clique number of a graph $G$ is the maximum size of a set of edges of which every pair has distance at most two.
In this talk, we prove that every ${C_5,C_{2k}}$-free graph has strong clique number at most $kDelta(G)-(k-1)$, which resolves a conjecture by Cames van Batenburg et al. We also prove that every $C_{2k}$-free graph has strong clique number at most $(2k−1)Delta(G) + (2k−1)^2$, improving the previous known upper bound $10k^2 (Delta(G)-1)$ due to Cames van Batenburg et al. This is joint work with Eun-Kyung Cho, Ilkyoo Choi, and Boram Park.

Pascal Gollin, Disjoint dijoins for classes of dibonds in finite and infinite digraphs
2020-04-07 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A dibond in a directed graph is a bond (i.e. a minimal non-empty cut) for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of an edge set meeting every dicut equals the maximum number of disjoint dibonds in that digraph. We call such sets dijoins.
Woodall conjectured a dual statement. He asked whether the maximum number of disjoint dijoins in a digraph equals the minimum size of a dibond.
We study a modification of this question where we restrict our attention to certain classes of dibonds, i.e. whether for a class $mathfrak{B}$ of dibonds of a digraph the maximum number of disjoint edge sets meeting every dibond in $mathfrak{B}$ equal the size a minimum dibond in $mathfrak{B}$.
In particular, we verify this questions for nested classes of dibonds, for the class of dibonds of minimum size, and for classes of infinite dibonds.

Casey Tompkins, Saturation problems in the Ramsey theory of graphs, posets and point sets
2020-04-14 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
In 1964, Erdős, Hajnal and Moon introduced a saturation version of Turán’s classical theorem in extremal graph theory. In particular, they determined the minimum number of edges in a $K_r$-free, $n$-vertex graph with the property that the addition of any further edge yields a copy of $K_r$. We consider analogues of this problem in other settings. We prove a saturation version of the Erdős-Szekeres theorem about monotone subsequences and saturation versions of some Ramsey-type theorems on graphs and Dilworth-type theorems on posets.
We also consider semisaturation problems, wherein we allow the family to have the forbidden configuration, but insist that any addition to the family yields a new copy of the forbidden configuration. In this setting, we prove a semisaturation version of the Erdős-Szekeres theorem on convex $k$-gons, as well as multiple semisaturation theorems for sequences and posets.
This project was joint work with Gábor Damásdi, Balázs Keszegh, David Malec, Zhiyu Wang and Oscar Zamora.

Sang-il Oum (엄상일), Survey on vertex-minors
2020-04-21 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
For a vertex v of a graph G, the local complementation at v is an operation to obtain a new graph denoted by G*v from G such that two distinct vertices x, y are adjacent in G*v if and only if both x, y are neighbors of v and x, y are non-adjacent, or at least one of x, y is not a neighbor of v and x, y are adjacent. A graph H is a vertex-minor of a graph G if H is obtained from G by a sequence of local complementation and vertex deletions. Interestingly vertex-minors have been used in the study of measurement-based quantum computing on graph states.
Motivated by the big success of the graph minor structure theory developed deeply by Robertson and Seymour since 1980s, we propose a similar theory for vertex-minors. This talk will illustrate similarities between graph minors and graph vertex-minors and give a survey of known theorems and open problems on vertex-minors of graphs.
