ترغب بنشر مسار تعليمي؟ اضغط هنا

On the cover Ramsey number of Berge hypergraphs

82   0   0.0 ( 0 )
 نشر من قبل Linyuan Lu
 تاريخ النشر 2019
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

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$.



قيم البحث

اقرأ أيضاً

We generalize a result of Balister, Gy{H{o}}ri, Lehel and Schelp for hypergraphs. We determine the unique extremal structure of an $n$-vertex, $r$-uniform, connected, hypergraph with the maximum number of hyperedges, without a $k$-Berge-path, where $n geq N_{k,r}$, $kgeq 2r+13>17$.
68 - Beka Ergemlidze 2020
In this paper, we consider maximum possible value for the sum of cardinalities of hyperedges of a hypergraph without a Berge $4$-cycle. We significantly improve the previous upper bound provided by Gerbner and Palmer. Furthermore, we provide a constr uction that slightly improves the previous lower bound.
In many proofs concerning extremal parameters of Berge hypergraphs one starts with analyzing that part of that shadow graph which is contained in many hyperedges. Capturing this phenomenon we introduce two new types of hypergraphs. A hypergraph $math cal{H}$ is a $t$-heavy copy of a graph $F$ if there is a copy of $F$ on its vertex set such that each edge of $F$ is contained in at least $t$ hyperedges of $mathcal{H}$. $mathcal{H}$ is a $t$-wise Berge copy of $F$ if additionally for distinct edges of $F$ those $t$ hyperedges are distinct. We extend known upper bounds on the Turan number of Berge hypergraphs to the $t$-wise Berge hypergraphs case. We asymptotically determine the Turan number of $t$-heavy and $t$-wise Berge copies of long paths and cycles and exactly determine the Turan number of $t$-heavy and $t$-wise Berge copies of cliques. In the case of 3-uniform hypergraphs, we consider the problem in more details and obtain additional results.
For $ngeq s> rgeq 1$ and $kgeq 2$, write $n rightarrow (s)_{k}^r$ if every hyperedge colouring with $k$ colours of the complete $r$-uniform hypergraph on $n$ vertices has a monochromatic subset of size $s$. Improving upon previous results by textcite {AGLM14} and textcite{EHMR84} we show that [ text{if } r geq 3 text{ and } n rightarrow (s)_k^r text{ then } 2^n rightarrow (s+1)_{k+3}^{r+1}. ] This yields an improvement for some of the known lower bounds on multicolour hypergraph Ramsey numbers. Given a hypergraph $H=(V,E)$, we consider the Ramsey-like problem of colouring all $r$-subsets of $V$ such that no hyperedge of size $geq r+1$ is monochromatic. We provide upper and lower bounds on the number of colours necessary in terms of the chromatic number $chi(H)$. In particular we show that this number is $O(log^{(r-1)} (r chi(H)) + r)$.
169 - Andras Gyarfas 2018
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$ confi gurations. 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.$$
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا