2019 IBS Summer Research Program on Algorithms and Complexity in Discrete Structures
2019-07-21 - 2019-08-10 | Room B232, IBS (기초과학연구원)
Schedule
July 22 Monday
10:00-11:00 Introduction, 11:00-12:00 Open Problems
July 23 Tuesday
10:00-10:30 Stefan Kratsch, Humboldt-Universität zu Berlin, Germany
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
10:45-11:15 Benjamin Bergougnoux, University Clermont Auvergne, France
More applications of the d-neighbor equivalence
11:30-12:00 Yixin Cao, Hong Kong Polytechnic University, China
Enumerating Maximal Induced Subgraphs
13:30-14:30 Open Problems
July 24 Wednesday
We will go to KAIST for June Huh‘s two talks 15:00-16:00, 16:30-17:30. A IBS shuttle bus @14:30 from the lobby.
July 25 Thursday
10:00-11:00 Nick Brettell, Durham University, UK
Recent work on characterising matroids representable over finite fields
11:30-12:00 Mamadou M. Kanté, University Clermont Auvergne, France
On recognising k-letter graphs
July 26 Friday
10:00-11:00 O-joung Kwon (권오정), Incheon National University, Korea
The grid theorem for vertex-minors
11:00-12:00 Progress Report
July 27 Saturday
8:30 Excursion to Damyang (departure from the accommodation)
July 29 Monday
10:00-11:00 Archontia Giannopoulou, National and Kapodistrian University of Athens, Greece
The directed flat wall theorem
11:30-12:00 Eunjung Kim (김은정), LAMSADE-CNRS, France
Subcubic even-hole-free graphs have a constant treewidth
July 30 Tuesday
10:00-11:00 Pierre Aboulker, ENS Ulm, France
Generalizations of the geometric de Bruijn Erdős Theorem
11:30-12:00 Michael Dobbins, Binghamton University, USA
Barycenters of points in polytope skeleta
July 31 Wednesday
10:00-11:00 Magnus Wahlström, Royal Holloway, University of London, UK
FPT-algorithms via LP-relaxations
11:30-12:00 Édouard Bonnet, ENS Lyon, France
The FPT/W[1]-hard dichotomy of Max Independent Set in H-free graphs
August 1 Thursday
10:00-11:00 Euiwoong Lee (이의웅), NYU, USA
Losing treewidth by separating subsets
11:30-12:00 Sang-il Oum (엄상일), IBS Discrete Mathematics Group and KAIST, Korea
Branch-depth: Generalizing tree-depth of graphs
August 2 Friday
10:00-11:00 Dabeen Lee (이다빈), IBS Discrete Mathematics Group, Korea
t-perfect graphs and the stable set problem
11:00-12:00 Progress Report
August 5-9: Free Discussions / Research Collaborations / Progress Report
Tea time: Every weekday 3:30pm
Abstracts
July 23 Tuesday
Stefan Kratsch, Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
The Vertex Cover problem plays an essential role in the study of polynomial kernelization in parameterized complexity, i.e., the study of provable and efficient preprocessing for NP-hard problems. Motivated by the great variety of positive and negative results for kernelization for Vertex Cover subject to different parameters and graph classes, we seek to unify and generalize them using so-called blocking sets, which have played implicit and explicit roles in many results. We show that in the most-studied setting, parameterized by the size of a deletion set to a specified graph class ${cal C}$, bounded minimal blocking set size is necessary but not sufficient to get a polynomial kernelization. Under mild technical assumptions, bounded minimal blocking set size is showed to allow an essentially tight efficient reduction in the number of connected components. We then determine the exact maximum size of minimal blocking sets for graphs of bounded elimination distance to any hereditary class ${cal C}$, including the case of graphs of bounded treedepth. We get similar but not tight bounds for certain non-hereditary classes ${cal C}$, including the class ${cal C}_{LP}$ of graphs where integral and fractional vertex cover size coincide. These bounds allow us to derive polynomial kernels for Vertex Cover parameterized by the size of a deletion set to graphs of bounded elimination distance to, e.g., forest, bipartite, or ${cal C}_{LP}$ graphs.
Benjamin Bergougnoux, More applications of the d-neighbor equivalence
In this talk, I will present a framework which gives efficient algorithms for several connectivity problems such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. For all these problems, we obtain efficient algorithms parameterized respectively by tree-width, clique-width, Q-rank-width, rank-width and maximum induced matching width. Our approach simplifies and unifies the known algorithms for each of the parameters and match asymptotically also the running time of the best algorithms for Vertex Cover and Dominating Set. Our framework is based on the d-neighbor equivalence defined in [Bui-Xuan, Telle and Vatshelle, TCS 2013]. The results we obtain highlight the importance and the generalizing power of this equivalence relation on width measures. We also prove that this equivalence relation could be useful for Max Cut: a W[1]-hard problem parameterized by clique-width.
Paper available on HAL : https://hal.archives-ouvertes.fr/hal-01799573
Yixin Cao, Enumerating Maximal Induced Subgraphs
We study efficient algorithms for the maximal induced subgraphs problem: Given a graph on $n$ vertices, enumerate all its maximal induced subgraphs that belong to a particular hereditary graph class. While its optimization version, known as the vertex deletion problem in literature, has been intensively studied, algorithms for the enumeration version exist only for few simple graph classes, e.g., independent sets and cliques. Enumeration algorithms are mainly categorized in three complexity classes, polynomial total time (polynomial on $n$ and the total number of solutions), incremental polynomial time (for all $s$, the time to output the first $s$ solutions is polynomial on $n$ and $s$), and polynomial delay (for all $s$, the time to output the first $s$ solutions is polynomial on $n$ and linear on $s$). We first show that the maximal induced subgraphs problem can be solved in polynomial total time if and only if it can be solved in incremental polynomial time. We then propose general approaches to develop polynomial-delay algorithms and incremental-polynomial-time algorithms for the problem. They enable us to develop simple algorithms to solve the problem with polynomial delay for a large number of graph classes, and in incremental polynomial time for interval graphs, chordal graphs as well as two of its well-studied subclasses, and all graph classes with finite forbidden induced subgraphs.
July 25 Thursday
Nick Brettell, Recent work on characterising matroids representable over finite fields
Characterising when a matroid is representable over a certain field or set of fields is one of the oldest problems in matroid theory, dating back to Whitney’s 1935 paper. In this talk, I will discuss some of the more recent work in this area, with a focus on work I have been involved with towards characterising matroids representable over all fields of size at least four.
Mamadou M. Kanté, On recognising k-letter graphs
$k$-letter graphs are a subclass of graphs of linear clique-width $k$, but are well-quasi-ordered by the induced subgraph ordering. I present a simple FPT algorithm for recognising $k$-letter graphs and also an upper bound on the size of minimal obstructions. The characterisation is based on a simple observation allowing an MSOL-definability. (joint work with V. Lozin)
July 26 Friday
O-joung Kwon (권오정), The grid theorem for vertex-minors
We prove that, for a circle graph $H$, every graph with sufficiently large rank-width contains a vertex-minor isomorphic to $H$. This is joint work with Jim Geelen, Rose McCarty, and Paul Wollan.
July 29 Monday
Archontia Giannopoulou, The directed flat wall theorem
At the core of the Robertson-Seymour theory of Graph Minors lies a powerful structure theorem which captures, for any fixed graph $H$, the common structural features of all the graphs not containing $H$ as a minor [Neil Robertson, Paul D. Seymour: Graph Minors. XVI. Excluding a non-planar graph. J. Comb. Theory, Ser. B 89(1): 43-76 (2003)]. An important step towards this structure theorem is the Flat Wall Theorem [Neil Robertson, Paul D. Seymour: Graph Minors .XIII. The Disjoint Paths Problem. J. Comb. Theory, Ser. B 63(1): 65-110 (1995)], which has a lot of algorithmic applications (for example, the minor-testing and the disjoint paths problem with fixed number terminals).
In this paper, we prove the directed analogue of this Flat Wall Theorem. Our result builds on the recent Directed Grid Theorem by two of the authors (Kawarabayashi and Kreutzer), and we hope that this is an important and significant step toward the directed structure theorem, as with the case for the undirected graph for the graph minor project.
Joint work with Ken-ichi Kawarabayashi, Stephan Kreutzer, and O-joung Kwon.
Eunjung Kim (김은정), Subcubic even-hole-free graphs have a constant treewidth
It is known that even-hole-free graphs can have arbitrarily large rankwidth, but all known constructions have many high-degree vertices. It has been believed in the structural graph theory community that the rankwidth shall be bounded if the maximum degree is bounded. We prove that there exists a universal constant $c$ such that every even-hole-free graph of degree at most three has treewidth at most $c$. As a by-product of the proof, we also show that there exists a function $f$ such that for any $r$, $K_r$-minor-free and even-hole-free graph has treewidth at most $f(r)$; this extends the result of Silva et. al. (Discrete Applied Mathematics 2010) addressing the case of planar graphs.
This is a joint work with Pierre Aboulker and Isolde Adler.
July 30 Tuesday
Pierre Aboulker, Generalizations of the geometric de Bruijn Erdős Theorem
A classic Theorem of de Bruijn and Erdős states that every noncollinear set of n points in the plane determines at least n distinct lines. The line $L(u,v)$ determined by two points $u$, $v$ in the plane consists of all points $p$ such that

$operatorname{dist}(p, u)+operatorname{dist}(u, v)=operatorname{dist}(p, v)$ (i.e. $u$ is between $p$ and $v$) or
$operatorname{dist}(u, p)+operatorname{dist}(p, v)=operatorname{dist}(u, v)$ (i.e. $p$ is between $u$ and $v$) or
$operatorname{dist}(u, v)+operatorname{dist}(v, p)=operatorname{dist}(u, p)$ (i.e. $v$ is between $u$ and $p$).

With this definition of line $L(uv)$ in an arbitrary metric space $(V, operatorname{dist})$, Chen and Chvátal conjectured that every metric space on n points, where n is at least 2, has at least n distinct lines or a line that consists of all n points. The talk will survey results on and around this conjecture.
Michael Dobbins, Barycenters of points in polytope skeleta
In this talk I will classify the n-tuples of dimensions such that any target point in any d-polytope is the barycenter of points in faces of the prescribed dimensions. Specifically, for a $(nk+r)$-polytope and target point, we can always find $r$ points in faces of dimension $k+1$, and $n-r$ points in faces of dimension $k$, that have their barycenter at the given target. This is tight in the sense that we cannot require even one of the points to be in a face of dimension less than $k$, and we cannot require more than $n-r$ of the points to be in faces of dimension $k$. This is joint work with Florian Frick.
July 31 Wednesday
Magnus Wahlström, FPT-algorithms via LP-relaxations
LP-relaxations are traditionally (within theoretical computer science) used for computing approximate solutions to NP-hard problems, but across the last few years there have been several examples where LP-relaxations have been used to guide FPT-algorithms — that is, exact (non-approximate) algorithms whose running time is bounded in terms of a “parameter” of the input instance. This approach has given algorithms that are simultaneously simpler and faster for a range of central problems in parameterized complexity. At the same time, this is applicable only to specific problems and relaxations; an arbitrary LP-relaxation, even one that has good properties in an approximation sense, will in general give no useful guidance with respect to exact solutions.
In this talk, we give an overview of these FPT applications, and the conditions they impose on the LP-relaxation. Our main focus is on an approach of “discrete relaxation” referred to as Valued CSPs, but we also briefly survey more immediately combinatorial conditions, as well as related algorithms that solve these problems more efficiently (e.g., so-called linear-time FPT algorithms) by bypassing the LP-solver.
Édouard Bonnet, The FPT/W[1]-hard dichotomy of Max Independent Set in H-free graphs
Maximum Independent Set (MIS) is in general graphs the paradigmatic W[1]-hard problem. In stark contrast, polynomial-time algorithms are known when the inputs are restricted to structured graph classes such as, for instance, perfect graphs (which includes bipartite graphs, chordal graphs, co-graphs, etc.) or claw-free graphs. In this talk, we introduce some variants of co-graphs with “parameterized noise”, that is, graphs that can be turned into disjoint unions or complete sums by the removal of a certain number of vertices and the edition of a certain number of edges per incident vertex, both controlled by the parameter. We give a series of FPT Turing-reductions on these classes and use them to make some progress on the parameterized complexity of MIS in $H$-free graphs. We present the current state of the (randomized) FPT vs W[1]-hard dichotomy of MIS in $H$-free graphs. We then show that for every fixed $t geq 1$, MIS is FPT in $P(1,t,t,t)$-free graphs, where $P(1,t,t,t)$ is the graph obtained by substituting all the vertices of a four-vertex path but one end of the path by cliques of size t. In particular, this helped finishing the classification when H has at most five vertices.
This follows joint works with Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant.
August 1 Thursday
Euiwoong Lee (이의웅), Losing treewidth by separating subsets
We study the problem of deleting the smallest set S of vertices (resp. edges) from a given graph $G$ such that the induced subgraph (resp. subgraph) $G setminus S$ belongs to some class of graphs $H$. When graphs in H have treewidth bounded by $t$, we construct a framework for both vertex and edge deletion versions where approximation algorithms for these problems can be obtained from approximation algorithms for natural graph partitioning problems called $k$-Subset Vertex Separator and $k$-Subset Edge Separator.
For the vertex deletion, our framework, combined with the previous best result for $k$-Subset Vertex Separator, yields improved approximation ratios for fundamental problems such as $k$-Treewidth Vertex Deletion and Planar-$F$ Vertex Deletion. For the edge deletion, we give improved approximation algorithms for $k$-Subset Edge Separator and their applications to various problems in bounded-degree graphs.
Joint work with Anupam Gupta, Jason Li, Pasin Manurangsi, and Michal Wlodarczyk.
Sang-il Oum (엄상일), Branch-depth: Generalizing tree-depth of graphs
We present a concept called the branch-depth of a connectivity function, that generalizes the tree-depth of graphs. Then we prove two theorems showing that this concept aligns closely with the notions of tree-depth and shrub-depth of graphs as follows. For a graph $G = (V,E)$ and a subset $A $ of $E$ we let $lambda_G (A)$ be the number of vertices incident with an edge in $A$ and an edge in $E setminus A$. For a subset $X$ of $V$, let $rho_G(X)$ be the rank of the adjacency matrix between $X$ and $V setminus X$ over the binary field. We prove that a class of graphs has bounded tree-depth if and only if the corresponding class of functions $lambda_G$ has bounded branch-depth and similarly a class of graphs has bounded shrub-depth if and only if the corresponding class of functions $rho_G$ has bounded branch-depth, which we call the rank-depth of graphs.
Furthermore we investigate various potential generalizations of tree-depth to matroids and prove that matroids representable over a fixed finite field having no large circuits are well-quasi-ordered by the restriction.
This is a joint work with Matt DeVos and O-joung Kwon.
August 2 Friday
Dabeen Lee (이다빈), t-perfect graphs and the stable set problem
A graph $G$ is called $t$-perfect if the stable set polytope of $G$ can be obtained after adding the odd cycle inequalities to the standard edge formulation for the problem. A motivation for studying $t$-perfect graphs is algorithmic: as the odd cycle inequalities can be separated in polynomial time, one can compute a maximum weight stable set in a $t$-perfect graph by an LP algorithm in polynomial time. There are rich classes of $t$-perfect graphs, but a complete characterization of $t$-perfect graphs is still open. Due to this, no graph-theoretic / combinatorial algorithm is known, although there is an algorithm for the unweighted case based on a combinatorial approximate LP algorithm. In this survey talk, I will (i) review classes of known $t$-perfect graphs, (ii) briefly explain the algorithm for the unweighted case and a possibility of extending it to the weighted case, and (iii) discuss some research directions towards finding a graph-theoretic algorithm for computing a maximum weight stable set in a $t$-perfect graph.
Participants (not including IBS researchers)

Pierre Aboulker, ENS Ulm, France
Rémy Belmonte, University of Electro-Communications, Japan
Benjamin Bergougnoux, University of Paris Diderot, France
Édouard Bonnet, ENS Lyon, France
Nick Brettell, Durham University, UK
Yixin Cao, Hong Kong Polytechnic University, China
Michael Dobbins, Binghamton University, USA
Chris Eppolito, Binghamton University, USA
Archontia Giannopoulou, National and Kapodistrian University of Athens, Greece
Mamadou M. Kante, University Clermont Auvergne, France
Eunjung Kim (김은정), LAMSADE-CNRS, France
Stefan Kratsch, Humboldt-Universität zu Berlin, Germany
O-joung Kwon (권오정), Incheon National University, Korea
Michael Lampis, Université Paris-Dauphine, France
Euiwoong Lee (이의웅), NYU, USA
Valia Mitsou, Université Paris-Diderot, France
Florian Sikora, University Paris Dauphine, France
Magnus Wahlström, Royal Holloway, University of London, UK

An invitation-only summer research program will be held in the summer of 2019. There will be 10-20 participants to work together at DIMAG. Talks are open.
Accommodation
Everyone will stay at the Daedeok Innopolis Guest House (대덕특구게스트하우스).

Address: 27-5, Expo-ro 123beon-gil, Yuseong-gu, Daejeon, 34125, Republic of Korea (대전광역시 유성구 엑스포로 123번길 27-5)
Tel: (+82)-042-865-2500

Organizers

Eunjung Kim (김은정), LAMSADE-CNRS, France
Sang-il Oum (엄상일), IBS Discrete Mathematics Group and KAIST, Korea

2019-2 IBS One-Day Conference on Extremal Graph Theory
2019-08-12 11:00 - 20:00 (Asia/Seoul) | Room B232, IBS (기초과학연구원)
Invited Speakers

Jaehoon Kim (김재훈), KAIST
Hong Liu (刘鸿), University of Warwick
Abhishek Methuku, IBS Discrete Mathematics Group
Péter Pál Pach, Budapest University of Technology and Economics

Schedule
August 12, Monday
11:00am-12:00pm Jaehoon Kim (김재훈): Tree decompositions of graphs without large bipartite holes
12:00pm-1:30pm Lunch
1:30pm-2:30pm Abhishek Methuku: Bipartite Turán problems for ordered graphs
3:00pm-4:00pm Péter Pál Pach: On some applications of graph theory to number theoretic problems
4:30pm-5:30pm Hong Liu: Recent advance in Ramsey-Turán theory
6:00pm-8:00pm Banquet
Abstract
Jaehoon Kim (김재훈), Tree decompositions of graphs without large bipartite holes
A recent result of Condon, Kim, Kühn and Osthus implies that for any $rgeq (frac{1}{2}+o(1))n$, an $n$-vertex almost $r$-regular graph $G$ has an approximate decomposition into any collections of $n$-vertex bounded degree trees. In this talk, we prove that a similar result holds for an almost $alpha n$-regular graph $G$ with any $alpha>0$ and a collection of bounded degree trees on at most $(1-o(1))n$ vertices if $G$ does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into $n$-vertex trees. This is joint work with Younjin Kim and Hong Liu.
Abhishek Methuku, Bipartite Turán problems for ordered graphs
A zero-one matrix $M$ contains a zero-one matrix $A$ if one can delete rows and columns of $M$, and turn 1-entries into 0-entries such that the resulting matrix is $A$. The extremal number of $A$, denoted by $ex(n,A)$, is the maximum number of $1$-entries in an $ntimes n$ sized matrix $M$ that does not contain $A$.
A matrix $A$ is column-$t$-partite (or row-$t$-partite), if it can be cut along the columns (or rows) into $t$ submatrices such that every row (or column) of these submatrices contains at most one $1$-entry. We prove that if $A$ is column-$t$-partite, then $operatorname{ex}(n,A)<n^{2-frac{1}{t}+frac{1}{2t^{2}}+o(1)}$, and if $A$ is both column- and row-$t$-partite, then $operatorname{ex}(n,A)<n^{2-frac{1}{t}+o(1)}$, and this bound is close to being optimal. Our proof introduces a new density-increment-type argument which is combined with the celebrated dependent random choice method.
Results about the extremal numbers of zero-one matrices translate into results about the Turán numbers of bipartite ordered graphs. In particular, a zero-one matrix with at most $t$ 1-entries in each row corresponds to an ordered graph with maximum degree $t$ in one of its vertex classes. The aim of this talk is to establish general results about the extremal numbers of ordered graphs. Our results are partially motivated by a well known result of Füredi (1991) and Alon, Krivelevich, Sudakov (2003) stating that if $H$ is a bipartite graph with maximum degree $t$ in one of the vertex classes, then $operatorname{ex}(n,H)=O(n^{2-frac{1}{t}})$. This is joint work with Tomon.
Péter Pál Pach, On some applications of graph theory to number theoretic problems
How large can a set of integers be, if the equation $a_1a_2dots a_h=b_1b_2dots b_h$ has no solution consisting of distinct elements of this set? How large can a set of integers be, if none of them divides the product of $h$ others? How small can a multiplicative basis for ${1, 2, dots, n}$ be? The first question is about a generalization of the multiplicative Sidon sets, the second one is of the primitive sets, while the third one is the multiplicative version of the well-studied analogue problem for additive bases.
In answering the above mentioned questions graph theory plays an important role and in most of our results not only the asymptotics are found, but very tight bounds are obtained for the error terms, as well. We will also discuss the counting version of these questions.
Hong Liu, Recent advance in Ramsey-Turán theory
We will talk about Ramsey-Turán theory and some recent development. More specifically, we will talk about graphs with $alpha_r(G)=o(n)$, where $alpha_r(G)$ is the largest size subset with no $K_r$. Two major open problems in this area from the 80s ask: (1) whether Bollobas-Erdos graph can be generalised to densities other than $1/2$; (2) whether the asymptotic extremal structure for $alpha_r(G)$ resembles that of $alpha_2(G)$. We settle the first conjecture by constructing Bollobas-Erdos type graph with density $a$ for arbitrary rational number $ale 1/2$; and refute the second conjecture by witnessing asymptotic extremal structures that are drastically different from the $alpha_2(G)$ problem via a ”Mobius product” construction.
Joint work with Christian Reiher, Maryam Sharifzadeh, and Katherine Staden.

2019 Combinatorics Workshop
2019-08-13 - 2019-08-15 | Hotel Skypark, Songdo, Incheon, Korea (송도 스카이파크호텔)
The annual conference on Combinatorics Workshop (조합론 학술대회) began in 2004 by the Yonsei University BK21 Research Group. This year it will take place in Songdo, Incheon, August 13-15, 2019.

Due to the capacity (50 persons) of the place, we are able to limit your registration. In principle, registration is on a first-come, first-served basis.

Title 2019 Combinatorics Workshop (2019 조합론 학술대회)
Date August 13-15 (Tue-Thu), 2019
Venue Hotel Skypark, Songdo, Incheon
Web https://cw2019.combinatorics.kr

We are going to

give six 50-minute talks and ten 25-minute talks in Korean.
distribute the program and abstracts of CW2019.
provide for the accommodations for all participants.
provide for six meals (two breakfasts, two luncheons, one dinner, and one banquet) for all participants.

Plenary Speaker

Mihyun Kang, Graz University of Technology

Keynote Speakers

Jaehoon Kim, KAIST
Seung Jin Lee, Seoul National University
Meesue Yoo, Dankook University

Invited Speakers

Eun-Kyung Cho, Hankuk University of Foreign Studies
Soogang Eoh, Seoul National University
JiSun Huh, Sungkyunkwan University
Jihyeug Jang, Sungkyunkwan University
Dong Yeap Kang, KAIST and IBS Discrete Mathematics Group
Min Jeong Kang, Incheon National University
Dabeen Lee, IBS Discrete Mathematics Group
Kang-Ju Lee, Seoul National University
Myeonghwan Lee, Incheon National University
Jihye Park, Yeungnam University
Sun-mi Yun, Sungkyunkwan University

Organizing Committee

O-joung Kwon, Incheon National University and IBS Discrete Mathematics Group
Suil O, SUNY Korea
Sang-il Oum, IBS Discrete Mathematics Group and KAIST
Heesung Shin, Inha University

Advisory Committee

Committee of Discrete Mathematics, The Korean Mathematical Society (Chair: Seog-Jin Kim, Konkuk University)

Sponsors

IBS Discrete Mathematics Group
NRF (National Research Foundation of Korea)

Mihyun Kang (강미현), The genus of a random graph and the fragile genus property
2019-08-20 16:30 - 17:30 | 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)
