Search

Let [ n ] = { 1 , 2 , ⋯ , n } . Let [ n ] k be the family of all subsets of [n] of size k. Define a real-valued weight function w on the set [ n ] k such that ∑ X ∈ [ n ] k w (X) ≥ 0 . Let U n , t , k be the set of all P = { P 1 , P 2 , ⋯ , P t } such that P i ∈ [ n ] k for all i and P i ∩ P j = ∅ for i ≠ j . For each P ∈ U n , t , k , let w (P) = ∑ P ∈ P w (P) . Let U n , t , k + (w) be set of all P ∈ U n , t , k with w (P) ≥ 0 . In this paper, we show that | U n , t , k + (w) | ≥ ∏ 1 ≤ i ≤ (t - 1) k (n - t k + i) (k !) t - 1 ((t - 1) !) for sufficiently large n. [ABSTRACT FROM AUTHOR]

Let [ n ] = { 1 , 2 , ⋯ , n } . For each i ∈ [ k ] and j ∈ [ n ] , let w i (j) be a real number. Suppose that ∑ i ∈ [ k ] , j ∈ [ n ] w i (j) ≥ 0 . Let F be the set of all functions with domain [k] and codomain [n]. For each f ∈ F , let w (f) = w 1 (f (1)) + w 2 (f (2)) + ⋯ + w k (f (k)). A function f ∈ F is said to be nonnegative if w (f) ≥ 0 . Let F + (w) be set of all nonnegative functions, i.e., F + (w) = { f ∈ F : w (f) ≥ 0 }. In this paper, we show that | F + (w) | ≥ n k - 1 for n ≥ 3 (k - 1) 2 . [ABSTRACT FROM AUTHOR]

Let Fq be the field of size q and SL(n, q) be the special linear group of order n over the field Fq. Assume that n is an even integer. Let Ai⊆SL(n,q) for i=1,2,⋯,k and |A1|=|A2|=⋯=|Ak|=l. The set {A1,A2,⋯,Ak} is called a k-cross (n, q)-Parsons set of size l, if for any pair of (i, j) with i≠j, A-B∈SL(n,q) for all A∈Ai and B∈Aj. Let m(k, n, q) be the largest integer l for which there is a k-cross (n, q)-Parsons set of size l. The integer m(k, n, q) will be called the k-cross (n, q)-Parsons numbers. In this paper, we will show that m(3,2,q)≤q. Furthermore, m(3,2,q)=q if and only if q=4r for some positive integer r. We will also show that if n is a multiple of q-1, then m(q-1,n,q)≥q12n(n-1). [ABSTRACT FROM AUTHOR]

Let S n be the symmetric group on n -points. The k -point fixing graph F ( n , k ) is defined to be the graph with vertex set S n and two vertices g , h of F ( n , k ) are joined if and only if g h − 1 fixes exactly k points. In this paper, we give a recurrence formula for the eigenvalues of a class of regular subgraphs of F ( n , k ) . By using this recurrence formula, we will determine the smallest eigenvalues for this class of regular subgraphs of F ( n , 1 ) for sufficiently large n . [ABSTRACT FROM AUTHOR]

Let Z be the set of integers and Zl be the set of integers modulo l. A set L⊆T=Zl1×Zl2×⋯×Zlm is called a line if there exist a,b∈T such that L={a+tb∈T:t∈Z}. A set X⊆T is called a no-three-in-line set if |X∩L|≤2 for all the lines L in T. The maximum size of a no-three-in-line set is denoted by τT. Let m≥2 and k1,k2,…,km be positive integers such that gcd(ki,kj)=1 for all i, j with i≠j. In this paper, we will show that τZk1n×Zk2n×⋯×Zkmn≤2nm-1.We will give sufficient conditions for which the equality holds. When k1=k2=⋯=km=1 and n=pl where p is a prime and l≥1 is an integer, we will show that equality holds if and only if p=2 and l=1, i.e., τZpl×Zpl×⋯×Zpl=2pl(m-1) if and only if p=2 and l=1. [ABSTRACT FROM AUTHOR]

It was conjectured in the monograph [9] by Godsil and Meagher and in the article [10] by Lindzey that the perfect matching derangement graph M 2 n possesses the alternating sign property, that is, for any integer partition λ = (λ 1 , ... , λ r) ⊢ n , the sign of the eigenvalue η λ of M 2 n is given by sign (η λ) = (− 1) n − λ 1 . In this paper, we prove that the conjecture is true. Our approach yields a recurrence formula for the eigenvalues of the perfect matching derangement graph as well as a new recurrence formula for the eigenvalues of the permutation derangement graph. [ABSTRACT FROM AUTHOR]

Let S n be the symmetric group on [ n ] = { 1 , … , n } . The k -point fixing graph F ( n , k ) is defined to be the graph with vertex set S n such that two vertices g , h of F ( n , k ) are joined if and only if g h − 1 fixes exactly k points. In this paper, we show that for sufficiently large n in terms of k the smallest eigenvalue of F ( n , k ) occurs at the partition ( n − t 0 , t 0 ) where t 0 is the smallest positive integer satisfying ∑ r = 0 t 0 ( k r ) ( − 1 ) t 0 − r ( t 0 − r ) ! < 0 . It was conjectured by Ellis in Ellis (2014) that if A is an independent set in F ( n , k ) , then | A | ≤ ( n − k − 1 ) ! for sufficiently large n . Our result implies that | A | ≤ O k ( ( n − k − 1 2 ) ! ) for sufficiently large n . [ABSTRACT FROM AUTHOR]

Let S n be the symmetric group on { 1 , … , n } . The k -point fixing graph F ( n , k ) is defined to be the graph with vertex set S n and two vertices g , h of F ( n , k ) are joined if and only if g h − 1 fixes exactly k points. In this paper, we determine the smallest eigenvalue for F ( n , 1 ) . [ABSTRACT FROM AUTHOR]

Let S n denote the set of permutations of [ n ] = { 1 , 2 , … , n } . For a positive integer k , define S n , k to be the set of all permutations of [ n ] with exactly k disjoint cycles, i.e., S n , k = { π ∈ S n : π = c 1 c 2 ⋯ c k } , where c 1 , c 2 , … , c k are disjoint cycles. The size of S n , k is given by [ n k ] = ( − 1 ) n − k s ( n , k ) , where s ( n , k ) is the Stirling number of the first kind. A family A ⊆ S n , k is said to be t -cycle-intersecting if any two elements of A have at least t common cycles. A family A ⊆ S n , k is said to be trivially t -cycle-intersecting if A is the stabiliser of t fixed points, i.e., A consists of all permutations in S n , k with some t fixed cycles of length one. For 1 ≤ j ≤ t , let Q j = { σ ∈ S n , k : σ ( i ) = i for all i ∈ [ k ] ∖ { j } } . For t + 1 ≤ s ≤ k , let B s = { σ ∈ S n , k : σ ( i ) = i for all i ∈ [ t ] ∪ { s } } . In this paper, we show that, given any positive integers k , t with k ≥ 2 t + 3 , there exists an n 0 = n 0 ( k , t ) , such that for all n ≥ n 0 , if A ⊆ S n , k is non-trivially t -cycle-intersecting, then | A | ≤ | B | , where B = ⋃ s = t + 1 k B s ∪ ⋃ j = 1 t Q j . Furthermore, equality holds if and only if A is a conjugate of B , i.e., A = β − 1 B β for some β ∈ S n . [ABSTRACT FROM AUTHOR]

Let N 0 be the set of non-negative integers, and let P ( n , l ) denote the set of all weak compositions of n with l parts, i.e., P ( n , l ) = { ( x 1 , x 2 , … , x l ) ∈ N 0 l : x 1 + x 2 + ⋯ + x l = n } . For any element u = ( u 1 , u 2 , … , u l ) ∈ P ( n , l ) , denote its i th-coordinate by u ( i ) , i.e., u ( i ) = u i . Let l = min ( l 1 , l 2 , … , l r ) . Families A j ⊆ P ( n j , l j ) ( j = 1 , 2 , … , r ) are said to be r -cross t -intersecting if | { i ∈ [ l ] : u 1 ( i ) = u 2 ( i ) = ⋯ = u r ( i ) } | ≥ t for all u j ∈ A j . Suppose that l ≥ t + 2 . We prove that there exists a constant n 0 = n 0 ( l 1 , l 2 , … , l r , t ) depending only on l j ’s and t , such that for all n j ≥ n 0 , if the families A j ⊆ P ( n j , l j ) ( j = 1 , 2 , … , r ) are r -cross t -intersecting, then ∏ j = 1 r | A j | ≤ ∏ j = 1 r n j + l j − t − 1 l j − t − 1 . Moreover, equality holds if and only if there is a t -set T of { 1 , 2 , … , l } such that A j = { u ∈ P ( n j , l j ) : u ( i ) = 0 for all i ∈ T } for j = 1 , 2 , … , r . [ABSTRACT FROM AUTHOR]

Covering and packing problems constitute a class of questions concerning finite metric spaces that have surfaced in recent literature. In this paper, we consider, for the first time, these problems for the finite metric space ( Ω , d ) arising from the set Ω of 1 -factors of the complete t -uniform hypergraph H on n t vertices for some positive integers n and t . We focus on the covering problem; in particular we investigate bounds on the covering radius of any code C ⊆ Ω . In doing so, we give both upper and lower bounds on the covering radius, as well as a frequency parameter type result that follows from the Lovász local lemma. [ABSTRACT FROM AUTHOR]

Let S n be the symmetric group on [ n ] = { 1 , … , n } . The k -point fixing graph F ( n , k ) is defined to be the graph with vertex set S n and two vertices g , h of F ( n , k ) are joined if and only if g h − 1 fixes exactly k points. In this paper, we derive a recurrence formula for the eigenvalues of F ( n , k ) . Then we apply our result to determine the sign of the eigenvalues of F ( n , 1 ) . [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we prove the Gallai–Edmonds structure theorem for weighted matching polynomials. Our result implies the Parter–Wiener theorem and its recent generalization about the existence of principal submatrices of a Hermitian matrix whose graph is a tree. [Copyright &y& Elsevier]

Abstract: Let be the set of non-negative integers, and let denote the set of all weak compositions of with parts, i.e., . For any element , denote its th-coordinate by , i.e., . A family is said to be -intersecting if for all . We prove that given any positive integers with , there exists a constant depending only on and , such that for all , if is -intersecting then Moreover, the equality holds if and only if for some -set of . [Copyright &y& Elsevier]

Abstract: Let be the set of positive integers, and let be the set of (ordered) partitions of . We show that there exist a rank function and orderings and such that the ranked poset is Macaulay. [Copyright &y& Elsevier]

Abstract: A graph has a perfect matching if and only if is not a root of its matching polynomial . Thus, Tutte’s famous theorem asserts that is not a root of if and only if for all , where denotes the number of odd components of . Tutte’s theorem can be proved using a characterization of the structure of maximal non-matchable graphs, that is, the edge-maximal graphs among those having no perfect matching. In this paper, we prove a generalized version of Tutte’s theorem in terms of avoiding any given real number as a root of . We also extend maximal non-matchable graphs to maximal -non-matchable graphs and determine the structure of such graphs. [Copyright &y& Elsevier]

Abstract: Let denote the collection of all set partitions of . Suppose is a non-trivial t-intersecting family of set partitions i.e. any two members of have at least t blocks in common, but there is no fixed set of t blocks of size one which belong to all of them. It is proved that for sufficiently large n depending on t, where is the n-th Bell number and is the number of set partitions of without blocks of size one. Moreover, equality holds if and only if is equivalent to where . This is an analogue of the Hilton–Milner theorem for set partitions. [Copyright &y& Elsevier]

Abstract: We give a new recurrence formula for the eigenvalues of the derangement graph. Consequently, we provide a simpler proof of the Alternating Sign Property of the derangement graph. Moreover, we prove that the absolute value of the eigenvalue decreases whenever the corresponding partition with a fixed first part decreases in the dominance order. In particular, this settles affirmatively a conjecture of Ku and Wales [C.Y. Ku, D.B. Wales, Eigenvalues of the derangement graph, J. Combin. Theory Ser. A 117 (2010) 289–312] regarding the lower and upper bounds for the absolute values of these eigenvalues. [Copyright &y& Elsevier]

Abstract: Recently, Bauer et al. [D. Bauer, H.J. Broersma, A. Morgana, E. Schmeichel, Tutte sets in graphs I: maximal Tutte sets and -graphs, J. Graph Theory 55 (2007) 343–358] introduced a graph operator , called the -graph of , which has been useful in investigating the structural aspects of maximal Tutte sets in with a perfect matching. Among other results, they proved a characterization of maximal Tutte sets in terms of maximal independent sets in the graph and maximal extreme sets in . This was later extended to graphs without perfect matchings by Busch et al. [A. Busch, M. Ferrara, N. Kahl, Generalizing -graphs, Discrete Appl. Math. 155 (2007) 2487–2495]. Let be a real number and be the matching polynomial of a graph . Let be the multiplicity of as a root of . We observe that the notion of -graph is implicitly related to . In this paper, we give a natural generalization of the -graph of for any real number , and denote this new operator by , so that coincides with when . We prove a characterization of maximal -Tutte sets which are -analogues of maximal Tutte sets in . In particular, we show that for any , , and any real number , if and only if for any , , thus extending the preceding work of Bauer et al. (2007)  and Busch et al. (2007)  which established the result for the case . Subsequently, we show that every maximal -Tutte set is matchable to an independent set in ; moreover, always contains an isomorphic copy of the subgraph induced by . To this end, we introduce another related graph which is a supergraph of , and prove that and have the same Gallai–Edmonds decomposition with respect to . Moreover, we determine the structure of in terms of its Gallai–Edmonds decomposition and prove that . [Copyright &y& Elsevier]

Abstract: Let G be a permutation group acting on and be a system of n subsets of . When is there an element so that for each ? If such a g exists, we say that G has a G-marriage subject to . An obvious necessary condition is the orbit condition: for any nonempty subset Y of , there is an element such that the image of Y under g is contained in . Keevash observed that the orbit condition is sufficient when G is the symmetric group ; this is in fact equivalent to the celebrated Hall''s Marriage Theorem. We prove that the orbit condition is sufficient if and only if G is a direct product of symmetric groups. We extend the notion of orbit condition to that of k-orbit condition and prove that if G is the cyclic group where or G acts 2-transitively on , then G satisfies the -orbit condition subject to if and only if G has a G-marriage subject to . [Copyright &y& Elsevier]

Abstract: In matching theory, barrier sets (also known as Tutte sets) have been studied extensively due to their connection to maximum matchings in a graph. For a root of the matching polynomial, we define -barrier and -extreme sets. We prove a generalized Berge–Tutte formula and give a characterization for the set of all -special vertices in a graph. [ABSTRACT FROM AUTHOR]

Abstract: We consider the Cayley graph on the symmetric group generated by derangements. It is well known that the eigenvalues of this graph are indexed by partitions of n. We investigate how these eigenvalues are determined by the shape of their corresponding partitions. In particular, we show that the sign of an eigenvalue is the parity of the number of cells below the first row of the corresponding Ferrers diagram. We also provide some lower and upper bounds for the absolute values of these eigenvalues. [Copyright &y& Elsevier]

Abstract: Godsil observed the simple fact that the multiplicity of 0 as a root of the matching polynomial of a graph coincides with the classical notion of deficiency. From this fact he asked to what extent classical results in matching theory generalize, replacing “deficiency” with multiplicity of θ as a root of the matching polynomial. We prove an analogue of the Stability Lemma for any given root, which describes how the matching structure of a graph changes upon deletion of a single vertex. An analogue of Gallai''s Lemma follows. Together these two results imply an analogue of the Gallai–Edmonds Structure Theorem. Consequently, the matching polynomial of a vertex transitive graph has simple roots. [Copyright &y& Elsevier]

Abstract: Let denote the collection of all permutations of . Suppose is a family of permutations such that any two of its elements (when written in its cycle decomposition) have at least t cycles in common. We prove that for sufficiently large n, with equality if and only if is the stabilizer of t fixed points. Similarly, let denote the collection of all set partitions of and suppose is a family of set partitions such that any two of its elements have at least t blocks in common. It is proved that, for sufficiently large n, with equality if and only if consists of all set partitions with t fixed singletons, where is the nth Bell number. [Copyright &y& Elsevier]

In this paper, we prove Erdős-Ko-Rado type results for (a) family of set partitions where the size of each block is a multiple of k ; and (b) family of set partitions with minimum block size k. [ABSTRACT FROM AUTHOR]