61 citations · 177 across the 33 of their papers we have counts for
8 papers · 1 filter
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…
Optimization of CNOT circuits on limited connectivity architecture
Bujiao Wu, Xiaoyu He, Shuai Yang +4
A CNOT circuit is the key gadget for entangling qubits in quantum computing systems. However, the qubit connectivity of noisy intermediate-scale quantum (NISQ) devices is constrain…
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…