기초과학연구원 이산수학그룹
One interesting difference between (nondegenerate) Graph Turán problem and Hypergraph Turán problem is that the hypergraph families can have at least two very different extremal constructions. In this talk, we will look at some recent progress and approaches to constructing hypergraph families with at least two different extremal constructions. Based on some joint work with …
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 …
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 …
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 …
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 …
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 …
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 …
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 …
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 …
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$ …