Sepehr Hajebi, Holes, hubs and bounded treewidth

Zoom ID: 869 4632 6610 (ibsdimag)

A hole in a graph $G$ is an induced cycle of length at least four, and for every hole $H$ in $G$, a vertex $h\in G\setminus H$ is called a $t$-hub for $H$ if $h$ has at least $t$ neighbor in $H$. Sintiari and Trotignon were the first to construct graphs with arbitrarily large treewidth

Noam Lifshitz, Product free sets in the alternating group

Zoom ID: 870 0312 9412 (ibsecopro)

A subset of a group is said to be product free if it does not contain the product of two elements in it. We consider how large can a product free subset of $A_n$ be? In the talk we will completely solve the problem by determining the largest product free subset of $A_n$. Our proof

Lars Jaffke, Taming graphs with no large creatures and skinny ladders

Zoom ID: 869 4632 6610 (ibsdimag)

We confirm a conjecture of Gartland and Lokshtanov : if for a hereditary graph class $\mathcal{G}$ there exists a constant $k$ such that no member of $\mathcal{G}$ contains a $k$-creature as an induced subgraph or a $k$-skinny-ladder as an induced minor, then there exists a polynomial $p$ such that every $G \in \mathcal{G}$ contains at

Akash Kumar, Random walks and Forbidden Minors

Zoom ID: 870 0312 9412 (ibsecopro)

Random walks and spectral methods have had a strong influence on modern graph algorithms as evidenced by the extensive literature on the subject. In this talk, I will present how random walks helped make progress on algorithmic problems on planar graphs. In particular, I show how random walk based (i.e., spectral) approaches led to progress

Brett Leroux, Expansion of random 0/1 polytopes

Zoom ID: 870 0312 9412 (ibsecopro)

A conjecture of Milena Mihail and Umesh Vazirani states that the edge expansion of the graph of every $0/1$ polytope is at least one. Any lower bound on the edge expansion gives an upper bound for the mixing time of a random walk on the graph of the polytope. Such random walks are important because they can be used

Raphael Steiner, Congruence-constrained subdivisions in digraphs

Zoom ID: 869 4632 6610 (ibsdimag)

I will present the short proof from that for every digraph F and every assignment of pairs of integers $(r_e,q_e)_{e\in A(F)}$ to its arcs, there exists an integer $N$ such that every digraph D with dichromatic number at least $N$ contains a subdivision of $F$ in which $e$ is subdivided into a directed path of

Dömötör Pálvölgyi, C-P3O: Orientation of convex sets and other good covers

Zoom ID: 870 0312 9412 (ibsecopro)

We introduce a novel definition of orientation on the triples of a family of pairwise intersecting planar convex sets and study its properties. In particular, we compare it to other systems of orientations on triples that satisfy a natural interiority condition. Such systems, P3O (partial 3-order), are a natural generalization of posets, and include the

Mehtaab Sawhney, Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture

Zoom ID: 870 0312 9412 (ibsecopro)

An $n$-vertex graph is called $C$-Ramsey if it has no clique or independent set of size $C\log_2 n$ (i.e., if it has near-optimal Ramsey behavior). We study edge-statistics in Ramsey graphs, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a $C$-Ramsey graph. One

Santiago Guzmán-Pro, Local expressions of graphs classes

Zoom ID: 869 4632 6610 (ibsdimag)

A common technique to characterize hereditary graph classes is to exhibit their minimal obstructions. Sometimes, the set of minimal obstructions might be infinite, or too complicated to describe. For instance, for any $k\ge 3$, the set of minimal obstructions of the class of $k$-colourable graphs is yet unknown. Nonetheless, the Roy-Gallai-Hasse-Vitaver Theorem asserts that a graph $G$

Konstantin Tikhomirov, A remark on the Ramsey number of the hypercube

Zoom ID: 870 0312 9412 (ibsecopro)

A well-known conjecture of Burr and Erdős asserts that the Ramsey number $r(Q_n)$ of the hypercube $Q_n$ on $2^n$ vertices is of the order $O(2^n)$. In this paper, we show that $r(Q_n)=O(2^{2n−cn})$ for a universal constant $c>0$, improving upon the previous best-known bound $r(Q_n)=O(2^{2n})$, due to Conlon, Fox, and Sudakov.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.