YWYiting Wang
Yiting Wang
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Yiting Wang has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Matthew Kwan
Institute of Science and Technology Austria (ISTA) Klosterneuburg Austria
2 shared publications - Adva Mond
Department of Mathematics, King’s College London, Strand, London, United Kingdom
1 shared publication - Julien Portier
Department of Pure Mathematics and Mathematical Statistics (DPMMS) University of Cambridge Cambridge UK
1 shared publication - Lawrence Hollom
Department of Pure Mathematics and Mathematical Statistics (DPMMS) University of Cambridge Wilberforce Road CB3 0WA Cambridge United Kingdom
1 shared publication - Lisa Sauermann
Institute for Applied Mathematics University of Bonn Germany
1 shared publication - Lyuben Lichev
TU Wien, Faculty of Mathematics and Geoinformation, Institute of Statistics and Mathematical Methods in Economics, Research Unit of Mathematical Stochastics, Vienna, Austria
1 shared publication
Latest Publications
- Open Access
Note on the trace of random walks on pseudorandom graphs
We study the graph-theoretic properties of the trace of random walks on pseudorandom graphs. We show that for any $\varepsilon>0$, there exists a constant $C$ such that the cover time of an $(n,d,λ)$-graph $G$ with $d/λ\ge C$ is at most $(1+\varepsilon)n\log n$, meaning the expected number of steps needed to reach all vertices at least once is at most $(1+\varepsilon)n\log n$ regardless of the starting vertex. Furthermore, we prove that with high probability, the trace of a random walk of length $(1+\varepsilon)n\log n$ on $G$ is Hamiltonian, regardless of the starting vertex. These results also hold for random $d$-regular graphs with sufficiently large $d$. These findings answer two questions proposed by Frieze, Krivelevich, Michaeli, and Peled [PLMS, 2018]. Notably, our results imply a bound on a stronger version of the cover time: with high probability, all vertices are covered after $(1+\varepsilon)n\log n$ steps, regardless of the starting vertex. Our proofs rely on the spectral properties of the adjacency matrix and the graph expansion. All results are asymptotically optimal.Open AccessNote on the trace of random walks on pseudorandom graphs
We study the graph-theoretic properties of the trace of random walks on pseudorandom graphs. We show that for any $\varepsilon>0$, there exists a constant $C$ such that the cover time of an $(n,d,λ)$-graph $G$ with $d/λ\ge C$ is at most $(1+\varepsilon)n\log n$, meaning the expected number of steps needed to reach all vertices at least once is at most $(1+\varepsilon)n\log n$ regardless of the starting vertex. Furthermore, we prove that with high probability, the trace of a random walk of length $(1+\varepsilon)n\log n$ on $G$ is Hamiltonian, regardless of the starting vertex. These results also hold for random $d$-regular graphs with sufficiently large $d$. These findings answer two questions proposed by Frieze, Krivelevich, Michaeli, and Peled [PLMS, 2018]. Notably, our results imply a bound on a stronger version of the cover time: with high probability, all vertices are covered after $(1+\varepsilon)n\log n$ steps, regardless of the starting vertex. Our proofs rely on the spectral properties of the adjacency matrix and the graph expansion. All results are asymptotically optimal. - Open Access
- 28 January 2026
- Published by Springer Nature in Combinatorica
- Vol. 46 (1) , 5
Counting Perfect Matchings in Dirac Hypergraphs
One of the foundational theorems of extremal graph theory is Dirac’s theorem , which says that if an n -vertex graph G has minimum degree at least n /2, then G has a Hamilton cycle, and therefore a perfect matching (if n is even). Later work by Sárközy, Selkow and Szemerédi showed that in fact Dirac graphs have many Hamilton cycles and perfect matchings, culminating in a result of Cuckler and Kahn that gives a precise description of the numbers of Hamilton cycles and perfect matchings in a Dirac graph G (in terms of an entropy-like parameter of G ). In this paper we extend Cuckler and Kahn’s result to perfect matchings in hypergraphs. For positive integers $$d , and for n divisible by k , let $$m_{d}(k,n)$$ be the minimum d -degree that ensures the existence of a perfect matching in an n -vertex k -uniform hypergraph. In general, it is an open question to determine (even asymptotically) the values of $$m_{d}(k,n)$$ , but we are nonetheless able to prove an analogue of the Cuckler–Kahn theorem, showing that if an n -vertex k -uniform hypergraph G has minimum d -degree at least $$(1+\gamma )m_{d}(k,n)$$ (for any constant $$\gamma >0$$ ), then the number of perfect matchings in G is controlled by an entropy-like parameter of G . This strengthens cruder estimates arising from work of Kang–Kelly–Kühn–Osthus–Pfenninger and Pham–Sah–Sawhney–Simkin.d < k - 28 January 2026
- Published by Springer Nature in Combinatorica
- Vol. 46 (1) , 5
Open AccessCounting Perfect Matchings in Dirac Hypergraphs
One of the foundational theorems of extremal graph theory is Dirac’s theorem , which says that if an n -vertex graph G has minimum degree at least n /2, then G has a Hamilton cycle, and therefore a perfect matching (if n is even). Later work by Sárközy, Selkow and Szemerédi showed that in fact Dirac graphs have many Hamilton cycles and perfect matchings, culminating in a result of Cuckler and Kahn that gives a precise description of the numbers of Hamilton cycles and perfect matchings in a Dirac graph G (in terms of an entropy-like parameter of G ). In this paper we extend Cuckler and Kahn’s result to perfect matchings in hypergraphs. For positive integers $$d , and for n divisible by k , let $$m_{d}(k,n)$$ be the minimum d -degree that ensures the existence of a perfect matching in an n -vertex k -uniform hypergraph. In general, it is an open question to determine (even asymptotically) the values of $$m_{d}(k,n)$$ , but we are nonetheless able to prove an analogue of the Cuckler–Kahn theorem, showing that if an n -vertex k -uniform hypergraph G has minimum d -degree at least $$(1+\gamma )m_{d}(k,n)$$ (for any constant $$\gamma >0$$ ), then the number of perfect matchings in G is controlled by an entropy-like parameter of G . This strengthens cruder estimates arising from work of Kang–Kelly–Kühn–Osthus–Pfenninger and Pham–Sah–Sawhney–Simkin.d < k - Open Access
Approximate Itai-Zehavi conjecture for random graphs
A famous conjecture by Itai and Zehavi states that, for every $d$-vertex-connected graph $G$ and every vertex $r$ in $G$, there are $d$ spanning trees of $G$ such that, for every vertex $v$ in $G\setminus \{r\}$, the paths between $r$ and $v$ in different trees are internally vertex-disjoint. We show that with high probability the Itai-Zehavi conjecture holds asymptotically for the Erdős-Rényi random graph $G(n,p)$ when $np= ω(\log n)$ and for random regular graphs $G(n,d)$ when $d= ω(\log n)$. Moreover, we essentially confirm the conjecture up to a constant factor for sparser random regular graphs. This answers positively a question of Draganić and Krivelevich. Our proof makes use of recent developments on sprinkling techniques in random regular graphs.Open AccessApproximate Itai-Zehavi conjecture for random graphs
A famous conjecture by Itai and Zehavi states that, for every $d$-vertex-connected graph $G$ and every vertex $r$ in $G$, there are $d$ spanning trees of $G$ such that, for every vertex $v$ in $G\setminus \{r\}$, the paths between $r$ and $v$ in different trees are internally vertex-disjoint. We show that with high probability the Itai-Zehavi conjecture holds asymptotically for the Erdős-Rényi random graph $G(n,p)$ when $np= ω(\log n)$ and for random regular graphs $G(n,d)$ when $d= ω(\log n)$. Moreover, we essentially confirm the conjecture up to a constant factor for sparser random regular graphs. This answers positively a question of Draganić and Krivelevich. Our proof makes use of recent developments on sprinkling techniques in random regular graphs. - Open Access
Algebraic aspects of the polynomial Littlewood-Offord problem
Consider a degree-$d$ polynomial $f(ξ_1,\dots,ξ_n)$ of independent Rademacher random variables $ξ_1,\dots,ξ_n$. To what extent can $f(ξ_1,\dots,ξ_n)$ concentrate on a single point? This is the so-called polynomial Littlewood-Offord problem. A nearly optimal bound was proved by Meka, Nguyen and Vu: the point probabilities are always at most about $1/\sqrt n$, unless $f$ is "close to the zero polynomial" (having only $o(n^d)$ nonzero coefficients). In this paper we prove several results supporting the general philosophy that the Meka-Nguyen-Vu bound can be significantly improved unless $f$ is "close to a polynomial with special algebraic structure", drawing some comparisons to phenomena in analytic number theory. In particular, one of our results is a corrected version of a conjecture of Costello on multilinear forms (in an appendix with Ashwin Sah and Mehtaab Sawhney, we disprove Costello's original conjecture).Open AccessAlgebraic aspects of the polynomial Littlewood-Offord problem
Consider a degree-$d$ polynomial $f(ξ_1,\dots,ξ_n)$ of independent Rademacher random variables $ξ_1,\dots,ξ_n$. To what extent can $f(ξ_1,\dots,ξ_n)$ concentrate on a single point? This is the so-called polynomial Littlewood-Offord problem. A nearly optimal bound was proved by Meka, Nguyen and Vu: the point probabilities are always at most about $1/\sqrt n$, unless $f$ is "close to the zero polynomial" (having only $o(n^d)$ nonzero coefficients). In this paper we prove several results supporting the general philosophy that the Meka-Nguyen-Vu bound can be significantly improved unless $f$ is "close to a polynomial with special algebraic structure", drawing some comparisons to phenomena in analytic number theory. In particular, one of our results is a corrected version of a conjecture of Costello on multilinear forms (in an appendix with Ashwin Sah and Mehtaab Sawhney, we disprove Costello's original conjecture).