기초과학연구원 이산수학그룹
We will discuss classical and recent results about phase transitions in random subgraphs of the hypercube and beyond. The focus will be on the giant component, long cycles, large matchings, and isoperimetric properties.
A local certification of a graph property is a protocol in which nodes are given “certificates of a graph property” that allow the nodes to check whether their network has this property while only communicating with their local network. The key property of a local certification is that if certificates are corrupted, some node in the …
This talk is an introduction to the recent notion of merge-width, proposed by Jan Dreier and Szymon Torúnczyk. I will give an overview of the context and motivations for merge-width, namely the first-order model checking problem, and present the definition, some examples, and some basic proof techniques with the example of χ-boundedness. This is based …
We formulate a geometric version of the Erdős-Hajnal conjecture that applies to finite projective geometries rather than graphs. In fact, we give a natural extension of the 'multicoloured' version of the Erdős-Hajnal conjecture. Roughly, our conjecture states that every colouring of the points of a finite projective geometry of dimension $n$ not containing a fixed …
The matroid intersection problem is a fundamental problem in combinatorial optimization. In this problem we are given two matroids and the goal is to find the largest common independent set in both matroids. This problem was introduced and solved by Edmonds in the 70s. The importance of matroid intersection stems from the large variety of …
We prove that for any circle graph $H$ with at least one edge and for any positive integer $k$, there exists an integer $t=t(k,H)$ so that every graph $G$ either has a vertex-minor isomorphic to the disjoint union of $k$ copies of $H$, or has a $t$-perturbation with no vertex-minor isomorphic to $H$. Using the …
Lehel's conjecture states that every 2-edge-colouring of the complete graph $K_n$ admits a partition of its vertices into two monochromatic cycles. This was proven for sufficiently large n by Luczak, Rödl, and Szemerédi (1998), extended by Allen (2008), and fully resolved by Bessy and Thomassé in 2010. We consider a rainbow version of Lehel's conjecture …
We will discuss two symmetry breaking parameters: distinguishing number and fixing number. Despite being introduced independently, they share meaningful connections. In particular, we show that if a tree is 2-distinguishable with order at least 3, it suffices to fix at most 4/11 of the vertices and if a tree is $d$-distinguishable, $d \geq 3$, it …
We prove that for all positive integers $k$ and $d$, the class of $K_{1,d}$-free graphs not containing the $k$-ladder or the $k$-wheel as an induced minor has a bounded tree-independence number. Our proof uses a generalization of the concept of brambles to tree-independence number. This is based on joint work with Claire Hilaire, Martin Milanič, …
Nowhere-zero flows of unsigned graphs were introduced by Tutte in 1954 as a dual problem to vertex-coloring of (unsigned) planar graphs. The definition of nowhere-zero flows on signed graphs naturally comes from the study of embeddings of graphs in non-orientable surfaces, where nowhere-zero flows emerge as the dual notion to local tensions. Nowhere-zero flows in …