Source author record

Hiep Hàn

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Extremal results for odd cycles in sparse pseudorandom graphs

We consider extremal problems for subgraphs of pseudorandom graphs. For graphs $F$ and $Γ$ the generalized Turán density $π_F(Γ)$ denotes the density of a maximum subgraph of $Γ$ , which contains no copy of~ $F$ . Extending classical Turán type results for odd cycles, we show that $π_{F}(Γ)=1/2$ provided $F$ is an odd cycle and $Γ$ is a sufficiently pseudorandom graph. In particular, for $(n,d,λ)$ -graphs $Γ$ , i.e., $n$ -vertex, $d$ -regular graphs with all non-trivial eigenvalues in the interval $[-λ,λ]$ , our result holds for odd cycles of length $\ell$ , provided $λ^{\ell-2}\ll \frac{d^{\ell-1}}n\log(n)^{-(\ell-2)(\ell-3)}\,.$ Up to the polylog-factor this verifies a conjecture of Krivelevich, Lee, and Sudakov. For triangles the condition is best possible and was proven previously by Sudakov, Szabó, and Vu, who addressed the case when $F$ is a complete graph. A construction of Alon and Kahale (based on an earlier construction of Alon for triangle-free $(n,d,λ)$ -graphs) shows that our assumption on $Γ$ is best possible up to the polylog-factor for every odd $\ell\geq 5$ .

preprint2014arXiv

Powers of Hamilton cycles in pseudorandom graphs

We study the appearance of powers of Hamilton cycles in pseudorandom graphs, using the following comparatively weak pseudorandomness notion. A graph $G$ is $(\varepsilon,p,k,\ell)$ -pseudorandom if for all disjoint $X$ and $Y\subset V(G)$ with $|X|\ge\varepsilon p^kn$ and $|Y|\ge\varepsilon p^\ell n$ we have $e(X,Y)=(1\pm\varepsilon)p|X||Y|$ . We prove that for all $β>0$ there is an $\varepsilon>0$ such that an $(\varepsilon,p,1,2)$ -pseudorandom graph on $n$ vertices with minimum degree at least $βpn$ contains the square of a Hamilton cycle. In particular, this implies that $(n,d,λ)$ -graphs with $λ\ll d^{5/2 }n^{-3/2}$ contain the square of a Hamilton cycle, and thus a triangle factor if $n$ is a multiple of $3$ . This improves on a result of Krivelevich, Sudakov and Szabó [Triangle factors in sparse pseudo-random graphs, Combinatorica 24 (2004), no. 3, 403--426]. We also extend our result to higher powers of Hamilton cycles and establish corresponding counting versions.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.