Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Turan number of Berge-K_4 in triple systems
170
0
0.0
(
0
)
Authors
Andras Gyarfas
Ask ChatGPT about the research
No Arabic abstract
A Berge-$K_4$ in a triple system is a configuration with four vertices $v_1,v_2,v_3,v_4$ and six distinct triples ${e_{ij}: 1le i< j le 4}$ such that ${v_i,v_j}subset e_{ij}$ for every $1le i<jle 4$. We denote by $cal{B}$ the set of Berge-$K_4$ configurations. A triple system is $cal{B}$-free if it does not contain any member of $cal{B}$. We prove that the maximum number of triples in a $cal{B}$-free triple system on $nge 6$ points is obtained by the balanced complete $3$-partite triple system: all triples ${abc: ain A, bin B, cin C}$ where $A,B,C$ is a partition of $n$ points with $$leftlfloor{nover 3}rightrfloor=|A|le |B|le |C|=leftlceil{nover 3}rightrceil.$$
rate research
Read More
A {em special four-cycle } $F$ in a triple system consists of four triples {em inducing } a $C_4$. This means that $F$ has four special vertices $v_1,v_2,v_3,v_4$ and four triples in the form $w_iv_iv_{i+1}$ (indices are understood $pmod 4$) where the $w_j$s are not necessarily distinct but disjoint from ${v_1,v_2,v_3,v_4}$. There are seven non-isomorphic special four-cycles, their family is denoted by $cal{F}$. Our main result implies that the Turan number $text{ex}(n,{cal{F}})=Theta(n^{3/2})$. In fact, we prove more, $text{ex}(n,{F_1,F_2,F_3})=Theta(n^{3/2})$, where the $F_i$-s are specific members of $cal{F}$. This extends previous bounds for the Turan number of triple systems containing no Berge four cycles. We also study $text{ex}(n,{cal{A}})$ for all ${cal{A}}subseteq {cal{F}}$. For 16 choices of $cal{A}$ we show that $text{ex}(n,{cal{A}})=Theta(n^{3/2})$, for 92 choices of $cal{A}$ we find that $text{ex}(n,{cal{A}})=Theta(n^2)$ and the other 18 cases remain unsolved.
In this paper we study Turan and Ramsey numbers in linear triple systems, defined as $3$-uniform hypergraphs in which any two triples intersect in at most one vertex. A famous result of Ruzsa and Szemeredi is that for any fixed $c>0$ and large enough $n$ the following Turan-type theorem holds. If a linear triple system on $n$ vertices has at least $cn^2$ edges then it contains a {em triangle}: three pairwise intersecting triples without a common vertex. In this paper we extend this result from triangles to other triple systems, called {em $s$-configurations}. The main tool is a generalization of the induced matching lemma from $aba$-patterns to more general ones. We slightly generalize $s$-configurations to {em extended $s$-configurations}. For these we cannot prove the corresponding Turan-type theorem, but we prove that they have the weaker, Ramsey property: they can be found in any $t$-coloring of the blocks of any sufficiently large Steiner triple system. Using this, we show that all unavoidable configurations with at most 5 blocks, except possibly the ones containing the sail $C_{15}$ (configuration with blocks 123, 345, 561 and 147), are $t$-Ramsey for any $tgeq 1$. The most interesting one among them is the {em wicket}, $D_4$, formed by three rows and two columns of a $3times 3$ point matrix. In fact, the wicket is $1$-Ramsey in a very strong sense: all Steiner triple systems except the Fano plane must contain a wicket.
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$.
For a fixed set of positive integers $R$, we say $mathcal{H}$ is an $R$-uniform hypergraph, or $R$-graph, if the cardinality of each edge belongs to $R$. An $R$-graph $mathcal{H}$ is emph{covering} if every vertex pair of $mathcal{H}$ is contained in some hyperedge. For a graph $G=(V,E)$, a hypergraph $mathcal{H}$ is called a textit{Berge}-$G$, denoted by $BG$, if there exists an injection $f: E(G) to E(mathcal{H})$ such that for every $e in E(G)$, $e subseteq f(e)$. In this note, we define a new type of Ramsey number, namely the emph{cover Ramsey number}, denoted as $hat{R}^R(BG_1, BG_2)$, as the smallest integer $n_0$ such that for every covering $R$-uniform hypergraph $mathcal{H}$ on $n geq n_0$ vertices and every $2$-edge-coloring (blue and red) of $mathcal{H}$ , there is either a blue Berge-$G_1$ or a red Berge-$G_2$ subhypergraph. We show that for every $kgeq 2$, there exists some $c_k$ such that for any finite graphs $G_1$ and $G_2$, $R(G_1, G_2) leq hat{R}^{[k]}(BG_1, BG_2) leq c_k cdot R(G_1, G_2)^3$. Moreover, we show that for each positive integer $d$ and $k$, there exists a constant $c = c(d,k)$ such that if $G$ is a graph on $n$ vertices with maximum degree at most $d$, then $hat{R}^{[k]}(BG,BG) leq cn$.
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 $kgeq 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
