Search

The fuzzy concept lattice is one of the effective tools for data mining, and granular reduction is one of its significant research contents. However, little research has been done on granular reduction at different granularities in formal fuzzy contexts (FFCs). Furthermore, the complexity of the composition of the fuzzy concept lattice limits the interest in its research. Therefore, how to simplify the concept lattice structure and how to construct granular reduction methods with granularity have become urgent issues that need to be investigated. To this end, firstly, the concept of an object granule with granularity is defined. Secondly, two reduction algorithms, one based on Boolean reasoning and the other on a graph-theoretic heuristic, are formulated while keeping the structure of this object granule unchanged. Further, to simplify the structure of the fuzzy concept lattice, a partial order relation with parameters is proposed. Finally, the feasibility and effectiveness of our proposed reduction approaches are verified by data experiments. [ABSTRACT FROM AUTHOR]

In this paper, we unfold balanced and totally balanced neighborhood hypergraphs to discover new classes of normally torsion-free monomial ideals. As a consequence, we establish that the closed neighborhood ideals and the dominating ideals of strongly chordal graphs are normally torsion-free. We discuss the stable sets of associated primes of the dominating ideals of cycles and characterize all the cycles with normally torsion-free dominating ideals. [ABSTRACT FROM AUTHOR]

The concept of intuitionistic fuzzy soft set is applied to generalize the theory of transversals in hypergraphs. The notion of transversals of an Intuitionistic Fuzzy Soft Hypergraphs (IFSHGs) and locally minimal transversals of IFSHGs are pioneered with some of its specifications. It is also proved that H ˜ is (μ, ν)-tempered IFSHGs if H ˜ is support simple, elementary and simply ordered. Then, an algorithm is developed and proposed to find the minimal transversals of IFSHGs. An application is also identified in selecting appropriate location for the installation of wind turbines. Finally the proposed algorithm works in finding the suitable place for wind turbine installation. As a result the proposed algorithm is helpful in making decisions. [ABSTRACT FROM AUTHOR]

The transversal number τ(H) $\tau (H)$ of a hypergraph H $H$ is the minimum number of vertices that intersect every edge of H $H$. This notion of transversal is fundamental in hypergraph theory and has been studied a great deal in the literature. A hypergraph H $H$ is r $r$‐regular if every vertex of H $H$ has degree r $r$, that is, every vertex of H $H$ belongs to exactly r $r$ edges. Further, H $H$ is k $k$‐uniform if every edge of H $H$ has size k $k$, and so every edge of H $H$ is a k $k$‐element subset of V(H) $V(H)$. For r≥2 $r\ge 2$ and k≥2 $k\ge 2$, let Hr,k,nreg ${{\rm{ {\mathcal H} }}}_{r,k,n}^{\text{reg}}$ be the class of all r $r$‐regular k $k$‐uniform hypergraphs of order n $n$. In this paper we study the problem posed by Tuza to determine or estimate the best possible constants θr,k ${\theta }_{r,k}$ (which depend only on r $r$ and k $k$) for each r≥2 $r\ge 2$ and k≥2 $k\ge 2$, such that τ(H)≤θr,k×n $\tau (H)\le {\theta }_{r,k}\times n$ for all H∈Hr,k,nreg $H\in {{\rm{ {\mathcal H} }}}_{r,k,n}^{\text{reg}}$. These constants are given by θr,k=supτ(H)n ${\theta }_{r,k}=\text{sup}\frac{\tau (H)}{n}$, where the supremum is taken over all H∈Hr,k,nreg $H\in {{\rm{ {\mathcal H} }}}_{r,k,n}^{\text{reg}}$. Tuza presented closed formulas when r=2 $r=2$ or k=2 $k=2$, and showed that θr,2=rr+1 ${\theta }_{r,2}=\frac{r}{r+1}$ for all r≥2 $r\ge 2$, θ2,k=43k ${\theta }_{2,k}=\frac{4}{3k}$ for k≥2 $k\ge 2$ even, and θ2,k=43k+1 ${\theta }_{2,k}=\frac{4}{3k+1}$ for k≥3 $k\ge 3$ odd. We conjecture that θ3,k≤32k ${\theta }_{3,k}\le \frac{3}{2k}$ for all k≥2 $k\ge 2$ and that θ4,k≤127k ${\theta }_{4,k}\le \frac{12}{7k}$ for all k≥2 $k\ge 2$. We show that both these conjectures hold for k∈{2,3,4,6} $k\in \{2,3,4,6\}$. Moreover we show, for example, that θ3,3=12 ${\theta }_{3,3}=\frac{1}{2}$ and θ4,3=59 ${\theta }_{4,3}=\frac{5}{9}$. We show that for every 0<ε<1 $0\lt \varepsilon \lt 1$ and for sufficiently large r $r$ and k $k$, the growth of θr,k ${\theta }_{r,k}$ is given by ε1+ln(r)k≤θr,k≤1+ln(r)k $\varepsilon \left(\frac{1+\mathrm{ln}(r)}{k}\right)\le {\theta }_{r,k}\le \frac{1+\mathrm{ln}(r)}{k}$. [ABSTRACT FROM AUTHOR]

Motivated from the surrounding property of a point set in R d introduced by Holmsen, Pach, and Tverberg, we consider the transversal number and chromatic number of a simplicial sphere. As an attempt to give a lower bound for the maximum transversal ratio of simplicial d-spheres, we provide two infinite constructions. The first construction gives infinitely many (d + 1) -dimensional simplicial polytopes with the transversal ratio exactly 2 / (d + 2) for every d ≥ 2 . In the case of d = 2 , this meets the previously well-known upper bound 1/2 tightly. The second gives infinitely many simplicial 3-spheres with the transversal ratio greater than 1/2. This was unexpected from what was previously known about the surrounding property. Moreover, we show that, for d ≥ 3 , the facet hypergraph F (K) of a d-dimensional simplicial sphere K has the chromatic number χ (F (K)) ∈ O (n (⌈ d / 2 ⌉ - 1) / d ) , where n is the number of vertices of K . This slightly improves the upper bound previously obtained by Heise, Panagiotou, Pikhurko, and Taraz. [ABSTRACT FROM AUTHOR]

We study the (a, b)-monochromatic transversal game that is a combinatorial Maker–Breaker game where Alice and Bob alternately colour a vertices in red and b vertices in blue of a hypergraph, respectively. Either player is enabled to start the game. Alice tries to construct a hyperedge transversal, and Bob tries to prevent this. The winner is Alice if she obtains a red hyperedge transversal; otherwise, Bob wins the game if he obtains a monochromatic blue hyperedge. Maker–Breaker games were determined to be PSPACE-complete. In this work, we analyze the game played on clique-hypergraphs of powers of cycles, and we show strategies that, depending on the choice of the parameters, allow a specific player to win the game. [ABSTRACT FROM AUTHOR]

The (a , b) - monochromatic transversal game is a combinatorial Maker-Breaker game where two players, Alice and Bob, alternately take turns colouring a and b vertices of a hypergraph in red and blue, respectively (either player may start the game). Alice tries to construct a hyperedge transversal, and Bob tries to prevent this. Alice wins if she obtains a red hyperedge transversal, and Bob wins if he obtains a monochromatic blue hyperedge. We study the game played on biclique-hypergraphs of powers of paths and powers of cycles, showing strategies that, depending on the choice of parameters a and b , allow a specific player to win the game. [ABSTRACT FROM AUTHOR]

In this paper we present an incremental algorithm for computing the transversal hypergraph. Our algorithm is an optimized version of Berge's algorithm [2] for solving the transversal hypergraph problem. The original algorithm of Berge is the simplest and most direct scheme for generating all minimal transversals of a hypergraph. Here we present an optimized version of Berge's algorithm that we call BergeOpt. We show that BergeOpt can significantly reduce the number of expensive inclusion tests. [ABSTRACT FROM AUTHOR]

The transversal number Τ (H) of a hypergraph H is the minimum number of vertices that intersect every edge of H. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [Discuss. Math. Graph Theory, 22 (2002), pp. 199-210] conjectured that if H is a 3-regular 6-uniform hypergraph of order n, then Τ(H) < 1/4n. In this paper we prove this conjecture, which has become known as the Tuza-Vestergaard conjecture. [ABSTRACT FROM AUTHOR]

A transversal in a hypergraph H is set of vertices that intersect every edge of H. A transversal coalition in H consists of two disjoint sets of vertices X and Y of H , neither of which is a transversal but whose union X ∪ Y is a transversal in H. Such sets X and Y are said to form a transversal coalition. A transversal coalition partition in H is a vertex partition Ψ = { V 1 , V 2 , ... , V p } such that for all i ∈ [ p ] , either the set V i is a singleton set that is a transversal in H or the set V i forms a transversal coalition with another set V j for some j , where j ∈ [ p ] ∖ { i }. The transversal coalition number C τ (H) in H equals the maximum order of a transversal coalition partition in H. For k ≥ 2 a hypergraph H is k -uniform if every edge of H has cardinality k. Among other results, we prove that if k ≥ 2 and H is a k -uniform hypergraph, then C τ (H) ≤ ⌊ 1 4 k 2 ⌋ + k + 1. Further we show that for every k ≥ 2 , there exists a k -uniform hypergraph that achieves equality in this upper bound. [ABSTRACT FROM AUTHOR]

As a basic notion in algebra, closure operations have been successfully applied to many fields of computer science. In this paper we study dense family in the closure operations. In particular, we prove some families to be dense in any closure operation, in which the greatest and smallest dense families, including the collection of the whole closed sets and the minimal generator of the closed sets, are also pointed out. More important, a necessary and sufficient condition for an arbitrary family to be dense is provided in our paper. Then we use these dense families to characterize minimal keys of the closure operation under the viewpoint of transversal hypergraphs and construct an algorithm for determining the minimal keys of a closure operation. [ABSTRACT FROM AUTHOR]

The transversal hypergraph problem asks to enumerate the minimal hitting sets of a hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP'95] gave an algorithm running in output-polynomial time, but whose space requirement also scales with the output. We improve this to polynomial delay and space. Central to our approach is the extension problem, deciding for a set X of vertices whether it is contained in any minimal hitting set. We show that this is one of the first natural problems to be W [ 3 ] -complete. We give an algorithm for the extension problem running in time O (m | X | + 1 n) and prove a SETH-lower bound showing that this is close to optimal. We apply our enumeration method to the discovery problem of minimal unique column combinations from data profiling. Our empirical evaluation suggests that the algorithm outperforms its worst-case guarantees on hypergraphs stemming from real-world databases. [ABSTRACT FROM AUTHOR]

Multi-column dependencies in relational databases come associated with two different computational tasks. The detection problem is to decide whether a dependency of a certain type and size holds in a given database, the discovery problem asks to enumerate all valid dependencies of that type. We settle the complexity of both of these problems for unique column combinations (UCCs), functional dependencies (FDs), and inclusion dependencies (INDs). We show that the detection of UCCs and FDs is W[2]-complete when parameterized by the solution size. The discovery of inclusion-wise minimal UCCs is proven to be equivalent under parsimonious reductions to the transversal hypergraph problem of enumerating the minimal hitting sets of a hypergraph. The discovery of FDs is equivalent to the simultaneous enumeration of the hitting sets of multiple input hypergraphs. We further identify the detection of INDs as one of the first natural W[3]-complete problems. The discovery of maximal INDs is shown to be equivalent to enumerating the maximal satisfying assignments of antimonotone, 3-normalized Boolean formulas. [ABSTRACT FROM AUTHOR]

Let H be a hypergraph of order n H = | V (H) | and size m H = | E (H) |. The transversal number τ (H) of H is the minimum number of vertices that intersect every edge of H. A linear hypergraph is one in which every two distinct edges intersect in at most one vertex. A k -uniform hypergraph has all edges of size k. Let L k be the class of k -uniform linear hypergraphs. In this paper we study the problem of determining or estimating the best possible constants q k (which depends only on k) such that τ (H) ≤ q k (n H + m H) for all H ∈ L k . We establish lower bounds on q k for all k ≥ 2. For all k ≥ 2 and for all 0 < a < 1 , we show that q k ≥ a (1 − a) k / ( (1 − a) k + a ln (e / a)) , where here ln denotes the natural logarithm to the base e. [ABSTRACT FROM AUTHOR]

In this paper, we study the dualization in distributive lattices, a generalization of the well-known hypergraph dualization problem. We in particular propose equivalent formulations of the problem in terms of graphs, hypergraphs, and posets. It is known that hypergraph dualization amounts to generate all minimal transversals of a hypergraph, or all minimal dominating sets of a graph. In this new framework, a poset on vertices is given together with the input (hyper)graph, and minimal "ideal solutions" are to be generated. This in particular allows us to study the complexity of the problem under various combined restrictions on graph classes and poset types, including bipartite, split, and co-bipartite graphs, and variants of neighborhood inclusion posets. For example, we show that while the enumeration of minimal dominating sets is possible with linear delay in split graphs, the problem, within the same class, gets as hard as for general graphs when generalized to this framework. More surprisingly, this result holds even when the poset is only comparing vertices with included neighborhoods in the graph. If both the poset and the graph class are sufficiently restricted, we show that the dualization is tractable relying on existing algorithms from the literature. [ABSTRACT FROM AUTHOR]

The (a,b)-monochromatic transversal game is an avoider-enforcer combinatorial game in which two players, Alice and Bob, alternately take turns colouring respectively a vertices in red and b vertices in blue of a hypergraph. She wins the game by obtaining a red transversal while he wins by obtaining a monochromatic blue hyperedge. Also, both players are enabled to start the game and they play optimally. In this paper, we analyze the game played on biclique-hypergraphs of powers of paths and of powers of cycles showing strategies that, depending on the choice of the parameters a and b, allow a specific player to win the game. [ABSTRACT FROM AUTHOR]

A subset T of vertices in a hypergraph H is a transversal if T has a nonempty intersection with every edge of H. The transversal number τ (H) of H is the minimum size of a transversal in H. A hypergraph H is 3-uniform if every edge of H has size 3. Let H be a 3-uniform hypergraph with n H vertices and m H edges. Tuza (Discrete Math 86:117–126, 1990) and Chvátal and McDiarmid (Combinatorica 12:19–26, 1992) showed that 4 τ (H) ≤ n H + m H . Chvátal and McDiarmid also showed that 6 τ (H) ≤ 2 n H + m H . The linear hypergraphs achieving equality in these bounds were characterized by the authors (Henning and Yeo in J Graph Theory 59:326–348, 2008; Discrete Math 313:959–966, 2013). In this paper, we show that these bounds can be improved if we impose some structural properties on H. We show that if H does not contain a subhypergraph isomorphic to the affine plane AG(2, 3) of order 3 with two vertices deleted, then 17 τ (H) ≤ 5 n H + 3 m H . The total domination number γ t (G) of a graph G is the minimum cardinality of a set S of vertices so that every vertex in G is adjacent to some vertex in S. It is known (Archdeacon et al. in J Graph Theory 46:207–210, 2004) that if G is a graph of order n with minimum degree at least 3, then γ t (G) ≤ 1 2 n , and that this bound is tight. As a consequence of our hypergraph results, we show that if G is a graph of order n with minimum degree at least 3 that contains no 4-cycles and no specified graph on 12 vertices as a subgraph, then γ t (G) ≤ 8 17 n . [ABSTRACT FROM AUTHOR]

In this paper, we prove a conjecture of Aharoni and Howard on the existence of rainbow (transversal) matchings in sufficiently large families F1,...,Fs of tuples in {1,...,n}k, provided s⩾470. [ABSTRACT FROM AUTHOR]

Abstract We consider the problem of enumerating all minimal hitting sets of a given hypergraph (V , R) , where V is a finite set, called the vertex set and R is a set of subsets of V called the hyperedges. We show that, when the hypergraph admits a balanced subdivision , then a recursive decomposition can be used to obtain efficiently all minimal hitting sets of the hypergraph. We apply this decomposition framework to get incremental polynomial-time algorithms for finding minimal hitting sets and minimal set covers for a number of hypergraphs induced by a set of points and a set of geometric objects. The set of geometric objects includes half-spaces, hyper-rectangles and balls, in fixed dimension. A distinguishing feature of the algorithms we obtain is that they admit an efficient global parallel implementation, in the sense that all minimal hitting sets can be generated in polylogarithmic time in | V | , | R | and the total number of minimal transversals M , using a polynomial number of processors. For half-spaces in R 2 , we show that the above two enumeration problems can be solved, using a different technique, with amortized polynomial delay. [ABSTRACT FROM AUTHOR]

Abstract We prove that one can count in polynomial time the number of minimal transversals of β -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. Kanté and T. Uno (2017) [18]. [ABSTRACT FROM AUTHOR]

Abstract A set S of vertices in a hypergraph H is a transversal if it has a nonempty intersection with every edge of H. For k ≥ 1 , if H is a hypergraph with every edge of size at least k , then a k -transversal in H is a transversal that intersects every edge of H in at least k vertices. In particular, a 1-transversal is a transversal. The upper k -transversal number ϒ k (H) of H is the maximum cardinality of a minimal k -transversal in H. We obtain asymptotically best possible lower bounds on ϒ k (H) for uniform hypergraphs H. More precisely, we show that for r ≥ 2 and for every integer k ∈ [ r ] , if H is a connected r -uniform hypergraph with n vertices, then ϒ k (H) > 2 3 n r − k + 1 . For r > k ≥ 1 and ε > 0 , we show that there exist infinitely many r -uniform hypergraphs, H r , k ∗ , of order n and a function f (r , k) of r and k satisfying ϒ k (H r , k ∗) < (1 + ε) ⋅ f (r , k) ⋅ n r − k + 1. [ABSTRACT FROM AUTHOR]

For a hypergraph H , the transversal is a subset of vertices whose intersection with every edge is nonempty. The cardinality of a minimum transversal is the transversal number of H , denoted by τ (H). The Tuza constant c k is defined as sup ⁡ τ (H) / (m + n) , where H ranges over all k -uniform hypergraphs, with m and n being the number of edges and vertices, respectively. We give an upper bound and a lower bound on c k. The upper bound improves the known ones for k ≥ 7 , and the lower bound improves the known ones for k ∈ { 7 , 8 , 10 , 11 , 13 , 14 , 17 }. [ABSTRACT FROM AUTHOR]

A subset T of vertices in a hypergraph H is a transversal if T has a nonempty intersection with every edge of H. The transversal number of H is the minimum size of a transversal in H. A subset S of vertices in a graph G with no isolated vertex, is a total dominating set if every vertex of G is adjacent to a vertex of S. The minimum cardinality of a total dominating set in G is the total domination number of G. In this paper, we obtain a new (improved) probabilistic upper bound for the transversal number of a hypergraph, and a new (improved) probabilistic upper bound for the total domination number of a graph. [ABSTRACT FROM AUTHOR]

Paul Erdős and László Lovász established by means of an example that there exists a maximal intersecting family of k -sets with ⌊ ( e − 1 ) k ! ⌋ blocks, where e is the base of natural logarithm. László Lovász conjectured that their example is best known example which has the maximum number of blocks. Later it was disproved. But the quest for such examples remain valid till this date. In this note we compute the transversal size of a certain series of intersecting families of k -sets, which is constructed over the Cyclic graph. It helps to provide an example of maximal intersecting family of k -sets with so many blocks and to present two worthwhile examples which disprove two special cases of one of the conjectures of Frankl et al. [ABSTRACT FROM AUTHOR]

Tuza’s Conjecture asserts that the minimum number τΔ′(G) of edges of a graph G whose deletion results in a triangle-free graph is at most 2 times the maximum number νΔ′(G) of edge-disjoint triangles of G. The complete graphs K4 and K5 show that the constant 2 would be best possible. Moreover, if true, the conjecture would be essentially tight even for K4-free graphs. In this paper, we consider several subclasses of K4-free graphs. We show that the constant 2 can be improved for them and we try to provide the optimal one. The classes we consider are of two kinds: graphs with edges in few triangles and graphs obtained by forbidding certain odd-wheels. We translate an approximate min-max relation for τΔ′(G) and νΔ′(G) into an equivalent one for the clique cover number and the independence number of the triangle graph of G and we provide θ-bounding functions for classes related to triangle graphs. In particular, we obtain optimal θ-bounding functions for the classes Free(K5,claw,diamond) and Free(P5,diamond,K2,3) and a χ-bounding function for the class (banner,odd-hole,K1,4¯). [ABSTRACT FROM AUTHOR]

Let Π q be an arbitrary finite projective plane of order q . A subset S of its points is called saturating if any point outside S is collinear with a pair of points from S . Applying probabilistic tools we improve the upper bound on the smallest possible size of the saturating set to ⌈ 3 q ln q ⌉ + ⌈ ( q + 1 ) ∕ 2 ⌉ . The same result is presented using an algorithmic approach as well, which points out the connection with the transversal number of uniform multiple intersecting hypergraphs. [ABSTRACT FROM AUTHOR]

Johnson and Lovász and Stein proved independently that any hypergraph satisfies τ ≤ ( 1 + ln Δ ) τ ∗ , where τ is the transversal number, τ ∗ is its fractional version, and Δ denotes the maximum degree. We prove τ f ≤ 3 . 153 τ ∗ max { ln Δ , f } for the f -fold transversal number τ f . Similarly to Johnson, Lovász and Stein, we also show that this bound can be achieved non-probabilistically, using a greedy algorithm. As a combinatorial application, we prove an estimate on how fast τ f ∕ f converges to τ ∗ . As a geometric application, we obtain an upper bound on the minimal density of an f -fold covering of the d -dimensional Euclidean space by translates of any convex body. [ABSTRACT FROM AUTHOR]

A transversal in a hypergraph H is a subset of vertices that has a nonempty intersection with every edge of H . A transversal family F of H is a family of (not necessarily distinct) transversals of H . The effective transversal-ratio of the family F is the ratio of the number of sets in F over the maximum times r F any element appears in F . The fractional disjoint transversal number FDT ( H ) is the supremum of the effective transversal-ratio taken over all transversal families. That is, FDT ( H ) = sup F | F | ∕ r F . Using a connection with not-all-equal 3 -SAT, we prove that if H is a 3 -regular 3 -uniform hypergraph, then FDT ( H ) ≥ 2 , which proves a known conjecture. Using probabilistic arguments, we prove that for all k ≥ 3 , if H is a k -regular k -uniform hypergraph, then FDT ( H ) ≥ 1 ∕ ( 1 − ( k − 1 k ) 1 k 1 k − 1 ) , and that this bound is essentially best possible. [ABSTRACT FROM AUTHOR]

A d-interval hypergraph has d disjoint copies of the unit interval as its vertex set, and each edge is the union of d subintervals, one on each copy. Extending a classical result of Gallai on the case $$d=1$$ , Tardos and Kaiser used topological tools to bound the ratio between the transversal number and the matching number in such hypergraphs. We take a dual point of view, and bound the edge-covering number (namely the minimal number of edges covering the entire vertex set) in terms of a parameter expressing independence of systems of partitions of the d unit intervals. The main tool we use is an extension of the KKM theorem to products of simplices, due to Peleg. [ABSTRACT FROM AUTHOR]

A d-interval is a union of at most d disjoint closed intervals on a fixed line. Tardos [14] and the second author [11] used topological tools to bound the transversal number τ of a family H of d-intervals in terms of d and the matching number ν of H. We investigate the weighted and fractional versions of this problem and prove upper bounds that are tight up to constant factors. We apply both a topological method and an approach of Alon [1]. For the use of the latter, we prove a weighted version of Turán's theorem. We also provide proofs of the upper bounds of [11] that are more direct than the original proofs. [ABSTRACT FROM AUTHOR]

Let r ( k ) denote the maximum number of edges in a k -uniform intersecting family with covering number k . Erdős and Lovász proved that ⌊ k ! ( e − 1 ) ⌋ ≤ r ( k ) ≤ k k . Frankl, Ota, and Tokushige improved the lower bound to r ( k ) ≥ ( k / 2 ) k − 1 , and Tuza improved the upper bound to r ( k ) ≤ ( 1 − e − 1 + o ( 1 ) ) k k . We establish that r ( k ) ≤ ( 1 + o ( 1 ) ) k k − 1 . [ABSTRACT FROM AUTHOR]

Consider a 3-uniform hypergraph of order n with clique number k such that the intersection of all its k -cliques is empty. Szemerédi and Petruska proved n ≤ 8 m 2 + 3 m , for fixed m = n − k , and they conjectured the sharp bound n ≤ ( m + 2 2 ). This problem is known to be equivalent to determining the maximum order of a τ -critical 3-uniform hypergraph with transversal number m (details may also be found in a companion paper by Kézdy and Lehel). The best known bound, n ≤ 3 4 m 2 + m + 1 , was obtained by Tuza using the machinery of τ -critical hypergraphs. Here we propose an alternative approach, a combination of the iterative decomposition process introduced by Szemerédi and Petruska with the skew version of Bollobás's theorem on set pair systems. The new approach improves the bound to n ≤ ( m + 2 2 ) + O (m 5 / 3) , resolving the conjecture asymptotically. [ABSTRACT FROM AUTHOR]

The transversal number τ (H) of a hypergraphHis the minimum cardinality of a set of vertices that intersects all edges ofH. The matching number α′(H) ofHis the maximum cardinality of a matching inH. A hypergraphHis intersecting if and only if α′(H) = 1. For an intersecting hypergraphHof rankrwithout isolated vertex, clearly τ (H) ≤r.His called 1-special if τ (H) =r, andHis maximal 1-special ifHis 1-special and adding any missingr-edge toHincreases the matching number.n2(r) andn3(r) are the maximum orders of a 1-special hypergraph and a maximal 1-special hypergraph, respectively. Furthermore, the intersecting hyper-graphHis called 1-edge-critical if for anye∈E(H) and anyv∈e,v-shrinkingeincreases the matching number;His called 1-vertex-critical if for anyv∈V(H) deleting the vertexvandv-shrinking all edges incident withvincreases the matching number.n4(r) andn5(r) are the maximum orders of a 1-edge-critical hypergraph and a 1-vertex-critical hypergraph, respectively. The intersecting hypergraphs, as defined above, are said to be matching critical [M.A. Henning and A. Yeo, Quaest. Math.37(2014), 127–138]. In this paper we study the extremal behavior of matching critical intersecting hypergraphs. We show thatn2(r) =n3(r) andn4(r) =n5(r) for allr≥ 2, which partly answers an open problem on matching critical intersecting hypergraphs posed by Henning and Yeo. We also give a strengthening of the resultn4(r) =n5(r) for intersectingr-uniform hypergraphs. [ABSTRACT FROM AUTHOR]

Let k , d , λ ⩾ 1 be integers with d ⩾ λ . Let m ( k , d , λ ) be the maximum positive integer n such that every set of n points (not necessarily in general position) in R d has the property that the convex hulls of all k -sets have a common transversal ( d − λ ) -plane. It turns out that m ( k , d , λ ) is strongly connected with other interesting problems, for instance, the chromatic number of Kneser hypergraphs and a discrete version of Rado's centerpoint theorem. In the same spirit, we introduce a natural discrete version m ⁎ of m by considering the existence of complete Kneser transversals . We study the relation between them and give a number of lower and upper bounds of m ⁎ as well as the exact value in some cases. The main ingredient for the proofs are Radon's partition theorem as well as oriented matroids tools. By studying the alternating oriented matroid we obtain the asymptotic behavior of the function m ⁎ for the family of cyclic polytopes. [ABSTRACT FROM AUTHOR]

The 3/4 -Game Total Domination Conjecture posed by Henning, Klavžar, and Rall [Combinatorica, (2016)] states that if G is a graph on n vertices in which every component contains at least three vertices, then γtg(G) ≤ 3/4n, where γtg(G) denotes the game total domination number of G. Motivated by this conjecture, we raise the problem to a higher level by introducing a transversal game in hypergraphs. We define the game transversal number, τg(H), of a hypergraph H, and prove that if every edge of H has size at least 2, and H ... C4, then τg(H) ≤ 4/11 (nH + mH), where nH and mH denote the number of vertices and edges, respectively, in H. Further, we characterize the hypergraphs achieving equality in this bound. As an application of this result, we prove that if G is a graph on n vertices with minimum degree at least 2, then γtg(G) < 8 11n. As a consequence of this result, the 3/4 -Game Total Domination Conjecture is true over the class of graphs with minimum degree at least 2. [ABSTRACT FROM AUTHOR]

We show that all minimal dominating sets of a chordal bipartite graph can be generated in incremental polynomial, hence output polynomial, time. Enumeration of minimal dominating sets in graphs is equivalent to enumeration of minimal transversals in hypergraphs. Whether the minimal transversals of a hypergraph can be enumerated in output polynomial time is a well-studied and challenging question that has been open for several decades. With this result we contribute to the known cases having an affirmative reply to this important question. [ABSTRACT FROM AUTHOR]

In this paper, we study some average properties of hypergraphs and the average complexity of algorithms applied to hypergraphs under different probabilistic models. Our approach is both theoretical and experimental since our goal is to obtain a random model that is able to capture the real-data complexity. Starting from a model that generalizes the Erdös–Renyi model [10,11] , we obtain asymptotic estimations on the average number of transversals, irredundants and minimal transversals in a random hypergraph. We use those results to obtain an upper bound on the average complexity of algorithms to generate the minimal transversals of a hypergraph. Then we make our random model more complex in order to bring it closer to real-data and identify cases where the average number of minimal transversals is at most polynomial, quasi-polynomial or exponential. [ABSTRACT FROM AUTHOR]

In [9] Thomassé and Yeo pose the following problem: Find the minimumckfor which everyk-uniform hypergraph withnvertices andnedges has a transversal of size at mostckn. A direct consequence of this result is that every graph of ordernwith minimum degree at leastkhas a total dominating set of cardinality at mostckn. It is known thatc2= 2/3,c3= 1/2, andc4= 3/7. Thomassé and Yeo show that 4/11 ≤c5and conjecture thatc5= 4/11. In this paper we show thatc5≤ 17/44. Thus, 16/44 ≤c5≤ 17/44. More generally we prove that every 5-uniform hypergraph onnvertices andmedges has a transversal with no more than (10n+7m)/44 vertices. Consequently, every graph onnvertices with minimum degree at least five has total domination number at most 17n/44. [ABSTRACT FROM PUBLISHER]

The paradigm shift prompted by Zadeh's fuzzy sets in 1965 did not end with the fuzzy model and logic. Extensions in various lines have produced e.g., intuitionistic fuzzy sets in 1983, complex fuzzy sets in 2002, or hesitant fuzzy sets in 2010. The researcher can avail himself of graphs of various types in order to represent concepts like networks with imprecise information, whether it is fuzzy, intuitionistic, or has more general characteristics. When the relationships in the network are symmetrical, and each member can be linked with groups of members, the natural concept for a representation is a hypergraph. In this paper we develop novel generalized hypergraphs in a wide fuzzy context, namely, complex intuitionistic fuzzy hypergraphs, complex Pythagorean fuzzy hypergraphs, and complex q-rung orthopair fuzzy hypergraphs. Further, we consider the transversals and minimal transversals of complex q-rung orthopair fuzzy hypergraphs. We present some algorithms to construct the minimal transversals and certain related concepts. As an application, we describe a collaboration network model through a complex q-rung orthopair fuzzy hypergraph. We use it to find the author having the most outstanding collaboration skills using score and choice values. [ABSTRACT FROM AUTHOR]

The concept of q-rung orthopair fuzzy sets generalizes the notions of intuitionistic fuzzy sets and Pythagorean fuzzy sets to describe complicated uncertain information more effectively. Their most dominant attribute is that the sum of the q th power of the truth-membership and the q th power of the falsity-membership must be equal to or less than one, so they can broaden the space of uncertain data. This set can adjust the range of indication of decision data by changing the parameter q, q ≥ 1 . In this research study, we design a new framework for handling uncertain data by means of the combinative theory of q-rung orthopair fuzzy sets and hypergraphs. We define q-rung orthopair fuzzy hypergraphs to achieve the advantages of both theories. Further, we propose certain novel concepts, including adjacent levels of q-rung orthopair fuzzy hypergraphs, (α , β) -level hypergraphs, transversals, and minimal transversals of q-rung orthopair fuzzy hypergraphs. We present a brief comparison of our proposed model with other existing theories. Moreover, we implement some interesting concepts of q-rung orthopair fuzzy hypergraphs for decision-making to prove the effectiveness of our proposed model. [ABSTRACT FROM AUTHOR]