Search

Abstract: We show that paper-folding words contain arbitrarily large abelian powers. [Copyright &y& Elsevier]

Determining whether an irreducible representation of a group (or ⁎-algebra) admits a non-degenerate invariant, positive-definite Hermitian form is an important problem in representation theory. In this paper, we study the related notion of signatures. Let q ∈ C with | q | = 1 , κ = − 1 / c with c ∈ Q < 0 with certain additional (mild) restrictions, and n ∈ Z ≥ 2. We study representations S λ (q) of H n (q) , the Hecke algebra of type A n − 1 , and representations M κ (λ) of H κ , the rational Cherednik algebra of type A n − 1 , which have unique (up to scaling) invariant Hermitian forms (here λ is a partition of n). The signature is the number of elements with positive norm minus the number of elements with negative norm, and we analogously define the signature character in the case that there is a natural grading on the module. We provide formulas for (1) signatures of modules over H n (q) and (2) signature characters of modules over H κ. We study the limit c → − ∞ , in which case the signature character has a simpler form in terms of inversions and descents of permutations in S n. We provide examples corresponding to some special shapes, and small values of n. Finally, when q = e 2 π i c , we show that the asymptotic signature character of the H κ -module M κ (τ) is the signature of the H n (q) -module S τ (q). [ABSTRACT FROM AUTHOR]

Objectives: Professional sporting organisations invest considerable resources collecting and analysing data in order to better understand the factors that influence performance. Recent advances in non-invasive technologies, such as global positioning systems (GPS), mean that large volumes of data are now readily available to coaches and sport scientists. However analysing such data can be challenging, particularly when sample sizes are small and data sets contain multiple highly correlated variables, as is often the case in a sporting context. Multicollinearity in particular, if not treated appropriately, can be problematic and might lead to erroneous conclusions. In this paper we present a novel ‘leave one variable out’ (LOVO) partial least squares correlation analysis (PLSCA) methodology, designed to overcome the problem of multicollinearity, and show how this can be used to identify the training load (TL) variables that influence most ‘end fitness’ in young rugby league players. Methods: The accumulated TL of sixteen male professional youth rugby league players (17.7 ± 0.9 years) was quantified via GPS, a micro-electrical-mechanical-system (MEMS), and players’ session-rating-of-perceived-exertion (sRPE) over a 6-week pre-season training period. Immediately prior to and following this training period, participants undertook a 30–15 intermittent fitness test (30-15IFT), which was used to determine a players ‘starting fitness’ and ‘end fitness’. In total twelve TL variables were collected, and these along with ‘starting fitness’ as a covariate were regressed against ‘end fitness’. However, considerable multicollinearity in the data (VIF >1000 for nine variables) meant that the multiple linear regression (MLR) process was unstable and so we developed a novel LOVO PLSCA adaptation to quantify the relative importance of the predictor variables and thus minimise multicollinearity issues. As such, the LOVO PLSCA was used as a tool to inform and refine the MLR process. Results: The LOVO PLSCA identified the distance accumulated at very-high speed (>7 m·s-1) as being the most important TL variable to influence improvement in player fitness, with this variable causing the largest decrease in singular value inertia (5.93). When included in a refined linear regression model, this variable, along with ‘starting fitness’ as a covariate, explained 73% of the variance in v30-15IFT ‘end fitness’ (p<0.001) and eliminated completely any multicollinearity issues. Conclusions: The LOVO PLSCA technique appears to be a useful tool for evaluating the relative importance of predictor variables in data sets that exhibit considerable multicollinearity. When used as a filtering tool, LOVO PLSCA produced a MLR model that demonstrated a significant relationship between ‘end fitness’ and the predictor variable ‘accumulated distance at very-high speed’ when ‘starting fitness’ was included as a covariate. As such, LOVO PLSCA may be a useful tool for sport scientists and coaches seeking to analyse data sets obtained using GPS and MEMS technologies. [ABSTRACT FROM AUTHOR]

In this paper, a unique and more distinctive encryption algorithm is proposed. This is based on the complexity of highly nonlinear S box in Flesnelet domain. The nonlinear pattern is transformed further to enhance the confusion in the dummy data using Fresnelet technique. The security level of the encrypted image boosts using the algebra of Galois field in Fresnelet domain. At first level, the Fresnelet transform is used to propagate the given information with desired wavelength at specified distance. It decomposes given secret data into four complex subbands. These complex sub-bands are separated into two components of real subband data and imaginary subband data. At second level, the net subband data, produced at the first level, is deteriorated to non-linear diffused pattern using the unique S-box defined on the Galois field . In the diffusion process, the permuted image is substituted via dynamic algebraic S-box substitution. We prove through various analysis techniques that the proposed scheme enhances the cipher security level, extensively. [ABSTRACT FROM AUTHOR]

The 3D orientation of clasts within a deposit are known to be informative on processes that formed that deposit. In archaeological sites, a portion of the clasts in the deposit are introduced by non-geological processes, and these are typically systematically recorded in archaeological excavations with total stations. By recording a second point on elongated clasts it is possible to quickly and precisely capture their orientation. The statistical and graphical techniques for analyzing these data are well published, and there is a growing set of actualistic and archaeological comparative data to help with the interpretation of the documented patterns. This paper advances this area of research in presenting methods to address some shortcomings in current methodologies. First, a method for calculating confidence intervals on orientation statistics is presented to help address the question of how many objects are needed to assess the formation of a deposit based on orientations. Second, a method for assessing the probability that two assemblages have different orientations is presented based on permutations testing. This method differs from existing ones in that it considers three-dimensional orientations rather than working separately with the two-dimensional bearing and plunge components. Third, a method is presented to examine spatial variability in orientations based on a moving windows approach. The raw data plus the R code to build this document and to implement these methods plus those already described by McPherron are included to help further their use in assessing archaeological site formation processes. [ABSTRACT FROM AUTHOR]

Nous poursuivons ici le travail commencé dans (Enjalbert and Hoang Ngoc Minh, 2012) en décrivant des produits de mélanges d’algèbres de plus en plus “grandes” de fonctions spéciales (issues d’équations différentielles à pôles simples). Les étudier nous conduit à définir une classe de produits de mélange, que nous nommons φ -shuffles. Nous étudions cette classe d’un point de vue combinatoire, en commençant par étendre (sous conditions) le théorème de Radford à celle-ci, puis en construisant (toujours sous conditions) sa bigèbre. Nous analysons les conditions des résultats précités pour les simplifier en les rendant visible dès la définition du produit de mélange. Nous testons enfin ces conditions sur les produits introduits en début d’article. We carry on the investigation initiated in Enjalbert and Hoang Ngoc Minh (2012): we describe new shuffle products coming from some special functions and group them, along with other products encountered in the literature, in larger and larger classes of products, which we name φ -shuffle products. Our paper is dedicated to a study of the latter class, from a combinatorial standpoint. We consider first how to extend Radford’s theorem to the products in that class, then how to construct their bi-algebras. As some conditions are necessary to carry that out, we study them closely and simplify them so that they can be seen directly from the definition of the product. We eventually test these conditions on the products mentioned above. [ABSTRACT FROM AUTHOR]

Code-based cryptography is one of few alternatives supposed to be secure in a post-quantum world. Meanwhile, identity-based identification and signature (IBI/IBS) schemes are two of the most fundamental cryptographic primitives, so several code-based IBI/IBS schemes have been proposed. However, with increasingly profound researches on coding theory, the security reduction and efficiency of such schemes have been invalidated and challenged. In this paper, we construct provably secure IBI/IBS schemes from code assumptions against impersonation under active and concurrent attacks through a provably secure code-based signature technique proposed by Preetha, Vasant and Rangan (PVR signature), and a security enhancement Or-proof technique. We also present the parallel-PVR technique to decrease parameter values while maintaining the standard security level. Compared to other code-based IBI/IBS schemes, our schemes achieve not only preferable public parameter size, private key size, communication cost and signature length due to better parameter choices, but also provably secure. [ABSTRACT FROM AUTHOR]

This paper presents a geometric model of the Auslander–Reiten quiver of a type A quiver together with a stability function for which all indecomposable modules are stable. We also introduce a new Catalan object which we call a maximal almost rigid representation. We show that its endomorphism algebra is a tilted algebra of type A. We define a partial order on the set of maximal almost rigid representations and use our new geometric model to show that this partial order is a Cambrian lattice. [ABSTRACT FROM AUTHOR]

In [8] , G. Kyureghyan showed that the function F ( x ) = x + γ f ( x ) is a permutation of F q m when f : F q m → F q is a function, γ ∈ F q m is a b -linear translator for f for some b ( ≠ − 1 ) ∈ F q . His idea has been extended in [19] by Qin et al. and in [9] by M. Kyureghyan and Abrahamyan to finitely many function–linear translator pairs. In this paper, we study the permutations generated by function–linear translator pairs along G. Kyureghyan's idea and prove that these permutations form groups whose group structures are well understood. [ABSTRACT FROM AUTHOR]

In 1980, Lusztig introduced the periodic Kazhdan–Lusztig polynomials, which are conjectured to have important information about the characters of irreducible modules of a reductive group over a field of positive characteristic, and also about those of an affine Kac–Moody algebra at the critical level. The periodic Kazhdan–Lusztig polynomials can be computed by using another family of polynomials, called the periodic R -polynomials. In this paper, we prove a (closed) combinatorial formula expressing periodic R -polynomials in terms of the “doubled” Bruhat graph associated to a finite Weyl group and a finite root system. [ABSTRACT FROM AUTHOR]

In a general (k, n) scalable secret image sharing (SSIS) scheme, the secret image is shared by n participants and any k or more than k participants have the ability to reconstruct it. The scalability means that the amount of information in the reconstructed image scales in proportion to the number of the participants. In most existing SSIS schemes, the size of each image shadow is relatively large and the dealer does not has a flexible control strategy to adjust it to meet the demand of differen applications. Besides, almost all existing SSIS schemes are not applicable under noise circumstances. To address these deficiencies, in this paper we present a novel SSIS scheme based on a brand-new technique, called compressed sensing, which has been widely used in many fields such as image processing, wireless communication and medical imaging. Our scheme has the property of flexibility, which means that the dealer can achieve a compromise between the size of each shadow and the quality of the reconstructed image. In addition, our scheme has many other advantages, including smooth scalability, noise-resilient capability, and high security. The experimental results and the comparison with similar works demonstrate the feasibility and superiority of our scheme. [ABSTRACT FROM AUTHOR]

In a system that performs both encryption and lossy compression, the conventional way is to compress first and then encrypt the compressed data. This separation approach has been proved to be optimal. In certain applications where sensitive information should be protected as early as possible, it is preferable to perform the encryption first and then compress the encrypted data, which leads to the concept of the reversed system. Johnson et al. proposed an achievable scheme for the reversed system, where a modulo-sum encryption is followed by a compression using the Wyner–Ziv distributed source coding with side information. However, in general, this reversed system performs worse than the conventional system in the sense that it requires more compression rate and secrecy key rate. In this paper, we propose a new achievable scheme for the reversed system, where the encryption is conducted by a permutation cipher, and then, the encrypted data is compressed using the optimal rate-distortion code. The proposed scheme can achieve the optimal compression rate and secret key rate. As a result, we show that reversing the order of the encryption and compression does not necessarily compromise the performance of an encryption-compression system. We show that the proposed system attains strong secrecy, and the information leakage vanishes exponentially. [ABSTRACT FROM PUBLISHER]

Abstract: In a seminal paper (Alon and Tarsi, 1992 ), Alon and Tarsi have introduced an algebraic technique for proving upper bounds on the choice number of graphs (and thus, in particular, upper bounds on their chromatic number). The upper bound on the choice number of G obtained via their method, was later coined the Alon–Tarsi number of G and was denoted by (see e.g. Jensen and Toft (1995) ). They have provided a combinatorial interpretation of this parameter in terms of the eulerian subdigraphs of an appropriate orientation of G. Their characterization can be restated as follows. Let D be an orientation of G. Assign a weight to every subdigraph H of D: if is eulerian, then , otherwise . Alon and Tarsi proved that if and only if there exists an orientation D of G in which the out-degree of every vertex is strictly less than k, and moreover . Shortly afterwards (Alon, 1993 ), for the special case of line graphs of d-regular d-edge-colorable graphs, Alon gave another interpretation of , this time in terms of the signed d-colorings of the line graph. In this paper we generalize both results. The first characterization is generalized by showing that there is an infinite family of weight functions (which includes the one considered by Alon and Tarsi), each of which can be used to characterize . The second characterization is generalized to all graphs (in fact the result is even more general—in particular it applies to hypergraphs). We then use the second generalization to prove that holds for certain families of graphs G. Some of these results generalize certain known choosability results. [Copyright &y& Elsevier]

Abstract: A nonidentity automorphism of a graph is said to be semiregular if all of its orbits are of the same length. Given a graph with a semiregular automorphism , the quotient of relative to is the multigraph whose vertices are the orbits of and two vertices are adjacent by an edge with multiplicity if every vertex of one orbit is adjacent to vertices of the other orbit. We say that is an expansion of . In [J.D. Horton, I.Z. Bouwer, Symmetric -graphs and -graphs, J. Combin. Theory Ser. B 53 (1991) 114–129], Horton and Bouwer considered a restricted sort of expansions (which we will call ‘strong’ in this paper) where every leaf of expands to a single cycle in . They determined all cubic arc-transitive strong expansions of simple (1, 3)-trees, that is, trees with all of their vertices having valency 1 or 3, thus extending the classical result of Frucht, Graver and Watkins (see [R. Frucht, J.E. Graver, M.E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971) 211–218]) about arc-transitive strong expansions of (also known as the generalized Petersen graphs). In this paper another step is taken further by considering the possible structure of cubic vertex-transitive expansions of general (1,3)-multitrees (where vertices with double edges are also allowed); thus the restriction on every leaf to be expanded to a single cycle is dropped. [Copyright &y& Elsevier]

In our previous paper, we presented the combinatorial theory for minimal isostatic pinned frameworks–Assur graphs–which arise in the analysis of mechanical linkages. In this paper we further explore the geometric properties of Assur graphs, with a focus on singular realizations which have static self-stresses. We provide a new geometric characterization of Assur graphs, based on special singular realizations. These singular positions are then related to dead-end positions in which an associated mechanism with an inserted driver will stop or jam. [Copyright &y& Elsevier]

Abstract: This paper investigates a competitive version of the coloring game on a finite graph . An asymmetric variant of the -relaxed coloring game is called the -relaxed -coloring game. In this game, two players, Alice and Bob, take turns coloring the vertices of a graph , using colors from a set , with . On each turn Alice colors vertices and Bob colors vertices. A color is legal for an uncolored vertex if by coloring with color , the subgraph induced by all the vertices colored with has maximum degree at most . Each player is required to color an uncolored vertex legally on each move. The game ends when there are no remaining uncolored vertices. Alice wins the game if all vertices of the graph are legally colored, Bob wins if at a certain stage there exists an uncolored vertex without a legal color. The -relaxed -game chromatic number, denoted by , of is the least for which Alice has a winning strategy in the -relaxed -coloring game. The -relaxed -coloring game has been well studied and there are many interesting results. For the -relaxed -coloring game, this paper proves that if a graph has an orientation with maximum outdegree and , then for all ; If , then - for all . [Copyright &y& Elsevier]

Abstract: Partial cubes are isometric subgraphs of hypercubes. Structures on a graph defined by means of semicubes, and Djoković’s and Winkler’s relations play an important role in the theory of partial cubes. These structures are employed in the paper to characterize bipartite graphs and partial cubes of arbitrary dimension. New characterizations are established and new proofs of some known results are given. The operations of Cartesian product and pasting, and expansion and contraction processes are utilized in the paper to construct new partial cubes from old ones. In particular, the isometric and lattice dimensions of finite partial cubes obtained by means of these operations are calculated. [Copyright &y& Elsevier]

Abstract: A graph is claw-free if no vertex has three pairwise nonadjacent neighbours. In earlier papers of this series we proved that every claw-free graph either belongs to one of several basic classes that we described explicitly, or admits one of a few kinds of decomposition. In this paper we convert this “decomposition” theorem into a theorem describing the global structure of claw-free graphs. [Copyright &y& Elsevier]

Abstract: This paper discusses the game colouring number of partial k-trees and planar graphs. Let and denote the maximum game colouring number of partial k trees and the maximum game colouring number of planar graphs, respectively. In this paper, we prove that and . We also prove that the game colouring number of a graph is a monotone parameter, i.e., if is a subgraph of , then . [Copyright &y& Elsevier]

Abstract: The motivation for this paper is threefold. First, we study the connectivity properties of the homomorphism order of directed graphs, and more generally for relational structures. As opposed to the homomorphism order of undirected graphs (which has no non-trivial finite maximal antichains), the order of directed graphs has finite maximal antichains of any size. In this paper, we characterise explicitly all maximal antichains in the homomorphism order of directed graphs. Quite surprisingly, these maximal antichains correspond to generalised dualities. The notion of generalised duality is defined here in full generality as an extension of the notion of finitary duality, investigated in [J. Nešetřil, C. Tardif, Duality theorems for finite structures (characterising gaps and good characterisations), J. Combin. Theory Ser. B 80 (1) (2000) 80–97]. Building upon the results of the cited paper, we fully characterise the generalised dualities. It appears that these dualities are determined by forbidding homomorphisms from a finite set of forests (rather than trees). Finally, in the spirit of [A. Atserias, On digraph coloring problems and treewidth duality, in: Proceedings of the 21st IEEE Symposium on Logic in Computer Science, LICS’06, IEEE Computer Society, 2006; B. Larose, C. Loten, C. Tardif, A characterisation of first-order constraint satisfaction problems, in: Proceedings of the 21st IEEE Symposium on Logic in Computer Science, LICS’06, IEEE Computer Society, 2006; V. Dalmau, A. Krokhin, B. Larose, First-order definable retraction problems for posets and reflexive graphs, in: Proceedings of the 19th IEEE Symposium on Logic in Computer Science, LICS’04, IEEE Computer Society, 2004 ] we shall characterise “generalised” constraint satisfaction problems (defined also here) that are first-order definable. These are again just generalised dualities corresponding to finite maximal antichains in the homomorphism order. [Copyright &y& Elsevier]

Abstract: This paper is concerned with the Constraint Satisfaction Problem (CSP). It is well-known that the general CSP is NP-hard. However, there has been significant success in discovering subproblems which are tractable (polynomial time solvable). One of the most effective ways to obtain a tractable subproblem has been to force all of the constraint relations to lie in some tractable language. In this paper we define a new way of identifying tractable subproblems of the CSP. Let P be an arbitrary CSP instance and Γ be any tractable language. Suppose there exists, for each variable of P, a permutation of the domain such the resultant permuted constraint relations of P all lie in Γ. The domain permuted instance is then an instance of a tractable class and can be solved by the polynomial time algorithm for Γ. Solutions to P can be obtained by inverting the domain permutations. The question, for a given class of instances and language Γ, whether such a set of domain permutations can be found efficiently is the key to this method''s tractability. One of the important contributions made in this paper is the notion of a “lifted constraint instance” which is a powerful tool to study this question. [•] We consider the open problem of discovering domain permutations which make instances max-closed. We show that, for bounded arity instances over a Boolean domain this problem is tractable, while for domain size three it is intractable even for binary instances. [•] We give a simple proof verifying the tractability of discovering domain permutations which make instances row convex. We refute a published result by giving a simple proof of the intractability of discovering domain permutations which make instances, even with domain size four, connected row convex. [•] We demonstrate that triangulated and stable marriage instances are reducible, via domain permutations, to max-closed instances. This provides a simple explanation for arc consistency deciding these instances. [•] We verify with a simple direct proof the tractability of identification of renamable Horn instances, and the intractability of finding the largest renamable Horn subset of clauses of an instance of SAT. [•] We describe natural tractable classes which properly extend the maximal relational classes arising from tractable constraint languages. We believe that domain permutation reductions have a significant chance of being useful in practical applications. [Copyright &y& Elsevier]

Abstract: Let us call a digraph D cycle-connected if for every pair of vertices there exists a cycle containing both u and . In this paper we study the following open problem introduced by Ádám. Let D be a cycle-connected digraph. Does there exist a universal edge in D, i.e., an edge such that for every there exists a cycle C such that and ? In his 2001 paper Hetyei conjectured that cycle-connectivity always implies the existence of a universal edge. In the present paper we prove the conjecture of Hetyei for bitournaments. [Copyright &y& Elsevier]

In the paper, the solvability of the word problem and the conjugacy problem is proved for a wide class of finitely presented groups defined by periodic defining relations of a sufficiently large odd degree. In the proof, we use a certain simplified version of the classification of periodic words and transformations of these words, which was presented in detail in the author’s monograph devoted to the well-known Burnside problem. The result is completed by the proof of an interesting result of Sarkisyan on the existence of a group, given by defining relations of the form E = 1, for which the word problem is unsolvable. This result was first published in abstracts of papers of the 13th All-Union Algebra Symposium in Gomel in 1975. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we introduce an elliptic analogue of the generalized Dedekind–Rademacher sums which satisfy reciprocity laws. In these sums, Kronecker''s double series play a role of elliptic Bernoulli functions. This paper gives an answer to the problem of S. Fukuhara and N. Yui concerning the elliptic Apostol–Dedekind sums. We also mention a relation between the generating function of Kronecker''s double series and that of the (Debye) elliptic polylogarithms studied by A. Levin. [Copyright &y& Elsevier]

Abstract: This paper is the second part of a study devoted to the mutual exclusion scheduling problem. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. The cardinality of such a coloring is denoted by . When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be -hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender, K. Jansen, Restrictions of graph partition problems. Part I. Theoret. Comput. Sci. 148 (1995) 93–109]. In this paper, the problem is approached from a different point of view by studying a non-trivial and practical sufficient condition for optimality. In particular, the following proposition is demonstrated: if an interval graph G admits a coloring such that each color appears at least k times, then . This proposition is extended to several classes of graphs related to interval graphs. Moreover, all our proofs are constructive and provide efficient algorithms to solve the MES problem for these graphs, given a coloring satisfying the condition in input. [Copyright &y& Elsevier]

Abstract: The partially asymmetric exclusion process (PASEP) is an important model from statistical mechanics which describes a system of interacting particles hopping left and right on a one-dimensional lattice of n sites. It is partially asymmetric in the sense that the probability of hopping left is q times the probability of hopping right. Additionally, particles may enter from the left with probability α and exit from the right with probability β. In this paper we prove a close connection between the PASEP and the combinatorics of permutation tableaux. (These tableaux come indirectly from the totally nonnegative part of the Grassmannian, via work of Postnikov, and were studied in a paper of Steingrímsson and the second author.) Namely, we prove that in the long time limit, the probability that the PASEP is in a particular configuration τ is essentially the generating function for permutation tableaux of shape enumerated according to three statistics. The proof of this result uses a result of Derrida, Evans, Hakim, and Pasquier on the matrix ansatz for the PASEP model. As an application, we prove some monotonicity results for the PASEP. We also derive some enumerative consequences for permutations enumerated according to various statistics such as weak excedence set, descent set, crossings, and occurrences of generalized patterns. [Copyright &y& Elsevier]

Abstract: The authors showed in an earlier paper that there is a tree that displays, up to a natural equivalence, all non-trivial 3-separations of a 3-connected matroid. The purpose of this paper is to show that if certain natural conditions are imposed on the tree, then it has a uniqueness property. In particular, suppose that, from every pair of edges that meet at a degree-2 vertex and have their other ends of degree at least three, one edge is contracted. Then the resulting tree is unique. [Copyright &y& Elsevier]

Abstract: In two previous papers, the study of partitions with short sequences has been developed both for its intrinsic interest and for a variety of applications. The object of this paper is to extend that study in various ways. First, the relationship of partitions with no consecutive integers to a theorem of MacMahon and mock theta functions is explored independently. Secondly, we derive in a succinct manner a relevant definite integral related to the asymptotic enumeration of partitions with short sequences. Finally, we provide the generating function for partitions with no sequences of length K and part exceeding N. [Copyright &y& Elsevier]

Abstract: A graph G is said to be bicritical if has a perfect matching for every choice of a pair of points and . Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a fundamental solution method for the problems of steady three-dimensional Stokes flow past obstacles in a planar periodic array. The solutions of these problems are periodic functions which are difficult to be approximated by the conventional fundamental solution method. In the presented method, we approximate the solutions by linear combinations of the periodic fundamental solutions presented by Ishii. Some numerical examples are also included in this paper and their results make a good agreement with the ones of the previous works. [Copyright &y& Elsevier]

Abstract: Demetrovics et al [Design type problems motivated by database theory, J. Statist. Plann. Inference 72 (1998) 149–164] constructed a decomposition of the family of all k-element subsets of an n-element set into disjoint pairs where two such pairs are relatively far from each other in some sense. The paper invented a proof method using a Hamiltonian-type theorem. The present paper gives a generalization of this tool, hopefully extending the power of the method. Problems where the method could be also used are shown. Moreover, open problems are listed which are related to the Hamiltonian theory. In these problems a cyclic permutation is to be found when certain restrictions are given by a family of k-element subsets. [Copyright &y& Elsevier]

Abstract: This paper is devoted to the lower bounds on the maximum genus of graphs. A simple statement of our results in this paper can be expressed in the following form: Let G be a k-edge-connected graph with minimum degree , for each positive integer , there exists a non-decreasing function such that the maximum genus of G satisfies the relation , and furthermore that , where is the cycle rank of G. The result shows that lower bounds of the maximum genus of graphs with any given connectivity become larger and larger as their minimum degree increases, and complements recent results of several authors. [Copyright &y& Elsevier]

Abstract: In [Math. Mag. 64 (1991) 325–332], Schwenk has completely determined the set of all integers and for which the chessboard admits a closed knight''s tour. In this paper, (i) we consider the corresponding problem with the knight''s move generalized to -knight''s move (defined in the paper, Section 1). (ii) We then generalize a beautiful coloring argument of Pósa and Golomb to show that various chessboards do not admit closed generalized knight''s tour (Section 3). (iii) By focusing on the -knight''s move, we show that the chessboard does not have a closed generalized knight''s tour if and and determine almost completely which chessboards have a closed generalized knight''s tour (Section 4). In addition, (iv) we present a solution to the (standard) open knight''s tour problem (Section 2). [Copyright &y& Elsevier]

Abstract: We give a combinatorial proof of Harer and Zagier''s formula for the disjoint cycle distribution of a long cycle multiplied by an involution with no fixed points, in the symmetric group on a set of even cardinality. The main result of this paper is a direct bijection of a set , the enumeration of which is equivalent to the Harer–Zagier formula. The elements of are of the form , where is a pairing on , is a partition into k blocks of the same set, and a certain relation holds between and . (The set partitions that can appear in are called “shift-symmetric”, for reasons that are explained in the paper.) The direct bijection for identifies it with a set of objects of the form , where is a pairing on a -subset of (a “partial pairing”), and t is an ordered tree with k vertices. If we specialize to the extreme case when , then is empty, and our bijection reduces to a well-known tree bijection. [Copyright &y& Elsevier]

In a previous paper ([10]) the second author showed that if M is a pseudomanifold with complementarity other than the 6-vertex real projective plane and the 9-vertex complex projective plane, then M must have dimension ≥ 6, and--in case of equality--M must have exactly 12 vertices. In this paper we prove that such a 6-dimensional pseudomanifold does not exist. On the way to proving our main result we also prove that all combinatorial triangulations of the 4-sphere with at most 10 vertices are combinatorial 4-spheres. [ABSTRACT FROM AUTHOR]

Katerinis and Tsikopoulos (Graphs. Combin. 12 (1996) 327) give sufficient conditions for a regular bipartite graph to have a perfect matching excluding a set of edges. In this paper, we give a necessary and sufficient condition for a bipartite graph to have an f-factor containing a set of edges and excluding another set of edges and discuss some applications of this condition. In particular, we obtain some sufficient conditions related to connectivity and edge-connectivity for a bipartite (mf)-graph to have an f-factor with special properties and generalize the results in (Graphs. Combin. 12 (1996) 327). The results in this paper are in some sense best possible. [Copyright &y& Elsevier]

Let G be a simple graph with n vertices and m edges and Gc be its complement. Let δ(G)=δ and Δ(G)=Δ be the minimum degree and the maximum degree of vertices of G, respectively. In this paper, we present a sharp upper bound for the Laplacian spectral radius as follows:Equality holds if and only if G is a connected regular bipartite graph. Another result of the paper is an upper bound for the Laplacian spectral radius of the Nordhaus–Gaddum type. We prove that [Copyright &y& Elsevier]

In this paper, we realize the algebra of ℤ2 relations, signed partition algebras and partition algebras as tabular algebras and prove the cellularity of these algebras using the method of [2]. Using the results of Graham and Lehrer in [1], we give the modular representations of the algebra of ℤ2-relations, signed partition algebras and partition algebras. [ABSTRACT FROM AUTHOR]

In this paper we explicitly compute all Littlewood–Richardson coefficients for semisimple and Kac–Moody groups G , that is, the structure constants (also known as the Schubert structure constants ) of the cohomology algebra H ⁎ ( G / P , C ) , where P is a parabolic subgroup of G . These coefficients are of importance in enumerative geometry, algebraic combinatorics and representation theory. Our formula for the Littlewood–Richardson coefficients is purely combinatorial and is given in terms of the Cartan matrix and the Weyl group of G . However, if some off-diagonal entries of the Cartan matrix are 0 or −1, the formula may contain negative summands. On the other hand, if the Cartan matrix satisfies a i j a j i ≥ 4 for all i , j , then each summand in our formula is nonnegative that implies nonnegativity of all Littlewood–Richardson coefficients. We extend this and other results to the structure coefficients of the T -equivariant cohomology of flag varieties G / P and Bott–Samelson varieties Γ i ( G ) . [ABSTRACT FROM AUTHOR]

Let ℤn denote the ring of integers modulo n. A permutation of ℤn is a sequence of n distinct elements of ℤn. Addition and subtraction of two permutations is defined element-wise. In this paper we consider two extremal problems on permutations of ℤn, namely, the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is again a permutation, and the maximum size of a collection of permutations such that no sum of two distinct permutations in the collection is a permutation. Let the sizes be denoted by s(n) and t(n) respectively. The case when n is even is trivial in both the cases, with s(n) = 1 and t(n) = n!. For n odd, we prove (nφ(n))/2k ≤ s(n) ≤ n!·2-(n-1)/2/((n-1)/2)! and 2(n-1)/2·(n-1/2)! ≤ t(n) ≤ 2k · (n-1)!/φ(n), where k is the number of distinct prime divisors of n and φ is the Euler's totient function. [ABSTRACT FROM AUTHOR]

Contrary to the notion of a set or a tuple, a multiset is an unordered collection of elements which do not need to be different. As multisets are already widely used in combinatorics and computer science, the aim of this paper is to get on track to algebraic multiset theory. We consider generalizations of known results that hold for equivalence and order relations on sets and get several properties that are specific to multisets. Furthermore, we exemplify the novelty that brings this concept by showing that multisets are suitable to represent partial orders. Finally, after introducing the notion of an algebra on multisets, we prove that two algebras on multisets, whose root algebras are isomorphic, are in general not isomorphic. [ABSTRACT FROM AUTHOR]

In this paper we introduce some new identities in combinatoric. [ABSTRACT FROM AUTHOR]

In an earlier paper, we introduced the notion of full quivers of representations of algebras, which are more explicit than quivers of algebras. Here, we consider full quivers (as well as pseudo-quivers) as a combinatoric tool in order to describe PI-varieties of algebras. Each full quiver is naturally associated to a polynomial that encapsulates trace-like properties of the underlying algebra. [ABSTRACT FROM AUTHOR]

Abstract: The classic Cayley identity states that where is an matrix of indeterminates and is the corresponding matrix of partial derivatives. In this paper we present straightforward algebraic/combinatorial proofs of a variety of Cayley-type identities, both old and new. The most powerful of these proofs employ Grassmann algebra (=exterior algebra) and Grassmann–Berezin integration. Among the new identities proven here are a pair of “diagonal-parametrized” Cayley identities, a pair of “Laplacian-parametrized” Cayley identities, and the “product-parametrized” and “border-parametrized” rectangular Cayley identities. [Copyright &y& Elsevier]

Abstract: As real-time embedded systems become more complex, resource partitioning is increasingly used to guarantee real-time performance. Recently, several compositional frameworks of resource partitioning have been proposed using real-time scheduling theory with various notions of real-time tasks running under restricted resource supply environments. However, these real-time scheduling-based approaches are limited in their expressiveness in that, although capable of describing resource-demand tasks, they are unable to model resource supply. This paper describes a process algebraic framework PADSfor reasoning about resource demand and resource supply inspired by the timed process algebra ACSR. In ACSR, real-time tasks are specified by enunciating their consumption needs for resources. To also accommodate resource-supply processes in PADS, given a resource , we write to denote the availability of for a requesting task process. Using PADS, we define a supply-demand relation where a pair belongs to the relation if the demand process can be scheduled under supply . We develop a theory of compositional schedulability analysis as well as a technique for synthesizing an optimal supply process for a set of tasks. Furthermore, we define ordering relations between supplies which describe when a supply offers more resource capacity than another. With this notion it is possible to formally represent hierarchical scheduling approaches that assign more “generous” resource allocations to tasks in exchange for a simple representation. We illustrate our techniques via a number of examples. [Copyright &y& Elsevier]

Abstract: For a (molecular) graph, the first Zagreb index is equal to the sum of squares of the vertex degrees, and the second Zagreb index is equal to the sum of products of degrees of pairs of adjacent vertices. In this paper, we investigate Zagreb indices of bicyclic graphs with a given matching number. Sharp upper bounds for the first and second Zagreb indices of bicyclic graphs in terms of the order and given size of matching are determined, respectively. [Copyright &y& Elsevier]

The Hoffman-Singleton graph is the unique strongly regular graph with parameters (50, 7, 0, 1). A well-known hypothesis states that a distance-regular graph in which the neighborhood of each vertex is isomorphic to the Hoffman-Singleton graph has intersection array {50, 42, 1; 1, 2, 50} or {50, 42, 9; 1, 2, 42}. In the present paper, we prove this hypothesis under the assumption that a distance-regular graph is a Terwilliger graph and the graph diameter is at most 5. [ABSTRACT FROM AUTHOR]

Abstract: Recently, Deutsch and Elizalde have studied the largest and the smallest fixed points of permutations. Motivated by their work, we consider the analogous problems in set partitions. Let denote the number of partitions of with the largest singleton for . In this paper, several explicit formulas for , involving a Dobinski-type analog, are obtained by algebraic and combinatorial methods. Furthermore, many combinatorial identities involving and Bell numbers are presented by operator methods, and congruence properties of are also investigated. It is shown that the sequences and (mod ) are periodic for any prime , and contain a string of consecutive zeroes. Moreover their minimum periods are conjectured to be . [Copyright &y& Elsevier]

The problem of classifying all the avoidable binary patterns in (full) words has been completely solved (see Chap. 3 of M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, ). In this paper, we classify all the avoidable binary patterns in partial words, or sequences that may have some undefined positions called holes. In particular we show that, if we do not substitute any variable of the pattern by a partial word consisting of only one hole, the avoidability index of the pattern remains the same as in the full word case. [ABSTRACT FROM AUTHOR]

The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring problem from the point of view of split-coloring, such as criticality and the uniqueness of the minimum split-coloring. We discuss some properties of split-critical and uniquely split-colorable graphs. We describe constructions of such graphs with some additional properties. We also study the effect of the addition and the removal of some edge sets on the value of the split-chromatic number. All these results are compared with their cochromatic counterparts. We conclude with several research directions on the topic. [ABSTRACT FROM AUTHOR]