Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Minimum Number of Edges in Uniform Hypergraphs with Property O
193
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Let $mathcal{H}$ be a hypergraph with $n$ vertices. Suppose that $d_1,d_2,ldots,d_n$ are degrees of the vertices of $mathcal{H}$. The $t$-th graph entropy based on degrees of $mathcal{H}$ is defined as $$ I_d^t(mathcal{H}) =-sum_{i=1}^{n}left(frac{d_i^{t}}{sum_{j=1}^{n}d_j^{t}}logfrac{d_i^{t}}{sum_{j=1}^{n}d_j^{t}}right) =logleft(sum_{i=1}^{n}d_i^{t}right)-sum_{i=1}^{n}left(frac{d_i^{t}}{sum_{j=1}^{n}d_j^{t}}log d_i^{t}right), $$ where $t$ is a real number and the logarithm is taken to the base two. In this paper we obtain upper and lower bounds of $I_d^t(mathcal{H})$ for $t=1$, when $mathcal{H}$ is among all uniform supertrees, unicyclic uniform hypergraphs and bicyclic uniform hypergraphs, respectively.
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.
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.
We study the problems of bounding the number weak and strong independent sets in $r$-uniform, $d$-regular, $n$-vertex linear hypergraphs with no cross-edges. In the case of weak independent sets, we provide an upper bound that is tight up to the first order term for all (fixed) $rge 3$, with $d$ and $n$ going to infinity. In the case of strong independent sets, for $r=3$, we provide an upper bound that is tight up to the second-order term, improving on a result of Ordentlich-Roth (2004). The tightness in the strong independent set case is established by an explicit construction of a $3$-uniform, $d$-regular, cross-edge free, linear hypergraph on $n$ vertices which could be of interest in other contexts. We leave open the general case(s) with some conjectures. Our proofs use the occupancy method introduced by Davies, Jenssen, Perkins, and Roberts (2017).
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 | .
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
