اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدVertex Turan problems for the oriented hypercube
69
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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}$.
قيم البحث
اقرأ أيضاً
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 mat
rix 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}$.
We find the asymptotic behavior of the Steiner k-diameter of the $n$-cube if $k$ is large. Our main contribution is the lower bound, which utilizes the probabilistic method.
Classical questions in extremal graph theory concern the asymptotics of $operatorname{ex}(G, mathcal{H})$ where $mathcal{H}$ is a fixed family of graphs and $G=G_n$ is taken from a `standard increasing sequence of host graphs $(G_1, G_2, dots)$, most
often $K_n$ or $K_{n,n}$. Inverting the question, we can instead ask how large $e(G)$ can be with respect to $operatorname{ex}(G,mathcal{H})$. We show that the standard sequences indeed maximize $e(G)$ for some choices of $mathcal{H}$, but not for others. Many interesting questions and previous results arise very naturally in this context, which also, unusually, gives rise to sensible extremal questions concerning multigraphs and non-uniform hypergraphs.
The Tur{a}n inequalities and the higher order Tur{a}n inequalities arise in the study of Maclaurin coefficients of an entire function in the Laguerre-P{o}lya class. A real sequence ${a_{n}}$ is said to satisfy the Tur{a}n inequalities if for $ngeq 1$
, $a_n^2-a_{n-1}a_{n+1}geq 0$. It is said to satisfy the higher order Tur{a}n inequalities if for $ngeq 1$, $4(a_{n}^2-a_{n-1}a_{n+1})(a_{n+1}^2-a_{n}a_{n+2})-(a_{n}a_{n+1}-a_{n-1}a_{n+2})^2geq 0$. A sequence satisfying the Turan inequalities is also called log-concave. For the partition function $p(n)$, DeSalvo and Pak showed that for $n>25$, the sequence ${ p(n)}_{n> 25}$ is log-concave, that is, $p(n)^2-p(n-1)p(n+1)>0$ for $n> 25$. It was conjectured by Chen that $p(n)$ satisfies the higher order Tur{a}n inequalities for $ngeq 95$. In this paper, we prove this conjecture by using the Hardy-Ramanujan-Rademacher formula to derive an upper bound and a lower bound for $p(n+1)p(n-1)/p(n)^2$. Consequently, for $ngeq 95$, the Jensen polynomials $g_{3,n-1}(x)=p(n-1)+3p(n)x+3p(n+1)x^2+p(n+2)x^3$ have only real zeros. We conjecture that for any positive integer $mgeq 4$ there exists an integer $N(m)$ such that for $ngeq N(m) $, the polynomials $sum_{k=0}^m {mchoose k}p(n+k)x^k$ have only real zeros. This conjecture was independently posed by Ono.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
