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


Yiting Wang has a total of 9 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Note on the trace of random walks on pseudorandom graphs

    by Yaobin Chen, Yiting Wang

    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

    Counting Perfect Matchings in Dirac Hypergraphs

    by Matthew Kwan, Roodabeh Safavi, Yiting Wang

    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 d < k , and for n divisible by k , let $$m_{d}(k,n)$$ 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)$$ 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)$$ ( 1 + γ ) m d ( k , n ) (for any constant $$\gamma >0$$ γ > 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.

  • Open Access

    Approximate Itai-Zehavi conjecture for random graphs

    by Lawrence Hollom, Lyuben Lichev, Adva Mond, Julien Portier, Yiting Wang

    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

    by Zhihan Jin, Matthew Kwan, Lisa Sauermann, Yiting Wang

    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).