اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDegenerate Turan problems for hereditary properties
67
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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}$.
قيم البحث
اقرأ أيضاً
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 orient
ed 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 whi
ch 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 hypergra
ph, 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 w
herein 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$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
