Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userVertex Turan problems for the oriented hypercube
69
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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}$.
rate research
Read More
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}$.
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 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
