Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAsymptotic enumeration of linear hypergraphs with given number of vertices and edges
101
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For $ngeq 3$, let $r=r(n)geq 3$ be an integer. A hypergraph is $r$-uniform if each edge is a set of $r$ vertices, and is said to be linear if two edges intersect in at most one vertex. In this paper, the number of linear $r$-uniform hypergraphs on $ntoinfty$ vertices is determined asymptotically when the number of edges is $m(n)=o(r^{-3}n^{ frac32})$. As one application, we find the probability of linearity for the independent-edge model of random $r$-uniform hypergraph when the expected number of edges is $o(r^{-3}n^{ frac32})$. We also find the probability that a random $r$-uniform linear hypergraph with a given number of edges contains a given subhypergraph.
rate research
Read More
A basic combinatorial invariant of a convex polytope $P$ is its $f$-vector $f(P)=(f_0,f_1,dots,f_{dim P-1})$, where $f_i$ is the number of $i$-dimensional faces of $P$. Steinitz characterized all possible $f$-vectors of $3$-polytopes and Grunbaum characterized the pairs given by the first two entries of the $f$-vectors of $4$-polytopes. In this paper, we characterize the pairs given by the first two entries of the $f$-vectors of $5$-polytopes. The same result was also proved by Pineda-Villavicencio, Ugon and Yost independently.
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.
Motivated by the ErdH{o}s-Faber-Lov{a}sz (EFL) conjecture for hypergraphs, we consider the list edge coloring of linear hypergraphs. We show that if the hyper-edge sizes are bounded between $i$ and $C_{i,epsilon} sqrt{n}$ inclusive, then there is a list edge coloring using $(1 + epsilon) frac{n}{i - 1}$ colors. The dependence on $n$ in the upper bound is optimal (up to the value of $C_{i,epsilon}$).
An oriented k-uniform hypergraph (a family of ordered k-sets) has the ordering property (or Property O) if for every linear order of the vertex set, there is some edge oriented consistently with the linear order. We find bounds on the minimum number of edges in a hypergraph with Property O.
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$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
