Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCounting results for sparse pseudorandom hypergraphs I
239
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We establish a so-called counting lemma that allows embeddings of certain linear uniform hypergraphs into sparse pseudorandom hypergraphs, generalizing a result for graphs [Embedding graphs with bounded degree in sparse pseudorandom graphs, Israel J. Math. 139 (2004), 93-137]. Applications of our result are presented in the companion paper [Counting results for sparse pseudorandom hypergraphs II].
rate research
Read More
We present a variant of a universality result of Rodl [On universality of graphs with uniformly distributed edges, Discrete Math. 59 (1986), no. 1-2, 125-134] for sparse, $3$-uniform hypergraphs contained in strongly jumbled hypergraphs. One of the ingredients of our proof is a counting lemma for fixed hypergraphs in sparse ``pseudorandom uniform hypergraphs, which is proved in the companion paper [Counting results for sparse pseudorandom hypergraphs I].
We consider extremal problems for subgraphs of pseudorandom graphs. For graphs $F$ and $Gamma$ the generalized Turan density $pi_F(Gamma)$ denotes the density of a maximum subgraph of $Gamma$, which contains no copy of~$F$. Extending classical Turan type results for odd cycles, we show that $pi_{F}(Gamma)=1/2$ provided $F$ is an odd cycle and $Gamma$ is a sufficiently pseudorandom graph. In particular, for $(n,d,lambda)$-graphs $Gamma$, i.e., $n$-vertex, $d$-regular graphs with all non-trivial eigenvalues in the interval $[-lambda,lambda]$, our result holds for odd cycles of length $ell$, provided [ lambda^{ell-2}ll frac{d^{ell-1}}nlog(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, Szabo, 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,lambda)$-graphs) shows that our assumption on $Gamma$ is best possible up to the polylog-factor for every odd $ellgeq 5$.
We prove that for any $tge 3$ there exist constants $c>0$ and $n_0$ such that any $d$-regular $n$-vertex graph $G$ with $tmid ngeq n_0$ and second largest eigenvalue in absolute value $lambda$ satisfying $lambdale c d^{t}/n^{t-1}$ contains a $K_t$-factor, that is, vertex-disjoint copies of $K_t$ covering every vertex of $G$.
Let $F$ be a graph. A hypergraph is called Berge $F$ if it can be obtained by replacing each edge in $F$ by a hyperedge containing it. Given a family of graphs $mathcal{F}$, we say that a hypergraph $H$ is Berge $mathcal{F}$-free if for every $F in mathcal{F}$, the hypergraph $H$ does not contain a Berge $F$ as a subhypergraph. In this paper we investigate the connections between spectral radius of the adjacency tensor and structural properties of a linear hypergraph. In particular, we obtain a spectral version of Tur{a}n-type problems over linear $k$-uniform hypergraphs by using spectral methods, including a tight result on Berge $C_4$-free linear $3$-uniform hypergraphs.
A tight Hamilton cycle in a $k$-uniform hypergraph ($k$-graph) $G$ is a cyclic ordering of the vertices of $G$ such that every set of $k$ consecutive vertices in the ordering forms an edge. R{o}dl, Ruci{n}ski, and Szemer{e}di proved that for $kgeq 3$, every $k$-graph on $n$ vertices with minimum codegree at least $n/2+o(n)$ contains a tight Hamilton cycle. We show that the number of tight Hamilton cycles in such $k$-graphs is $exp(nln n-Theta(n))$. As a corollary, we obtain a similar estimate on the number of Hamilton $ell$-cycles in such $k$-graphs for all $ellin{0,dots,k-1}$, which makes progress on a question of Ferber, Krivelevich and Sudakov.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
