Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA note on maximum size of Berge-$C_4$-free hypergraphs
69
0
0.0
(
0
)
Authors
Beka Ergemlidze
Ask ChatGPT about the research
No Arabic abstract
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 construction that slightly improves the previous lower bound.
rate research
Read More
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$.
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 $mathcal{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.
A hypergraph $mathcal{F}$ is non-trivial intersecting if every two edges in it have a nonempty intersection but no vertex is contained in all edges of $mathcal{F}$. Mubayi and Verstra{e}te showed that for every $k ge d+1 ge 3$ and $n ge (d+1)n/d$ every $k$-graph $mathcal{H}$ on $n$ vertices without a non-trivial intersecting subgraph of size $d+1$ contains at most $binom{n-1}{k-1}$ edges. They conjectured that the same conclusion holds for all $d ge k ge 4$ and sufficiently large $n$. We confirm their conjecture by proving a stronger statement. They also conjectured that for $m ge 4$ and sufficiently large $n$ the maximum size of a $3$-graph on $n$ vertices without a non-trivial intersecting subgraph of size $3m+1$ is achieved by certain Steiner systems. We give a construction with more edges showing that their conjecture is not true in general.
A emph{$k$--bisection} of a bridgeless cubic graph $G$ is a $2$--colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes have order at most $k$. Ban and Linial conjectured that {em every bridgeless cubic graph admits a $2$--bisection except for the Petersen graph}. In this note, we prove Ban--Linials conjecture for claw--free cubic graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
