اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe size of $3$-uniform hypergraphs with given matching number and codegree
141
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Determine the size of $r$-graphs with given graph parameters is an interesting problem. Chvatal and Hanson (JCTB, 1976) gave a tight upper bound of the size of 2-graphs with restricted maximum degree and matching number; Khare (DM, 2014) studied the same problem for linear $3$-graphs with restricted matching number and maximum degree. In this paper, we give a tight upper bound of the size of $3$-graphs with bounded codegree and matching number.
قيم البحث
اقرأ أيضاً
Let $rge 3$. Given an $r$-graph $H$, the minimum codegree $delta_{r-1}(H)$ is the largest integer $t$ such that every $(r-1)$-subset of $V(H)$ is contained in at least $t$ edges of $H$. Given an $r$-graph $F$, the codegree Turan density $gamma(F)$ is
the smallest $gamma >0$ such that every $r$-graph on $n$ vertices with $delta_{r-1}(H)ge (gamma + o(1))n$ contains $F$ as a subhypergraph. Using results on the independence number of hypergraphs, we show that there are constants $c_1, c_2>0$ depending only on $r$ such that [ 1 - c_2 frac{ln t}{t^{r-1}} le gamma(K_t^r) le 1 - c_1 frac{ln t}{t^{r-1}}, ] where $K_t^r$ is the complete $r$-graph on $t$ vertices. This gives the best general bounds for $gamma(K_t^r)$.
For all integers $k,d$ such that $k geq 3$ and $k/2leq d leq k-1$, let $n$ be a sufficiently large integer {rm(}which may not be divisible by $k${rm)} and let $sle lfloor n/krfloor-1$. We show that if $H$ is a $k$-uniform hypergraph on $n$ vertices w
ith $delta_{d}(H)>binom{n-d}{k-d}-binom{n-d-s+1}{k-d}$, then $H$ contains a matching of size $s$. This improves a recent result of Lu, Yu, and Yuan and also answers a question of Kuhn, Osthus, and Townsend. In many cases, our result can be strengthened to $sleq lfloor n/krfloor$, which then covers the entire possible range of $s$. On the other hand, there are examples showing that the result does not hold for certain $n, k, d$ and $s= lfloor n/krfloor$.
There is a remarkable connection between the clique number and the Lagrangian of a 2-graph proved by Motzkin and Straus in 1965. It is useful in practice if similar results hold for hypergraphs. However the obvious generalization of Motzkin and Strau
s result to hypergraphs is false. Frankl and F{u}redi conjectured that the $r$-uniform hypergraph with $m$ edges formed by taking the first $m$ sets in the colex ordering of ${mathbb N}^{(r)}$ has the largest Lagrangian of all $r$-uniform hypergraphs with $m$ edges. For $r=2$, Motzkin and Straus theorem confirms this conjecture. For $r=3$, it is shown by Talbot that this conjecture is true when $m$ is in certain ranges. In this paper, we explore the connection between the clique number and Lagrangians for $3$-uniform hypergraphs. As an application of this connection, we confirm that Frankl and F{u}redis conjecture holds for bigger ranges of $m$ when $r$=3. We also obtain two weak
We bound the number of minimal hypergraph transversals that arise in tri-partite 3-uniform hypergraphs, a class commonly found in applications dealing with data. Let H be such a hypergraph on a set of vertices V. We give a lower bound of 1.4977 |V | and an upper bound of 1.5012 |V | .
Given a hypergraph $H$, the size-Ramsey number $hat{r}_2(H)$ is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges with the property that in any colouring of the edges of $G$ with two colours there is a monochromatic copy of $
H$. We prove that the size-Ramsey number of the $3$-uniform tight path on $n$ vertices $P^{(3)}_n$ is linear in $n$, i.e., $hat{r}_2(P^{(3)}_n) = O(n)$. This answers a question by Dudek, Fleur, Mubayi, and Rodl for $3$-uniform hypergraphs [On the size-Ramsey number of hypergraphs, J. Graph Theory 86 (2016), 417-434], who proved $hat{r}_2(P^{(3)}_n) = O(n^{3/2} log^{3/2} n)$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
