Tuan Tran

collaborators

2 papers

math.CO2024

Graph with any rational density and no rich subsets of linear size

Seonghyuk Im, Suyun Jiang, Hong Liu +1

A well-known application of the dependent random choice asserts that any $n$ -vertex graph $G$ with positive edge density contains a `rich' vertex subset $U$ of size $n^{1 - o (1)}$ su…

math.CO2024

Approximate packing of independent transversals in locally sparse graphs

Debsoumya Chakraborti, Tuan Tran

Fix $ε > 0$ and consider a multipartite graph $G$ with maximum degree at most $(1 - ε) n$ , parts $V_{1}, \dots, V_{k}$ of the same size $n$ , and where every vertex has a…