اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe exact linear Turan number of the Sail
85
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A hypergraph is linear if any two of its edges intersect in at most one vertex. The Sail (or $3$-fan) $F^3$ is the $3$-uniform linear hypergraph consisting of $3$ edges $f_1, f_2, f_3$ pairwise intersecting in the same vertex $v$ and an additional edge $g$ intersecting all $f_i$ in a vertex different from $v$. The linear Turan number $ex_{lin}(n, F^3)$ is the maximum number of edges in a $3$-uniform linear hypergraph on $n$ vertices that does not contain a copy of $F^3$. F{u}redi and Gyarfas proved that if $n = 3k$, then $ex_{lin}(n, F^3) = k^2$ and the only extremal hypergraphs in this case are transversal designs. They also showed that if $n = 3k+2$, then $ex_{lin}(n, F^3) = k^2+k$, and the only extremal hypergraphs are truncated designs (which are obtained from a transversal design on $3k+3$ vertices with $3$ groups by removing one vertex and all the hyperedges containing it) along with three other small hypergraphs. However, the case when $n =3k+1$ was left open. In this paper, we solve this remaining case by proving that $ex_{lin}(n, F^3) = k^2+1$ if $n = 3k+1$, answering a question of F{u}redi and Gyarfas. We also characterize all the extremal hypergraphs. The difficulty of this case is due to the fact that these extremal examples are rather non-standard. In particular, they are not derived from transversal designs like in the other cases.
قيم البحث
اقرأ أيضاً
The Turan number of a graph $H$, denoted by $ex(n,H)$, is the maximum number of edges in any graph on $n$ vertices which does not contain $H$ as a subgraph. Let $P_{k}$ denote the path on $k$ vertices and let $mP_{k}$ denote $m$ disjoint copies of $P
_{k}$. Bushaw and Kettle [Tur{a}n numbers of multiple paths and equibipartite forests, Combin. Probab. Comput. 20(2011) 837--853] determined the exact value of $ex(n,kP_ell)$ for large values of $n$. Yuan and Zhang [The Tur{a}n number of disjoint copies of paths, Discrete Math. 340(2)(2017) 132--139] completely determined the value of $ex(n,kP_3)$ for all $n$, and also determined $ex(n,F_m)$, where $F_m$ is the disjoint union of $m$ paths containing at most one odd path. They also determined the exact value of $ex(n,P_3cup P_{2ell+1})$ for $ngeq 2ell+4$. Recently, Bielak and Kieliszek [The Tur{a}n number of the graph $2P_5$, Discuss. Math. Graph Theory 36(2016) 683--694], Yuan and Zhang [Tur{a}n numbers for disjoint paths, arXiv: 1611.00981v1] independently determined the exact value of $ex(n,2P_5)$. In this paper, we show that $ex(n,2P_{7})=max{[n,14,7],5n-14}$ for all $n ge 14$, where $[n,14,7]=(5n+91+r(r-6))/2$, $n-13equiv r,(text{mod }6)$ and $0leq r< 6$.
Let $F$ be a graph. The planar Turan number of $F$, denoted by $text{ex}_{mathcal{P}}(n,F)$, is the maximum number of edges in an $n$-vertex planar graph containing no copy of $F$ as a subgraph. Let $Theta_k$ denote the family of Theta graphs on $kge
q 4$ vertices, that is, a graph obtained by joining a pair of non-consecutive vertices of a $k$-cycle with an edge. Y. Lan, et.al. determined sharp upper bound for $text{ex}_{mathcal{P}}(n,Theta_4)$ and $text{ex}_{mathcal{P}}(n,Theta_5)$. Moreover, they obtained an upper bound for $text{ex}_{mathcal{P}}(n,Theta_6)$. They proved that, $text{ex}_{mathcal{P}}(n,Theta_6)leq frac{18}{7}n-frac{36}{7}$. In this paper, we improve their result by giving a bound which is sharp. In particular, we prove that $text{ex}_{mathcal{P}}(n,Theta_6)leq frac{18}{7}n-frac{48}{7}$ and demonstrate that there are infinitely many $n$ for which there exists a $Theta_6$-free planar graph $G$ on $n$ vertices, which attains the bound.
Let ${rm ex}_{mathcal{P}}(n,T,H)$ denote the maximum number of copies of $T$ in an $n$-vertex planar graph which does not contain $H$ as a subgraph. When $T=K_2$, ${rm ex}_{mathcal{P}}(n,T,H)$ is the well studied function, the planar Turan number of
$H$, denoted by ${rm ex}_{mathcal{P}}(n,H)$. The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both ${rm ex}_{mathcal{P}}(n,C_4)$ and ${rm ex}_{mathcal{P}}(n,C_5)$. Later on, Y. Lan, et al. continued this topic and proved that ${rm ex}_{mathcal{P}}(n,C_6)leq frac{18(n-2)}{7}$. In this paper, we give a sharp upper bound ${rm ex}_{mathcal{P}}(n,C_6) leq frac{5}{2}n-7$, for all $ngeq 18$, which improves Lans result. We also pose a conjecture on ${rm ex}_{mathcal{P}}(n,C_k)$, for $kgeq 7$.
Let $F$ be a fixed graph. The rainbow Turan number of $F$ is defined as the maximum number of edges in a graph on $n$ vertices that has a proper edge-coloring with no rainbow copy of $F$ (where a rainbow copy of $F$ means a copy of $F$ all of whose e
dges have different colours). The systematic study of such problems was initiated by Keevash, Mubayi, Sudakov and Verstraete. In this paper, we show that the rainbow Turan number of a path with $k+1$ edges is less than $left(frac{9k}{7}+2right) n$, improving an earlier estimate of Johnston, Palmer and Sarkar.
The Turan number of a graph H, ex(n,H), is the maximum number of edges in a graph on n vertices which does not have H as a subgraph. Let P_k be the path with k vertices, the square P^2_k of P_k is obtained by joining the pairs of vertices with distan
ce one or two in P_k. The powerful theorem of ErdH{o}s, Stone and Simonovits determines the asymptotic behavior of ex(n,P^2_k). In the present paper, we determine the exact value of ex(n,P^2_5) and ex(n,P^2_6) and pose a conjecture for the exact value of ex(n,P^2_k).
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
