7 papers
On efficient graph covers and steered random walks
Nathan Tung, Richard Ueltzen
We prove that the vertices of any -vertex graph can be partitioned into pieces of radius such that the sum of the sizes of their closed neighborhoods is at most…
Linear equations and chromatic thresholds in sets
Nathan Tung
We derive sparse analogs of several Roth-type results, showing that they hold in sets of near-maximum size. It is shown that if a set is free of pairwise distinct solut…
Coloring sparse random Cayley graphs
Nathan Tung
It is shown that there exists so that the Cayley graph over any finite abelian group generated by random elements is properly 3-colorable with high probabi…
Randomly piercing algebraic sets
Daniel Altman, Nathan Tung
We show, for example, that if one samples \[\frac{\log p}{2\log(1+(p-1)^{-1})} \cdot n^2(1 + o_{n\to \infty}(1))\] points in at random then asymptotically almost s…
Cutting a unit square and permuting blocks
Nathan Tung
Consider a random permutation of objects that permutes disjoint blocks of size and then permutes elements within each block. Normalizing its cycle lengths by give…
New Sidorenko-type inequalities in tournaments
Xiaoyu He, Nitya Mani, Jiaxi Nie +2
As a directed analog of Sidorenko's conjecture in extremal graph theory, Fox, Himwich, Zhou, and the second author defined an oriented graph to be tournament Sidorenko (anti-Si…