기초과학연구원 이산수학그룹
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 $n\to \infty$? I will answer this question for a variety of sparse graph classes $\mathcal{G}$. In particular, we show that the answer is …
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$, …
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 …
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 …
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 …
Corneil, Olariu, and Stewart presented a recognition algorithm for interval graphs by six graph searches. Li and Wu 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 …
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 …
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 …
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.
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 …