3 papers
math.CO2025
A Freeable Matrix Characterization of Bipartite Graphs of Ferrers Dimension Three
Parinya Chalermsook, Ly Orgo, Minoo Zarsav
Ferrer dimension, along with the order dimension, is a standard dimensional concept for bipartite graphs. In this paper, we prove that a graph is of Ferrer dimension three (equival…
math.CO2025
On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers
Parinya Chalermsook, Ly Orgo, Minoo Zarsav
This paper considers the \textit{Zarankiewicz problem} in graphs with low-dimensional geometric representation (i.e., low Ferrers dimension). Our first result reveals a separation…
cs.DS2023
Polynomial-time Approximation of Independent Set Parameterized by Treewidth
Parinya Chalermsook, Fedor Fomin, Thekla Hamm +3
We prove the following result about approximating the maximum independent set in a graph. Informally, we show that any approximation algorithm with a ``non-trivial'' approximation…