Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe size of $3$-uniform hypergraphs with given matching number and codegree
141
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 with $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 Straus 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)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
