Discrete Mathematics Group

Tuan Tran, Minimum saturated families of sets
2021-01-26 04:30 - 17:30 (Asia/Seoul) | 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.

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.

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.

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.

Jie Ma (马杰), Non-repeated cycle lengths and Sidon sequences
2021-02-10 16:30 - 17:30 | 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.

Martin Ziegler, Quantitative Coding and Complexity Theory of Continuous Data
2021-02-16 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Specifying a computational problem requires fixing encodings for input and output: encoding graphs as adjacency matrices, characters as integers, integers as bit strings, and vice versa. For such discrete data, the actual encoding is usually straightforward and/or complexity-theoretically inessential (up to polynomial time, say).
But concerning continuous data, already real numbers naturally suggest various encodings with very different computational properties.
We recall the existing qualitative theory of computably ‘sensible’ encodings of topological spaces; and we newly develop the quantitative theory of complexity-theoretically ‘sensible’ encodings of metric spaces.
Joint work with Donghyun Lim.

David Wood, Tree densities of sparse graph classes
2021-02-17 10:00 - 11:00 | Zoom ID: 869 4632 6610 (ibsdimag)
This talk considers the following question at the intersection of extremal and structural graph theory: What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a graph class $mathcal{G}$ as $nto infty$? I will answer this question for a variety of sparse graph classes $mathcal{G}$. In particular, we show that the answer is $Theta(n^{alpha_d(T)})$ where $alpha_d(T)$ is the size of the largest stable set in the subforest of $T$ induced by the vertices of degree at most $d$, for some integer $d$ that depends on $mathcal{G}$. For example, when $mathcal{G}$ is the class of $k$-degenerate graphs then $d=k$; when $mathcal{G}$ is the class of graphs containing no $K_{s,t}$-minor ($tgeq s$) then $d=s-1$; and when $mathcal{G}$ is the class of $k$-planar graphs then $d=2$. All these results are in fact consequences of a single lemma in terms of a finite set of excluded subgraphs. This is joint work with Tony Huynh (arXiv:2009.12989).

Minki Kim (김민기), Rainbow paths and rainbow matchings
2021-02-23 16:30 - 17:30 | 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 on a previous result, in which $3n-3$ is replaced by $3n-2$. We also prove a “cooperative” generalization: for $t > 0$ and $n geq 3$, any $3n-4+t$ sets of edges, the union of every $t$ of which contains a matching of size $n$, have rainbow matching of size $n$. This is joint work with Ron Aharoni, Joseph Briggs, and Jinha Kim.

Kevin Hendrey, A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
2021-03-02 16:30 - 17:30 | 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 cycles. Such a duality does not hold if we restrict to odd cycles. However, in 1999, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles.
A multitude of natural properties of cycles can be encoded in this setting, for example cycles of length at least $ell$, cycles of length $p$ modulo $q$, cycles intersecting a prescribed set of vertices at least $t$ times, and cycles contained in given $mathbb{Z}_2$-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties.
This is joint work with J. Pascal Gollin, Ken-ichi Kawarabayashi, O-joung Kwon, and Sang-il Oum.

Debsoumya Chakraborti, Some classical problems in graph saturation
2021-03-09 16:30 - 17:30 | 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 the addition of any edge creates a copy of $F$. The function $operatorname{sat}(n,F)$ is defined to be the minimum number of edges in an $n$-vertex $F$-saturated graph.
In the first half of the talk, we will discuss a generalization of Erdős-Hajnal-Moon theorem (1964), which determined the value of $operatorname{sat}(n,K_s)$. We resolve one of the fundamental questions of minimizing the number of cliques of size $r$ in a $K_s$-saturated graph for all sufficiently large number of vertices, confirming a conjecture of Kritschgau, Methuku, Tait, and Timmons. We further establish a corresponding stability result.
In the second half, we will focus on a central conjecture in graph saturation made by Tuza (1986), which states that for every graph $F$, the limit $lim_{n rightarrow infty} frac{operatorname{sat}(n,F)}{n}$ exists. We make progress in the negative direction of this conjecture.
This talk will be based on a joint work with Po-Shen Loh.

Se-Young Yun (윤세영), Regret in Online Recommendation Systems
2021-03-16 16:30 - 17:30 | 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 population of m users, requests a recommendation. The decision-maker observes the user and selects an item from a catalogue of n items. Importantly, an item cannot be recommended twice to the same user. The probabilities that a user likes each item are unknown. The performance of the recommendation algorithm is captured through its regret, considering as a reference an Oracle algorithm aware of these probabilities. We investigate various structural assumptions on these probabilities: we derive for each structure regret lower bounds, and devise algorithms achieving these limits. Interestingly, our analysis reveals the relative weights of the different components of regret: the component due to the constraint of not presenting the same item twice to the same user, that due to learning the chances users like items, and finally that arising when learning the underlying structure.
This is joint work with Kaito Ariu, Narae Ryu, and Alexandre Proutière.

Yixin Cao (操宜新), Recognizing (unit) interval graphs by zigzag graph searches
2021-03-17 17:00 - 18:00 | Room B232, IBS (기초과학연구원)
Corneil, Olariu, and Stewart [SODA 1998; SIAM Journal on Discrete Mathematics 2009] presented a recognition algorithm for interval graphs by six graph searches. Li and Wu [Discrete Mathematics & Theoretical Computer Science 2014] simplified it to only four. The great simplicity of the latter algorithm is however eclipsed by the complicated and long proofs. The main purpose of this paper is to present a new and significantly shorter proof for Li and Wu’s algorithm, as well as a simpler implementation. We also give a self-contained presentation of the recognition algorithm of Corneil [Discrete Applied Mathematics 2004] for unit interval graphs, based on three sweeps of graph searches. Moreover, we show that two sweeps are already sufficient. Toward the proofs of the main results, we make several new structural observations that might be of independent interests.

Hong Liu (刘鸿), Nested cycles with no geometric crossing
2021-03-22 16:30 - 17:30 | 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$, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound $f(n)=O(n)$ using sublinear expanders.
This is joint work with Irene Gil Fernández, Jaehoon Kim and Younjin Kim.

Édouard Bonnet, Twin-width and ordered binary structures
2021-03-24 17:00 - 18:00 | 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 its vertex set V(G), and every part X of every partition P of the sequence has at most d other parts Y of P with both at least one edge and at least one non-edge between X and Y. Twin-width is closely tied to total orders on the vertices, and can be extended to general binary structures. We will thus consider the twin-width of ordered binary structures, or if you prefer, matrices on a finite alphabet. This turns out to be key in understanding combinatorial, algorithmic, and model-theoretic properties of (hereditary) classes of those objects. We will see several characterizations of bounded twin-width for these classes. The main consequences in the three domains read as follows.

Enumerative combinatorics: All the classes of 0,1-matrices with superexponential growth have growth at least n! (in turn resolving a conjecture of Balogh, Bollobás, and Morris on the growth of hereditary classes of ordered graphs).
Algorithms: First-order model checking of ordered binary structures is tractable exactly when the twin-width is bounded.
Finite model theory: Monadically-dependent and dependent hereditary classes of ordered binary structures are the same.

In addition we get a fixed-parameter algorithm approximating matrix twin-width within a function of the optimum, which is still missing for unordered graphs.
Joint work with Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé. Similar results have been obtained independently by Pierre Simon and Szymon Toruńczyk.

Casey Tompkins, 3-uniform hypergraphs avoiding a cycle of length four
2021-03-30 16:30 - 17:30 | 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 Győri and Lemons and by Füredi and Özkahya. Joint work with Ergemlidze, Győri, Methuku, Salia.

Sophie Spirkl, Pure pairs in ordered graphs
2021-04-01 10:00 - 11:00 | 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 none of the edges between A and B are present. Pure pairs have been studied recently motivated by their connections to the Erdos-Hajnal conjecture.
In this talk, I will discuss the topic of pure pairs in ordered graphs, that is, graphs with a linear ordering on their vertex set. If we exclude a graph H as an ordered induced subgraph, how large a pure pair can we guarantee? I will talk about how the answer differs from the case of unordered graphs and show some of the techniques used.
Based on joint work with Maria Chudnovsky, Jacob Fox, Alex Scott, and Paul Seymour.

Rutger Campbell, Matroid orientability and representability
2021-04-06 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
In this talk we will have a brief introduction to oriented matroids and their relation to real-representability.

Michał Pilipczuk, Structural properties of powers of sparse graphs
2021-04-07 17:00 - 18:00 | Zoom ID: 869 4632 6610 (ibsdimag)
For a graph G and an integer d, the dth power of G is the graph $G^d$ on the same vertex set as G where two vertices are considered adjacent if and only if they are at distance at most d in G. Assuming that G is sparse, what can we say about the structure in $G^d$? Certainly $G^d$ can be dense, as the square of a star is a complete graph, but $G^d$ still retains many properties that can be derived from the sparsity of G. We will present some recent results in this spirit, in particular connected to colorings and to the Erdős-Hajnal property, assuming that G is drawn from a fixed class of bounded expansion or from a fixed nowhere dense class. The talk will be based on the recent papers: “Clustering Powers of Sparse Graphs” (with J. Nešetřil, P. Ossona de Mendez, and X. Zhu) and “Erdős-Hajnal properties for powers of sparse graphs” (with M. Briański, P. Micek, and M. Seweryn).

William Overman, Some Ordered Ramsey Numbers of Graphs on Four Vertices
2021-04-13 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Ordered Ramsey numbers were introduced in 2014 by Conlon, Fox, Lee, and Sudakov. Their results included upper bounds for general graphs and lower bounds showing separation from classical Ramsey numbers. We show the first nontrivial results for ordered Ramsey numbers of specific small graphs. In particular we prove upper bounds for orderings of graphs on four vertices, and determine some numbers exactly using SAT solvers for lower bounds. These results are in the spirit of exact calculations for classical Ramsey numbers and use only elementary combinatorial arguments.
This is joint work with Jeremy Alm, Kayla Coffey, and Carolyn Langhoff.

István Tomon, Ramsey properties of semilinear graphs
2021-04-14 17:00 - 18:00 | Zoom ID: 869 4632 6610 (ibsdimag)
A graph $G$ is semilinear of bounded complexity if the vertices of $G$ are elements of $mathbb{R}^{d}$, and the edges of $G$ are defined by the sign patterns of $t$ linear functions, where $d$ and $t$ are constants. In this talk, I will present several results about the symmetric and asymmetric Ramsey properties of semilinear graphs. Some interesting instances of such graphs are intersection graphs of boxes, interval overlap graphs, and shift graphs, so our results extend several well known theorems about the Ramsey and coloring properties of these geometrically defined graphs.

Sang-il Oum (엄상일), What is an isotropic system?
2021-04-20 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Bouchet introduced isotropic systems in 1983 unifying some combinatorial features of binary matroids and 4-regular graphs. The concept of isotropic system is a useful tool to study vertex-minors of graphs and yet it is not well known. I will give an introduction to isotropic systems.

Reinhard Diestel, Tangles of set separations: a novel clustering method and type recognition in machine learning
2021-04-21 17:00 - 18:00 | Zoom ID: 869 4632 6610 (ibsdimag)
Traditional clustering identifies groups of objects that share certain qualities. Tangles do the converse: they identify groups of qualities that typically occur together. They can thereby discover, relate, and structure types: of behaviour, political views, texts, or proteins. Tangles offer a new, quantitative, paradigm for grouping phenomena rather than things. They can identify key phenomena that allow predictions of others. Tangles also offer a new paradigm for clustering in large data sets.
The mathematical theory of tangles has its origins in the theory of graph minors developed by Robertson and Seymour. It has recently been axiomatized in a way that makes it applicable to a wide range of contexts outside mathematics: from clustering in data science to predicting customer behaviour in economics, from DNA sequencing and drug development to text analysis and machine learning.
This very informal talk will not show you the latest intricacies of abstract tangle theory (for which you can find links on the tangle pages of my website), but to win you over to join our drive to develop real tangle applications in areas as indicated above. We have some software to share, but are looking for people to try it out with us on real-world examples!
Here are some introductory pages from a book I am writing on this, which may serve as an extended abstract: https://arxiv.org/abs/2006.01830

Jungho Ahn (안정호), Well-partitioned chordal graphs with the obstruction set and applications
2021-04-27 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the vertex set into cliques that can be arranged in a star structure, the leaves of which are of size one. Well-partitioned chordal graphs are a generalization of this concept in the following two ways. First, the cliques in the partition can be arranged in a tree structure, and second, each clique is of arbitrary size. We mainly provide a characterization of well-partitioned chordal graphs by forbidden induced subgraphs and give a polynomial-time algorithm that given any graph, either finds an obstruction or outputs a partition of its vertex set that asserts that the graph is well-partitioned chordal. We demonstrate the algorithmic use of this graph class by showing that two variants of the problem of finding pairwise disjoint paths between k given pairs of vertices are in FPT, parameterized by k, on well-partitioned chordal graphs, while on chordal graphs, these problems are only known to be in XP. From the other end, we introduce some problems that are polynomial-time solvable on split graphs but become NP-complete on well-partitioned chordal graphs.
This is joint work with Lars Jaffke, O-joung Kwon, and Paloma T. Lima.

Extremal and Probabilistic Combinatorics (2021 KMS Spring Meeting)
2021-04-30 09:00 - 12:20
A special session “Extremal and Probabilistic Combinatorics” at the 2021 KMS Spring Meeting is organized by Tuan Tran.
URL: https://www.kms.or.kr/meetings/spring2021/
Speakers and Schedule
All talks are on April 30.

[9:00 am] Joonkyung Lee (이준경), University College London

Majority dynamics on sparse random graphs

[9:30 am] Dong Yeap Kang (강동엽), Unversity of Birmingham

The Erdős-Faber-Lovász conjecture and related results

[10:00 am] Jinyoung Park (박진영), IAS

The threshold for the square of a Hamilton cycle

[10:50 am] Debsoumya Chakraborti, IBS Discrete Mathematics Group

Generalized graph saturation

[11:20 am] Jaehoon Kim (김재훈), KAIST

Resolution of the Oberwolfach problem

[11:50 am] Hong Liu, University of Warwick

Sublinear expanders and its applications

Abstracts
Debsoumya Chakraborti, Generalized graph saturation
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 the addition of any edge creates a copy of F. We resolve one of the most fundamental questions of minimizing the number of cliques of size r in a $K_s$-saturated graph for all sufficiently large numbers of vertices, confirming a conjecture of Kritschgau, Methuku, Tait and Timmons. We further prove a corresponding stability result. This talk will be based on joint work with Po-Shen Loh.
Jaehoon Kim (김재훈), Resolution of the Oberwolfach problem
The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of $K_{2n+1}$ into edge-disjoint copies of a given 2-factor. We show that this can be achieved for all large n. We actually prove a significantly more general result, which allows for decompositions into more general types of factors.
Dong Yeap Kang (강동엽), The Erdős-Faber-Lovász conjecture and related results
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.

Joonkyung Lee (이준경), Majority dynamics on sparse random graphs
Majority dynamics on a graph G is a deterministic process such that every vertex updates its {-1,1}-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O’Donnell, Tamuz and Tan conjectured that, in the Erdős-Rényi random graph G(n,p), the random initial {-1,1}-assignment converges to the unanimity with high probability whenever p>> 1/n.
This conjecture was firstly confirmed for $p>Cn^{-1/2}$ for a large constant C>0 by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, none of them managed to extend it beyond the barrier $p>Cn^{-1/2}$. We prove the conjecture for sparser random graphs G(n,p), where $Dn^{-3/5}log n < p < C n^{-1/2}$ with a large constant D>0.
Joint work with Debsoumya Chakraborti, Jeong Han Kim and Tuan Tran.
Hong Liu, Sublinear expanders and its applications
I will review the history of sublinear expander and present some recent applications, which lead to resolutions of several long-standing problems in sparse graphs embeddings.
Jinyoung Park (박진영), The threshold for the square of a Hamilton cycle
We will talk about a recent result of Jeff Kahn, Bhargav Narayanan, and myself stating that the threshold for the random graph G(n,p) to contain the square of a Hamilton cycle is $1/sqrt n$, resolving a conjecture of Kühn and Osthus from 2012. The proof idea is motivated by the recent work of Frankston and the three aforementioned authors on a conjecture of Talagrand — “a fractional version of Kahn-Kalai expectation threshold conjecture.”

Raul Lopes, Adapting the Directed Grid Theorem into an FPT Algorithm
2021-05-06 10:00 - 11:00 | Zoom ID: 869 4632 6610 (ibsdimag)
The Grid Theorem of Robertson and Seymour [JCTB, 1986] is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem in digraphs was conjectured by Johnson et al. [JCTB, 2001] , and proved by Kawarabayashi and Kreutzer [STOC, 2015]. They showed that there is a function f(k) such that every digraph of directed tree-width at least f(k) contains a cylindrical grid of order k as a butterfly minor and stated that their proof can be turned into an XP algorithm, with parameter k, that either constructs a decomposition of the appropriate width, or finds the claimed large cylindrical grid as a butterfly minor.
In this talk, we present the ideas used in our adaptation of the Directed Grid Theorem into an FPT algorithm. We provide two FPT algorithms with parameter k. The first one either produces an arboreal decomposition of width 3k-2 or finds a haven of order k in a digraph D. The second one uses a bramble B that naturally occurs in digraphs of large directed tree-width to find a well-linked set of order k that is contained in the set of vertices of a path hitting all elements of B. As tools to prove these results, we show how to solve a generalized version of the problem of finding balanced separators for a given set of vertices T in FPT time with parameter |T|.
Joint work with Victor Campos, Ana Karolinna Maia, and Ignasi Sau.

Hong Liu, Sublinear expander and embeddings sparse graphs
2021-05-06 16:15 - 17:15 | Zoom
A notion of sublinear expander has played a central role in the resolutions of a couple of long-standing conjectures in embedding problems in graph theory, including e.g. the odd cycle problem of Erdős and Hajnal that the harmonic sum of odd cycle length in a graph diverges with its chromatic number. I will survey some of these developments.

Mark Siggers, The list switch homomorphism problem for signed graphs
2021-05-11 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A signed graph is a graph in which each edge has a positive or negative sign. Calling two graphs switch equivalent if one can get from one to the other by the iteration of the local action of switching all signs on edges incident to a given vertex, we say that there is a switch homomorphism from a signed graph $G$ to a signed graph $H$ if there is a sign preserving homomorphism from $G’$ to $H$ for some graph $G’$ that is switch equivalent to $G$. By reductions to CSP this problem, and its list version, are known to be either polynomial time solvable or NP-complete, depending on $H$. Recently those signed graphs $H$ for which the switch homomorphism problem is in $P$ were characterised. Such a characterisation is yet unknown for the list version of the problem.
We talk about recent work towards such a characterisation and about how these problems fit in with bigger questions that still remain around the recent CSP dichotomy theorem.

Johannes Carmesin, A Whitney type theorem for surfaces: characterising graphs with locally planar embeddings
2021-05-12 17:00 - 18:00 | Zoom ID: 869 4632 6610 (ibsdimag)
Given a graph, how do we construct a surface so that the graph embeds in that surface in an optimal way? Thomassen showed that for minimum genus as optimality criterion, this problem would be NP-hard. Instead of minimum genus, here we use local planarity — and provide a polynomial algorithm.
Our embedding method is based on Whitney’s trick to use matroids to construct embeddings in the plane. Consequently we obtain a characterisation of the graphs admitting locally planar embeddings in surfaces in terms of a certain matroid being co-graphic.

Pascal Gollin, Enlarging vertex-flames in countable digraphs
2021-05-18 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A rooted digraph is a vertex-flame if for every vertex v there is a set of internally disjoint directed paths from the root to v whose set of terminal edges covers all ingoing edges of v. It was shown by Lovász that every finite rooted digraph admits a spanning subdigraph which is a vertex-flame and large, where the latter means that it preserves the local connectivity to each vertex from the root. A structural generalisation of vertex-flames and largeness to infinite digraphs was given by Joó and the analogue of Lovász’ result for countable digraphs was shown.
In this talk, I present a strengthening of this result stating that in every countable rooted digraph each vertex-flame can be extended to a large vertex-flame.
Joint work with Joshua Erde and Attila Joó.

Benjamin Bumpus, Directed branch-width: A directed analogue of tree-width
2021-05-21 17:00 - 18:00 | Zoom ID: 869 4632 6610 (ibsdimag)
Many problems that are NP-hard in general become tractable on `structurally recursive’ graph classes. For example, consider classes of bounded tree- or clique-width. Since the 1990s, many directed analogues of tree-width have been proposed. However, many natural problems (e.g. directed HamiltonPath and MaxCut) remain intractable on such digraph classes of `bounded width’.
In this talk, I will introduce a new tree-width analogue for digraphs called directed branch-width which allows us to define digraph classes for which many problems (including directed HamiltonPath and MaxCut) become linear-time solvable. Furthermore, via the definition of directed branch-width, I will obtain a generalisation to digraphs of Gurski and Wanke’s characterization of graph classes of bounded tree-width in terms of their line graphs.
This is joint work with Kitty Meeks and William Pettersson.
