61 citations · 177 across the 33 of their papers we have counts for
26 papers · 1 filter
Antichain Codes
Benjamin Gunby, Xiaoyu He, Bhargav Narayanan +1
A family of sets is said to be an antichain if for all distinct , and it is said to be a distance- code if every pair of distinct elements of …
Hypergraph Ramsey numbers of cliques versus stars
David Conlon, Jacob Fox, Xiaoyu He +3
Let denote the complete -uniform hypergraph on vertices and the -uniform hypergraph on vertices consisting of all edges incid…
Logarithmically larger deletion codes of all distances
Noga Alon, Gabriela Bourla, Ben Graham +2
The deletion distance between two binary words is the smallest such that and share a common subsequence of length . A set of binary words o…
Set-coloring Ramsey numbers via codes
David Conlon, Jacob Fox, Xiaoyu He +3
For positive integers with , the set-coloring Ramsey number is the minimum such that if every edge of the complete graph receives a set of c…
Down-set thresholds
Benjamin Gunby, Xiaoyu He, Bhargav Narayanan
We elucidate the relationship between the threshold and the expectation-threshold of a down-set. Qualitatively, our main result demonstrates that there exist down-sets with polynom…
Ramsey goodness of books revisited
Jacob Fox, Xiaoyu He, Yuval Wigderson
The Ramsey number is the minimum such that every graph on vertices contains as a subgraph or its complement contains as a subgraph. For integers $n \geq k…
Maximal independent sets in clique-free graphs
Xiaoyu He, Jiaxi Nie, Sam Spiro
Nielsen proved that the maximum number of maximal independent sets (MIS's) of size in an -vertex graph is asymptotic to , with the extremal construction a disjoint…
Ramsey numbers of sparse digraphs
Jacob Fox, Xiaoyu He, Yuval Wigderson
Burr and Erdős in 1975 conjectured, and Chvátal, Rödl, Szemerédi and Trotter later proved, that the Ramsey number of any bounded degree graph is linear in the number of vertices. I…
Multicolor list Ramsey numbers grow exponentially
Jacob Fox, Xiaoyu He, Sammy Luo +1
The list Ramsey number , recently introduced by Alon, Bucić, Kalvari, Kuperwasser, and Szabó, is a list-coloring variant of the classical Ramsey number. They showed…
Hat Guessing on Books and Windmills
Xiaoyu He, Yuzu Ido, Benjamin Przybocki
The hat-guessing number is a graph invariant defined by Butler, Hajiaghayi, Kleinberg, and Leighton. We determine the hat-guessing number exactly for book graphs with sufficiently…
Hat Guessing Numbers of Degenerate Graphs
Xiaoyu He, Ray Li
Recently, Farnik asked whether the hat guessing number of a graph could be bounded as a function of its degeneracy , and Bosek, Dudek, Farnik, Grytczuk and Ma…
On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions
Xiaoyu He, Youming Qiao
Let be an odd prime. From a simple undirected graph , through the classical procedures of Baer (Trans. Am. Math. Soc., 1938), Tutte (J. Lond. Math. Soc., 1947) and Lovász (B…
Tomescu's graph coloring conjecture for -connected graphs
John Engbers, Aysel Erey, Jacob Fox +1
Let be the number of proper -colorings of a finite simple graph . Tomescu's conjecture, which was recently solved by Fox, He, and Manners, states that $P_G(k) \le k!…
Universality of random permutations
Xiaoyu He, Matthew Kwan
It is a classical fact that for any , a random permutation of length typically contains a monotone subsequence of length . As a…
On the subgraph query problem
Ryan Alweiss, Chady Ben Hamida, Xiaoyu He +1
Given a fixed graph , a real number , and an infinite Erdős-Rényi graph , how many adjacency queries do we have to make to find a copy of insid…
Multicolor Ramsey numbers via pseudorandom graphs
Xiaoyu He, Yuval Wigderson
A weakly optimal -free -graph is a -regular -free graph on vertices with and spectral expansion , for some fixed .…
Independent sets in hypergraphs with a forbidden link
Jacob Fox, Xiaoyu He
We give a probabilistic construction of a -uniform hypergraph on vertices with independence number in which there are at most two edges among any f…
Hedetniemi's conjecture is asymptotically false
Xiaoyu He, Yuval Wigderson
Extending a recent breakthrough of Shitov, we prove that the chromatic number of the tensor product of two graphs can be a constant factor smaller than the minimum chromatic number…
Ramsey, Paper, Scissors
Jacob Fox, Xiaoyu He, Yuval Wigderson
We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on vertices, on each turn Propose…
An upper bound for the restricted online Ramsey number
David Gonzalez, Xiaoyu He, Hanzhi Zheng
The restricted -online Ramsey game is a game played between two players, Builder and Painter. The game starts with isolated vertices. Each turn Builder picks an edge t…
Online Ramsey Numbers and the Subgraph Query Problem
David Conlon, Jacob Fox, Andrey Grinshpun +1
The -online Ramsey game is a combinatorial game between two players, Builder and Painter. Starting from an infinite set of isolated vertices, Builder draws an edge on each t…
A proof of Tomescu's graph coloring conjecture
Jacob Fox, Xiaoyu He, Freddie Manners
In 1971, Tomescu conjectured that every connected graph on vertices with chromatic number has at most proper -colorings. Recently, Knox and Moha…
Exponential Lower Bounds on the Generalized Erdős-Ginzburg-Ziv Constant
Jared Bitz, Sarah Griffith, Xiaoyu He
For a finite abelian group , the generalized Erdős--Ginzburg--Ziv constant is the smallest such that a sequence of elements in always contains a $…
Linear dependence between hereditary quasirandomness conditions
Xiaoyu He
Answering a question of Simonovits and S\' os, Conlon, Fox, and Sudakov proved that for any nonempty graph , and any , there exists polynomial in $\varepsil…