From the 1 of 16 linked papers with an AI index.
16 papers
Sharp bounds for the fractional chromatic number of high-girth -degenerate graphs
Peter Allen, Abhishek Dhawan, Jonathan A. Noel
The paper proves tight upper and lower bounds of order d/log d for the fractional chromatic number of high‑girth d‑degenerate graphs, provides a randomized algorithm achieving the…
The independence number of uncrowded hypergraphs: bounds matching the shattering threshold
Abhishek Dhawan, Abhishek Methuku, Minh-Quan Vo
A foundational theorem of Ajtai, Komlós, Pintz, Spencer, and Szemerédi asserts that every -vertex -uniform uncrowded hypergraph with maximum degree contains an indepen…
Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
Abhishek Dhawan, Nhi U. Dinh, Eren C. KızıldaÄ +2
We study the algorithmic tractability of finding large independent sets in dense random hypergraphs. In the sparse regime, much of the natural algorithms can be formulated within e…
Fractional coloring via entropy
Abhishek Dhawan
In recent work, Martinsson and Steiner proved that triangle-free -degenerate graphs have fractional chromatic number . Here, we introduc…
The strong chromatic index of -free graphs
Richard Bi, Peter Bradshaw, Abhishek Dhawan +1
A strong edge coloring of a graph is an edge coloring such that each color class forms an induced matching in . The strong chromatic inde…
Choosability of multipartite hypergraphs
Peter Bradshaw, Abhishek Dhawan, Nhi Dinh +2
A -uniform hypergraph (or -graph) is -partite if can be partitioned into sets such that each edge in contains precisely one ver…