Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDegenerate Turan problems for hereditary properties
67
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $H$ be a graph and $tgeq sgeq 2$ be integers. We prove that if $G$ is an $n$-vertex graph with no copy of $H$ and no induced copy of $K_{s,t}$, then $lambda(G) = Oleft(n^{1-1/s}right)$ where $lambda(G)$ is the spectral radius of the adjacency matrix of $G$. Our results are motivated by results of Babai, Guiduli, and Nikiforov bounding the maximum spectral radius of a graph with no copy (not necessarily induced) of $K_{s,t}$.
rate research
Read More
In this short note we consider the oriented vertex Turan problem in the hypercube: for a fixed oriented graph $overrightarrow{F}$, determine the maximum size $ex_v(overrightarrow{F}, overrightarrow{Q_n})$ of a subset $U$ of the vertices of the oriented hypercube $overrightarrow{Q_n}$ such that the induced subgraph $overrightarrow{Q_n}[U]$ does not contain any copy of $overrightarrow{F}$. We obtain the exact value of $ex_v(overrightarrow{P_k}, overrightarrow{Q_n})$ for the directed path $overrightarrow{P_k}$, the exact value of $ex_v(overrightarrow{V_2}, overrightarrow{Q_n})$ for the directed cherry $overrightarrow{V_2}$ and the asymptotic value of $ex_v(overrightarrow{T}, overrightarrow{Q_n})$ for any directed tree $overrightarrow{T}$.
Given a family of graphs $mathcal{F}$, we prove that the normalized edit distance of any given graph $Gamma$ to being induced $mathcal{F}$-free is estimable with a query complexity that depends only on the bounds of the Frieze--Kannan Regularity Lemma and on a Removal Lemma for $mathcal{F}$.
Combining two classical notions in extremal combinatorics, the study of Ramsey-Turan theory seeks to determine, for integers $mle n$ and $p leq q$, the number $mathsf{RT}_p(n,K_q,m)$, which is the maximum size of an $n$-vertex $K_q$-free graph in which every set of at least $m$ vertices contains a $K_p$. Two major open problems in this area from the 80s ask: (1) whether the asymptotic extremal structure for the general case exhibits certain periodic behaviour, resembling that of the special case when $p=2$; (2) constructing analogues of Bollobas-ErdH{o}s graphs with densities other than $1/2$. We refute the first conjecture by witnessing asymptotic extremal structures that are drastically different from the $p=2$ case, and address the second problem by constructing Bollobas-ErdH{o}s-type graphs using high dimensional complex spheres with all rational densities. Some matching upper bounds are also provided.
Given $r$-uniform hypergraphs $G$ and $H$ the Turan number $rm ex(G, H)$ is the maximum number of edges in an $H$-free subgraph of $G$. We study the typical value of $rm ex(G, H)$ when $G=G_{n,p}^{(r)}$, the ErdH{o}s-Renyi random $r$-uniform hypergraph, and $H=C_{2ell}^{(r)}$, the $r$-uniform linear cycle of length $2ell$. The case of graphs ($r=2$) is a longstanding open problem that has been investigated by many researchers. We determine $rm ex(G_{n,p}^{(r)}, C_{2ell}^{(r)})$ up to polylogarithmic factors for all but a small interval of values of $p=p(n)$ whose length decreases as $ell$ grows. Our main technical contribution is a balanced supersaturation result for linear even cycles which improves upon previous such results by Ferber-Mckinley-Samotij and Balogh-Narayanan-Skokan. The novelty is that the supersaturation result depends on the codegree of some pairs of vertices in the underlying hypergraph. This approach could be used to prove similar results for other hypergraphs $H$.
For given graphs $G$ and $F$, the Turan number $ex(G,F)$ is defined to be the maximum number of edges in an $F$-free subgraph of $G$. Foucaud, Krivelevich and Perarnau and later independently Briggs and Cox introduced a dual version of this problem wherein for a given number $k$, one maximizes the number of edges in a host graph $G$ for which $ex(G,H) < k$. Addressing a problem of Briggs and Cox, we determine the asymptotic value of the inverse Turan number of the paths of length $4$ and $5$ and provide an improved lower bound for all paths of even length. Moreover, we obtain bounds on the inverse Turan number of even cycles giving improved bounds on the leading coefficient in the case of $C_4$. Finally, we give multiple conjectures concerning the asymptotic value of the inverse Turan number of $C_4$ and $P_{ell}$, suggesting that in the latter problem the asymptotic behavior depends heavily on the parity of $ell$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
