اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدBounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs
241
0
0.0
(
0
)
تأليف
Alexandre Bazin
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 | .
قيم البحث
اقرأ أيضاً
A tripartite-circle drawing of a tripartite graph is a drawing in the plane, where each part of a vertex partition is placed on one of three disjoint circles, and the edges do not cross the circles. We present upper and lower bounds on the minimum nu
mber of crossings in tripartite-circle drawings of $K_{m,n,p}$ and the exact value for $K_{2,2,n}$. In contrast to 1- and 2-circle drawings, which may attain the Harary-Hill bound, our results imply that balanced restricted 3-circle drawings of the complete graph are not optimal.
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
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.
A tripartite-circle drawing of a tripartite graph is a drawing in the plane, where each part of a vertex partition is placed on one of three disjoint circles, and the edges do not cross the circles. The tripartite-circle crossing number of a triparti
te graph is the minimum number of edge crossings among all tripartite-circle drawings. We determine the tripartite-circle crossing number of $K_{2,2,n}$.
We prove that one can count in polynomial time the number of minimal transversals of $beta$-acyclic hypergraphs. In consequence, we can count in polynomial time the number of minimal dominating sets of strongly chordal graphs, continuing the line of
research initiated in [M.M. Kante and T. Uno, Counting Minimal Dominating Sets, TAMC17].
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
