Search

We investigate the list packing number of a graph, the least $k$ such that there are always $k$ disjoint proper list-colourings whenever we have lists all of size $k$ associated to the vertices. We are curious how the behaviour of the list packing number contrasts with that of the list chromatic number, particularly in the context of bounded degree graphs. The main question we pursue is whether every graph with maximum degree $\Delta$ has list packing number at most $\Delta +1$. Our results highlight the subtleties of list packing and the barriers to, for example, pursuing a Brooks'-type theorem for the list packing number. [ABSTRACT FROM AUTHOR]

Erratum and addendum to "On the Isomorphism Classes of Transversals III", J. Indian Math. Soc., Vol. 82(3-4), (2015), 83-96. [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]

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]

In this paper, we give a method to determine a complete set of mutually orthogonal Latin squares of order m, where m is an odd prime or power of a prime, as a group transversal of a Frobenius group. [ABSTRACT FROM AUTHOR]

Gyárfás and Sárközy conjectured that every n×n$$ n\times n $$ Latin square has a "cycle‐free" partial transversal of size n−2$$ n-2 $$. We confirm this conjecture in a strong sense for almost all Latin squares, by showing that as n→∞$$ n\to \infty $$, all but a vanishing proportion of n×n$$ n\times n $$ Latin squares have a Hamilton transversal, that is, a full transversal for which any proper subset is cycle‐free. In fact, we prove a counting result that in almost all Latin squares, the number of Hamilton transversals is essentially that of Taranenko's upper bound on the number of full transversals. This result strengthens a result of Kwan (which in turn implies that almost all Latin squares also satisfy the famous Ryser–Brualdi–Stein conjecture). [ABSTRACT FROM AUTHOR]

In this paper, a new combinatorial structure is introduced for image encryption, which has an excellent encryption effect on security and efficiency. An n-transversal in a Latin square has the function of classifying all the matrix's positions, and it can provide a pair of orthogonal Latin squares. Employing an n-transversal of a Latin square, we can permutate all the pixels of an image group by group for the first time, then use two Latin squares for auxiliary diffusion based on a chaotic sequence, and finally, make use of a pair of orthogonal Latin squares to perform the second scrambling. The whole encryption process is "scrambling–diffusion–scrambling". The experimental results indicated that this algorithm passed various tests and achieved a secure and fast encryption effect, which outperformed many of the latest papers. The final information entropy was very close to 8, and the correlation coefficient was approximately 0. All these tests verified the robustness and practicability of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The Hofstadter triangles with their elements (transversals, points, and sectrices) were investigated first by Hofstadter and then were studied and analyzed by many researchers. Based on these known elements, new ones closely related to Hofstadter's elements called "twins" have been defined, analyzed and studied very recently. All of them lie basically in the interior of a given triangle. In this article we analyze and study in an analogous way what we call "exterior Hofstadter elements" in contrast to the known ones which we call "interior Hofstadter elements". The "exterior twins" of the former elements will be studied in a forthcoming work soon. This is because their analysis and study are much more complicated. [ABSTRACT FROM AUTHOR]

In this paper, we have determined the number of isomorphism classes of transversals of subgroups of order 2 and 5 of Alt(5). Further, we have introduced two new graphs Γtic(G) and Γd,tic(G) on a finite group G, where d is the order of a subgroup of G and studied some properties of these graphs. [ABSTRACT FROM AUTHOR]

In this article, we prove that if H is a non-normal subgroup of a finite nilpotent group G non-isomorphic to the dihedral group D8 of order 8, then the number of isomorphism classes of normalized right transversals (NRTs) of H in G is greater than 16, where the isomorphism classes are formed with respect to the induced right-quasigroup structure (induced by the binary operation of G) on each NRT of H in G. [ABSTRACT FROM AUTHOR]

In 1957 Hugo Steinhaus published an elementary, recreational problem concerning a configuration of rooks on the chessboard (Steinhaus in Matematyka, czasopismo dla nauczycieli 1:55, 1957). Over the last 60 years, this problem has achieved quite a peculiar status: apparently, it had two (both published) solutions—one short and elegant (Steinhaus in Sto zadań [One Hundred Problems], PWN, Warszawa, 1958), but (as it soon turned out) incorrect (Zadania konkursowe, Rozwiązania [Competition problems, Solutions]. Matematyka, Czasopismo dla nauczycieli 4-6:62-65, 1958); while the other (Zadania konkursowe, 1958) (Steinhaus in One Hundred Problems in Elementary Mathematics. Popular Lectures in Mathematics, Pergamon Press, Oxford and PWN, Warszawa, 1963)—known internationally, yet long and complex, so probably never read (except, perhaps, by its author) and never checked for its correctness. It was only in 2004 when a correct and short solution of the original Steinhaus' problem was found and published (Morawiec in Matematyka Czasopismo dla nauczycieli 2:46-50, 2004). The solution involved the well-known Hall's 'marriage' theorem (Wilson in Introduction to Graph Theory, Longman, Harlow, 1996, p. 113). Further investigation has shown that the connection between Steinhaus' problem and Hall's theorem runs deeper than the use of the latter in the solution of the former. In this paper we present the results of this investigation, by the way defining a simple but seemingly new class of special matchings (ibid.) in bipartite graphs (id., p. 18). [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]

Let k, d, λ ≥ 1 be integers with d ≥ λ and let X be a finite set of points in Rd. A (d-λ)-plane L transversal to the convex hulls of all k-sets of X is called a Kneser transversal. If in addition L contains (d-λ) + 1 points of X, then L is called a complete Kneser transversal. In this paper, we present various results on the existence of (complete) Kneser transversals for λ = 2, 3. In order to do this, we introduce the notions of stability and instability for (complete) Kneser transversals. We first give a stability result for collections of d+2(k-λ) points in Rd with k-λ ≥ 2 and λ = 2, 3. We then present a description of Kneser transversals L of collections of d + 2(k - λ) points in Rd with k-λ ≥ 2 for λ = 2, 3. We show that either L is a complete Kneser transversal or it contains d-2(λ-1) points and the remaining 2(k-1) points of X are matched in k-1 pairs in such a way that L intersects the corresponding closed segments determined by them. The latter leads to new upper and lower bounds (in the case when λ = 2 and 3) for m(k, d, λ) defined as the maximum positive integer n such that every set of n points (not necessarily in general position) in Rd admit a Kneser transversal. Finally, by using oriented matroid machinery, we present some computational results (closely related to the stability and unstability notions). We determine the existence of (complete) Kneser transversals for each of the 246 different order types of configurations of 7 points in R3. [ABSTRACT FROM AUTHOR]

We consider the size of the smallest set of vertices required to intersect every longest path in a chordal graph. Such sets are known as longest path transversals. We show that if ω (G) is the clique number of a chordal graph G , then there is a transversal of order at most 4 ⌈ ω (G) 5 ⌉. We also consider the analogous question for longest cycles, and show that if G is a 2-connected chordal graph then there is a transversal intersecting all longest cycles of order at most 2 ⌈ ω (G) 3 ⌉. [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]

Let T ( n ) denote the maximal number of transversals in an order- n Latin square. Improving on the bounds obtained by McKay et al., Taranenko recently proved that T ( n ) ≤ ( ( 1 + o ( 1 ) ) n e 2 ) n , and conjectured that this bound is tight. We prove via a probabilistic construction that indeed T ( n ) = ( ( 1 + o ( 1 ) ) n e 2 ) n . Until the present paper, no superexponential lower bound for T ( n ) was known. We also give a simpler proof of the upper bound. [ABSTRACT FROM AUTHOR]

We explore transversals of finite index subgroups of finitely generated groups. We show that when $H$ is a subgroup of a rank-$n$ group $G$ and $H$ has index at least $n$ in $G$, we can construct a left transversal for $H$ which contains a generating set of size $n$ for $G$; this construction is algorithmic when $G$ is finitely presented. We also show that, in the case where $G$ has rank $n\leq 3$, there is a simultaneous left–right transversal for $H$ which contains a generating set of size $n$ for $G$. We finish by showing that if $H$ is a subgroup of a rank-$n$ group $G$ with index less than $3\cdot 2^{n-1}$, and $H$ contains no primitive elements of $G$, then $H$ is normal in $G$ and $G/H\cong C_{2}^{n}$. [ABSTRACT FROM AUTHOR]

We show that, as a consequence of a new result of Pór on universal Tverberg partitions, any large-enough set P of points in R d has a (d + 2) -sized subset whose Radon point has half-space depth at least c d ⋅ | P | , where c d ∈ (0 , 1) depends only on d. We then give two applications of this result. The first is to computing weak ϵ -nets by random sampling. The second is to show that given any set P of points in R d and a parameter ϵ > 0 , there exists a set of O (ϵ − ⌊ d 2 ⌋ + 1) ⌊ d 2 ⌋ -dimensional simplices (ignoring polylogarithmic factors) spanned by points of P such that they form a transversal for all convex objects containing at least ϵ ⋅ | P | points of P. [ABSTRACT FROM AUTHOR]

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]