Andrew Suk

Andrew Suk

Auto-generated profile, based on publicly available information

Andrew Suk

Department of Mathematics University of California at San Diego La Jolla 92093 CA USA

Research Focus & Metrics

Academic Career Length

10Years (2017-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
19 November 2018 in Discrete & Computational Geometry
Verified
Journal Article
Open access
PDF file
JFJacob Fox
Jacob Fox
JPJános Pach
János Pach
ASAndrew Suk
Andrew Suk
The Vapnik–Chervonenkis dimension (in short, VC-dimension) of a graph is defined as the VC-dimension of the set system induced by the neighborhoods of its vertices. We show that every n-vertex graph with bounded VC-dimension contains a clique or an independent set of size at least \(e^{(\log n)^{1 - o(1)}}\). The dependence on the VC-dimension is hidden in the o(1) term. This improves the general lower bound, \(e^{c\sqrt{\log n}}\), due to Erdős and Hajnal, which is valid in the class of graphs satisfying any fixed nontrivial hereditary property. Our result is almost optimal and nearly matches the celebrated Erdős–Hajnal conjecture, according to which one can always find a clique or an independent set of size at least \(e^{\Omega (\log n)}\). Our results partially explain why most geometric intersection graphs arising in discrete and computational geometry have exceptionally favorable Ramsey-type properties. Our main tool is a partitioning result found by Lovász–Szegedy and Alon–Fischer–Newman, which is called the “ultra-strong regularity lemma” for graphs with bounded VC-dimension. We extend this lemma to k-uniform hypergraphs, and prove that the number of parts in the partition can be taken to be \((1/\varepsilon )^{O(d)}\), improving the original bound of \((1/\varepsilon )^{O(d^2)}\) in the graph setting. We show that this bound is tight up to an absolute constant factor in the exponent. Moreover, we give an \(O(n^k)\)-time algorithm for finding a partition meeting the requirements. Finally, we establish tight bounds on Ramsey–Turán numbers for graphs with bounded VC-dimension.

22 November 2020
Verified
Book Chapter
Closed access
PDF file
DMDhruv Mubayi
Dhruv Mubayi
ASAndrew Suk
Andrew Suk

27 December 2017 in Bulletin of the London Mathematical Society
Verified
Journal Article
Closed access
PDF file
DMDhruv Mubayi
Dhruv Mubayi
ASAndrew Suk
Andrew Suk

15 April 2024 in Studia Scientiarum Mathematicarum Hungarica
Verified
Journal Article
Closed access
PDF file
DCDavid Conlon
David Conlon
JFJacob Fox
Jacob Fox
XHXiaoyu He
Xiaoyu He
DMDhruv Mubayi
Dhruv Mubayi
ASAndrew Suk
Andrew Suk
JVJacques Verstraëte
Jacques Verstraëte
For positive integers 𝑛, 𝑟, 𝑠 with 𝑟 > 𝑠, the set-coloring Ramsey number 𝑅(𝑛; 𝑟, 𝑠) is the minimum 𝑁 such that if every edge of the complete graph 𝐾

15 January 2021 in Bulletin of the London Mathematical Society
Verified
Journal Article
Closed access
PDF file
ASAndrew Suk
Andrew Suk
ITIstván Tomon
István Tomon

1 February 2023 in Combinatorica
Verified
Journal Article
Closed access
PDF file
JFJacob Fox
Jacob Fox
JPJános Pach
János Pach
ASAndrew Suk
Andrew Suk