112 results
Search Results
2. A refinement of Wilf-equivalence for patterns of length 4.
- Author
-
Bloom, Jonathan
- Subjects
- *
EQUIVALENCE classes (Set theory) , *BIJECTIONS , *PERMUTATIONS , *MAXIMA & minima , *MATHEMATICAL analysis - Abstract
Abstract: In their paper [6], Dokos et al. conjecture that the major index statistic is equidistributed among 1423-avoiding, 2413-avoiding, and 3214-avoiding permutations. In this paper we confirm this conjecture by constructing two major index preserving bijections, and . In fact, we show that Θ (respectively, Ω) preserves numerous other statistics including the descent set, right-to-left maxima (respectively, left-to-right minima), and a statistic we call steps. Additionally, Θ (respectively, Ω) fixes all permutations avoiding both 1423 and 2413 (respectively, 3214 and 2413). [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
3. Combinatorial representations
- Author
-
Cameron, Peter J., Gadouleau, Maximilien, and Riis, Søren
- Subjects
- *
COMBINATORICS , *REPRESENTATIONS of algebras , *MATROIDS , *MATRICES (Mathematics) , *SET theory , *GRAPH theory , *MATHEMATICAL analysis - Abstract
Abstract: This paper introduces combinatorial representations, which generalise the notion of linear representations of matroids. We show that any family of subsets of the same cardinality has a combinatorial representation via matrices. We then prove that any graph is representable over all alphabets of size larger than some number depending on the graph. We also provide a characterisation of families representable over a given alphabet. Then, we associate a rank function and a closure operator to any representation which help us determine some criteria for the functions used in a representation. While linearly representable matroids can be viewed as having representations via matrices with only one row, we conclude this paper by an investigation of representations via matrices with only two rows. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
4. An explicit formula for ndinv, a new statistic for two-shuffle parking functions
- Author
-
Hicks, Angela and Kim, Yeonkyung
- Subjects
- *
MATHEMATICAL proofs , *PROBLEM solving , *EIGENANALYSIS , *MATHEMATICAL analysis , *FUNCTIONAL analysis , *OPERATOR theory , *LOGICAL prediction - Abstract
Abstract: In a recent paper, Duane, Garsia, and Zabrocki introduced a new statistic, “ndinv”, on a family of parking functions. The definition was guided by their study of a recursion on for a Macdonald eigenoperator, a modified Hall–Littlewood operator, and a composition of n. Using their newly introduced statistic, one can give a new interpretation for as a sum of parking functions counted by area and ndinv. This is a departure from the traditional sum, as stated by the shuffle conjecture, which q, t counts area and diagonal inversion number (dinv). Since their definition is necessarily recursive, they pose the problem of obtaining a non-recursive definition. In this paper, we solve this problem by giving an explicit formula for ndinv similar to the classical definition of dinv and prove it is equivalent to the ndinv of Duane, Garsia, and Zabrocki. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
5. Modified growth diagrams, permutation pivots, and the BWX map
- Author
-
Bloom, Jonathan and Saracino, Dan
- Subjects
- *
PERMUTATIONS , *MATHEMATICAL mappings , *EQUIVALENCE relations (Set theory) , *MATHEMATICAL transformations , *PROOF theory , *ALGORITHMS , *MATHEMATICAL analysis - Abstract
Abstract: In their paper on Wilf-equivalence for singleton classes, Backelin, West, and Xin introduced a transformation , defined by an iterative process and operating on (all) full rook placements on Ferrers boards. Bousquet-Mélou and Steingrímsson proved the analogue of the main result of Backelin, West, and Xin in the context of involutions, and in so doing they needed to prove that commutes with the operation of taking inverses. The proof of this commutation result was long and difficult, and Bousquet-Mélou and Steingrímsson asked if might be reformulated in such a way as to make this result obvious. In the present paper we provide such a reformulation of , by modifying the growth diagram algorithm of Fomin. This also answers a question of Krattenthaler, who noted that a bijection defined by the unmodified Fomin algorithm obviously commutes with inverses, and asked what the connection is between this bijection and . [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
6. Linear relations of refined enumerations of alternating sign matrices
- Author
-
Fischer, Ilse
- Subjects
- *
MATRICES (Mathematics) , *SET theory , *LINEAR systems , *NUMBER theory , *MATHEMATICAL analysis , *NUMERICAL analysis - Abstract
Abstract: In recent papers we have studied refined enumerations of alternating sign matrices with respect to a fixed set of top and bottom rows. The present paper is a first step towards extending these considerations to alternating sign matrices where in addition some left and right columns are fixed. The main result is a simple linear relation between the number of alternating sign matrices where the top row as well as the left and the right column is fixed and the number of alternating sign matrices where the two top rows and the bottom row are fixed. This may be seen as a first indication for the fact that the refined enumerations of alternating sign matrices with respect to a fixed set of top and bottom rows as well as left and right columns can possibly be reduced to the refined enumerations where only some top and bottom rows are fixed. For the latter numbers we provide a system of linear equations that conjecturally determines them uniquely. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
7. The existence of k-radius sequences
- Author
-
Blackburn, Simon R.
- Subjects
- *
MATHEMATICAL sequences , *MATCHING theory , *HYPERGRAPHS , *MATHEMATICAL functions , *MATHEMATICAL analysis , *NUMERICAL analysis - Abstract
Abstract: Let n and k be positive integers, and let F be an alphabet of size n. A sequence over F of length m is a k-radius sequence if any two distinct elements of F occur within distance k of each other somewhere in the sequence. These sequences were introduced by Jaromczyk and Lonc in 2004, in order to produce an efficient caching strategy when computing certain functions on large data sets such as medical images. Let be the length of the shortest n-ary k-radius sequence. The paper shows, using a probabilistic argument, that whenever k is fixed and The paper observes that the same argument generalises to the situation when we require the following stronger property for some integer t such that : any t distinct elements of F must simultaneously occur within a distance k of each other somewhere in the sequence. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
8. Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs.
- Author
-
Ergemlidze, Beka, Győri, Ervin, and Methuku, Abhishek
- Subjects
- *
HYPERGRAPHS , *ASYMPTOTIC distribution , *EDGES (Geometry) , *LINEAR statistical models , *MATHEMATICAL analysis - Abstract
Abstract Let F be a family of 3-uniform linear hypergraphs. The linear Turán number of F is the maximum possible number of edges in a 3-uniform linear hypergraph on n vertices which contains no member of F as a subhypergraph. In this paper we show that the linear Turán number of the five cycle C 5 (in the Berge sense) is 1 3 3 n 3 / 2 asymptotically. We also show that the linear Turán number of the four cycle C 4 and { C 3 , C 4 } are equal asymptotically, which is a strengthening of a theorem of Lazebnik and Verstraëte [16]. We establish a connection between the linear Turán number of the linear cycle of length 2 k + 1 and the extremal number of edges in a graph of girth more than 2 k − 2. Combining our result and a theorem of Collier-Cartaino, Graber and Jiang [8] , we obtain that the linear Turán number of the linear cycle of length 2 k + 1 is Θ (n 1 + 1 k ) for k = 2 , 3 , 4 , 6. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
9. On a biased edge isoperimetric inequality for the discrete cube.
- Author
-
Ellis, David, Keller, Nathan, and Lifshitz, Noam
- Subjects
- *
ISOPERIMETRIC inequalities , *GENERALIZATION , *MONOTONE operators , *MATHEMATICAL models , *MATHEMATICAL analysis - Abstract
Abstract The 'full' edge isoperimetric inequality for the discrete cube { 0 , 1 } n (due to Harper, Lindsey, Berstein and Hart) specifies the minimum size of the edge boundary ∂ A of a set A ⊂ { 0 , 1 } n , as function of | A |. A weaker (but more widely-used) lower bound is | ∂ A | ≥ | A | log (2 n / | A |) , where equality holds whenever A is a subcube. In 2011, the first author obtained a sharp 'stability' version of the latter result, proving that if | ∂ A | ≤ | A | (log (2 n / | A |) + ϵ) , then there exists a subcube C such that | A Δ C | / | A | = O (ϵ / log (1 / ϵ)). The 'weak' version of the edge isoperimetric inequality has the following well-known generalization for the ' p -biased' measure μ p on the discrete cube: if p ≤ 1 / 2 , or if 0 < p < 1 and A is monotone increasing, then p μ p (∂ A) ≥ μ p (A) log p (μ p (A)). In this paper, we prove a sharp stability version of the latter result, which generalizes the aforementioned result of the first author. Namely, we prove that if p μ p (∂ A) ≤ μ p (A) (log p (μ p (A)) + ϵ) , then there exists a subcube C such that μ p (A Δ C) / μ p (A) = O (ϵ ′ / log (1 / ϵ ′)) , where ϵ ′ : = ϵ ln (1 / p). This result is a central component in recent work of the authors proving sharp stability versions of a number of Erdős–Ko–Rado type theorems in extremal combinatorics, including the seminal 'complete intersection theorem' of Ahlswede and Khachatrian. In addition, we prove a biased-measure analogue of the 'full' edge isoperimetric inequality, for monotone increasing sets, and we observe that such an analogue does not hold for arbitrary sets, hence answering a question of Kalai. We use this result to give a new proof of the 'full' edge isoperimetric inequality, one relying on the Kruskal–Katona theorem. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
10. The asymptotic existence of group divisible designs of large order with index one
- Author
-
Mohácsy, Hedvig
- Subjects
- *
DIVISIBILITY groups , *ASYMPTOTES , *EXISTENCE theorems , *ALGEBRAIC number theory , *GROUP theory , *MATHEMATICAL analysis - Abstract
Abstract: This paper gives the answer to a question of R.M. Wilson regarding the existence of group divisible designs of large order. Let k and u be positive integers such that . Then there exists an integer such that there exists a group divisible design of group type with block size k and index one for any integer satisfying the necessary arithmetic conditions [1.] , [2.] . This paper also presents a large-index asymptotic existence theorem for group divisible t-designs with a fixed number of groups, fixed group size and fixed block size. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
11. An existence theorem for group divisible 3-designs of large order
- Author
-
Mohácsy, Hedvig
- Subjects
- *
EXISTENCE theorems , *ORDERED groups , *MATHEMATICAL analysis , *MATHEMATICAL proofs , *COMBINATORICS , *MATHEMATICAL research - Abstract
Abstract: In this paper we establish an asymptotic existence result for group divisible 3-designs of large order. Let k and u be positive integers, . Then there exists an integer such that there exists a group divisible 3-design of group type with block size k and index one for all integers if and only if [1.] , [2.] , [3.] . An analogous theorem was proved by Mohácsy and Ray-Chaudhuri for group divisible 2-designs in a previously published paper in 2002. The case of this theorem gives an asymptotic existence result for transversal 3-designs which was proved by Blanchard in his unpublished manuscript as well. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
12. Some remarks on Euclidean tight designs
- Author
-
Hirao, Masatake, Sawa, Masanori, and Zhou, Yuanyuan
- Subjects
- *
EUCLIDEAN algorithm , *DIMENSIONAL analysis , *WEYL groups , *DESIGN , *MATHEMATICAL analysis , *PRODUCT attributes - Abstract
Abstract: In this paper we present a new 4-dimensional tight Euclidean 5-design on 3 concentric spheres, together with a list of all known tight Euclidean designs which has been updated since the last survey paper by Bannai and Bannai (2009) . We also examine whether each of all known tight Euclidean designs has the structure of a coherent configuration. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
13. Optimal and perfect difference systems of sets
- Author
-
Ding, Cunsheng
- Subjects
- *
NONLINEAR functional analysis , *SET theory , *SYNCHRONIZATION , *NONLINEAR theories , *MATHEMATICAL analysis , *MATHEMATICS - Abstract
Abstract: Difference systems of sets (DSS) were introduced in 1971 by Levenstein for the construction of codes for synchronization, and are closely related to cyclic difference families. In this paper, algebraic constructions of difference systems of sets using functions with optimum nonlinearity are presented. All the difference systems of sets constructed in this paper are perfect and optimal. One conjecture on difference systems of sets is also presented. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
14. Equipartitions of a mass in boxes
- Author
-
Vrećica, Siniša T.
- Subjects
- *
PARTITIONS (Mathematics) , *HOMOLOGY theory , *TOPOLOGY , *COMBINATORICS , *INDEX theory (Mathematics) , *MATHEMATICAL analysis - Abstract
Abstract: The aim of this paper is to provide the sufficient condition for a mass distribution in to admit an equipartition with a collection of hyperplanes some of which are parallel. The results extend the previously obtained results for the equipartitions with non-parallel hyperplanes. (See [P. Mani-Levitska, S. Vrećica, R. Živaljević, Topology and combinatorics of partitions of masses by hyperplanes, Adv. Math. 207 (2006) 266–296; E.A. Ramos, Equipartitions of mass distributions by hyperplanes, Discrete Comput. Geom. 15 (1996) 147–167].) The paper also serves as the illustration of the applicability and the power of the methods of equivariant topology (more precisely, equivariant index theory) in the problems of geometric combinatorics. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
15. Integrals, partitions and MacMahon's Theorem
- Author
-
Andrews, George, Eriksson, Henrik, Petrov, Fedor, and Romik, Dan
- Subjects
- *
GENERATING functions , *COMBINATORICS , *ALGEBRA , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2007
- Full Text
- View/download PDF
16. Enumeration of partitions with prescribed successive rank parity blocks.
- Author
-
Seo, Seunghyun and Yee, Ae Ja
- Subjects
- *
LISTS , *PARTITIONS (Mathematics) , *NUMERICAL analysis , *MATHEMATICAL analysis , *NUMBER theory - Abstract
Successive ranks of a partition, which were introduced by Atkin, are the difference of the lengths of the i -th row and the i -th column in the Ferrers graph. Recently, in the study of singular overpartitions, Andrews revisited successive ranks and parity blocks. Motivated by his work, we investigate partitions with prescribed successive rank parity blocks. The main result of this paper is the generating function of partitions with exactly d successive ranks and m parity blocks. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
17. Permutation groups and derangements of odd prime order.
- Author
-
Burness, Timothy C. and Giudici, Michael
- Subjects
- *
PERMUTATIONS , *QUASIVARIETIES (Universal algebra) , *GRAPH theory , *PARTITIONS (Mathematics) , *MATHEMATICAL analysis - Abstract
Let G be a transitive permutation group of degree n . We say that G is 2′-elusive if n is divisible by an odd prime, but G does not contain a derangement of odd prime order. In this paper we study the structure of quasiprimitive and biquasiprimitive 2′-elusive permutation groups, extending earlier work of Giudici and Xu on elusive groups. As an application, we use our results to investigate automorphisms of finite arc-transitive graphs of prime valency. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
18. “K-theoretic” analog of Postnikov–Shapiro algebra distinguishes graphs.
- Author
-
Nenashev, Gleb and Shapiro, Boris
- Subjects
- *
K-theory , *GRAPH theory , *ISOMORPHISM (Mathematics) , *GENERALIZATION , *MATHEMATICAL analysis - Abstract
In this paper we study a filtered “ K -theoretical” analog of a graded algebra associated to any loopless graph G which was introduced in [5] . We show that two such filtered algebras are isomorphic if and only if their graphs are isomorphic. We also study a large family of filtered generalizations of the latter graded algebra which includes the above “ K -theoretical” analog. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
19. Point-primitive generalised hexagons and octagons.
- Author
-
Bamberg, John, Glasby, S.P., Popiel, Tomasz, Praeger, Cheryl E., and Schneider, Csaba
- Subjects
- *
HEXAGONS , *OCTAGONS , *LIE groups , *PERMUTATION groups , *MATHEMATICAL analysis , *GENERALIZABILITY theory - Abstract
The only known examples of finite generalised hexagons and octagons arise from the finite almost simple groups of Lie type G 2 , D 4 3 , and F 4 2 . These groups act transitively on flags, primitively on points, and primitively on lines. The best converse result prior to the writing of this paper was that of Schneider and Van Maldeghem (2008): if a group G acts flag-transitively, point-primitively, and line-primitively on a finite generalised hexagon or octagon, then G is an almost simple group of Lie type. We strengthen this result by showing that the same conclusion holds under the sole assumption of point-primitivity. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
20. Four-dimensional polytopes of minimum positive semidefinite rank.
- Author
-
Gouveia, João, Pashkovich, Kanstanstin, Robinson, Richard Z., and Thomas, Rekha R.
- Subjects
- *
POLYTOPES , *COMBINATORICS , *MATRICES (Mathematics) , *SET theory , *MATHEMATICAL analysis - Abstract
The positive semidefinite (psd) rank of a polytope is the size of the smallest psd cone that admits an affine slice that projects linearly onto the polytope. The psd rank of a d -polytope is at least d + 1 , and when equality holds we say that the polytope is psd-minimal. In this paper we develop new tools for the study of psd-minimality and use them to give a complete classification of psd-minimal 4-polytopes. The main tools introduced are trinomial obstructions, a new algebraic obstruction for psd-minimality, and the slack ideal of a polytope, which encodes the space of realizations of a polytope up to projective equivalence. Our central result is that there are 31 combinatorial classes of psd-minimal 4-polytopes. We provide combinatorial information and an explicit psd-minimal realization in each class. For 11 of these classes, every polytope in them is psd-minimal, and these are precisely the combinatorial classes of the known projectively unique 4-polytopes. We give a complete characterization of psd-minimality in the remaining classes, encountering in the process counterexamples to some open conjectures. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
21. The mathematics of lecture hall partitions.
- Author
-
Savage, Carla D.
- Subjects
- *
AUDITORIUMS , *POLYHEDRAL functions , *MODULAR functions , *COMBINATORICS , *MATHEMATICAL analysis - Abstract
Over the past twenty years, lecture hall partitions have emerged as fundamental combinatorial structures, leading to new generalizations and interpretations of classical theorems and new results. In recent years, geometric approaches to lecture hall partitions have used polyhedral geometry to discover further properties of these rich combinatorial objects. In this paper we give an overview of some of the surprising connections that have surfaced in the process of trying to understand the lecture hall partitions. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
22. A Topological Representation Theorem for tropical oriented matroids.
- Author
-
Horn, Silke
- Subjects
- *
TOPOLOGICAL spaces , *ORIENTED matroids , *LINEAR systems , *MATHEMATICAL proofs , *MATHEMATICAL analysis - Abstract
Tropical oriented matroids were defined by Ardila and Develin in 2007. They are a tropical analogue of classical oriented matroids in the sense that they encode the properties of the types of points in an arrangement of tropical hyperplanes — in much the same way as the covectors of “classical” oriented matroids describe the types in arrangements of linear hyperplanes. Ardila and Develin proved that tropical oriented matroids can be represented as mixed subdivisions of dilated simplices. In this paper we show that this correspondence is a bijection. Moreover, tropical analogues for the Topological Representation Theorem for “classical” oriented matroids by Folkman and Lawrence are presented. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
23. On the maximum number of Latin transversals.
- Author
-
Glebov, Roman and Luria, Zur
- Subjects
- *
NUMBER theory , *TRANSVERSAL lines , *MATHEMATICAL proofs , *MATHEMATICAL analysis , *MAGIC squares , *ORTHOGONAL functions - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
24. On judicious partitions of uniform hypergraphs.
- Author
-
Hou, Jianfeng, Wu, Shufei, and Yan, Guiying
- Subjects
- *
PARTITIONS (Mathematics) , *HYPERGRAPHS , *SET theory , *MATHEMATICAL proofs , *MATHEMATICAL analysis - Abstract
Bollobás and Scott showed that the vertices of a graph of m edges can be partitioned into k sets such that each set contains at most m / k 2 + o ( m ) edges. They conjectured that the vertices of an r -uniform hypergraph, where r ≥ 3 , of m edges may likewise be partitioned into k sets such that each set contains at most m / k r + o ( m ) edges. In this paper, we prove the weaker statement that a partition into k sets can be found in which each set contains at most m ( k − 1 ) r + r 1 / 2 ( k − 1 ) r / 2 + o ( m ) edges. Some partial results on this conjecture are also given. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
25. Littlewood–Richardson rules for symmetric skew quasisymmetric Schur functions.
- Author
-
Bessenrodt, Christine, Tewari, Vasu, and van Willigenburg, Stephanie
- Subjects
- *
SYMMETRIC functions , *QUASISYMMETRIC groups , *SCHUR functions , *COEFFICIENTS (Statistics) , *COMBINATORICS , *MATHEMATICAL analysis - Abstract
The classical Littlewood–Richardson rule is a rule for computing coefficients in many areas, and comes in many guises. In this paper we prove two Littlewood–Richardson rules for symmetric skew quasisymmetric Schur functions that are analogous to the famed version of the classical Littlewood–Richardson rule involving Yamanouchi words. Furthermore, both our rules contain this classical Littlewood–Richardson rule as a special case. We then apply our rules to combinatorially classify symmetric skew quasisymmetric Schur functions. This answers affirmatively a conjecture of Bessenrodt, Luoto and van Willigenburg. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
26. Uniform and Bernoulli measures on the boundary of trace monoids.
- Author
-
Abbes, Samy and Mairesse, Jean
- Subjects
- *
BERNOULLI equation , *MONOIDS , *COMPUTER science , *POLYNOMIALS , *MATHEMATICAL analysis - Abstract
Trace monoids and heaps of pieces appear in various contexts in combinatorics. They also constitute a model used in computer science to describe the executions of asynchronous systems. The design of a natural probabilistic layer on top of the model has been a long standing challenge. The difficulty comes from the presence of commuting pieces and from the absence of a global clock. In this paper, we introduce and study the class of Bernoulli probability measures that we claim to be the simplest adequate probability measures on infinite traces. For this, we strongly rely on the theory of trace combinatorics with the Möbius polynomial in the key role. These new measures provide a theoretical foundation for the probabilistic study of concurrent systems. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
27. Studying the singularity of LCM-type matrices via semilattice structures and their Möbius functions.
- Author
-
Haukkanen, Pentti, Mattila, Mika, and Mäntysalo, Jori
- Subjects
- *
LOWEST common multiple , *MATRICES (Mathematics) , *SEMILATTICES , *MATHEMATICAL functions , *MATHEMATICAL analysis - Abstract
The invertibility of Least Common Multiple (LCM) matrices and their Hadamard powers have been extensively studied over the years by many authors. Bourque and Ligh conjectured in 1992 that the LCM matrix [ S ] = [ [ x i , x j ] ] on any GCD closed set S = { x 1 , x 2 , … , x n } is invertible, but in 1997 this was proven to be false. Nevertheless, many open conjectures concerning LCM matrices and their Hadamard powers remain. In this paper we utilize lattice-theoretic structures and the Möbius function to explain the singularity of classical LCM matrices and their Hadamard powers. As a result we disprove some open conjectures of Hong. Elementary mathematical analysis is applied to prove that for most semilattice structures there exists a set S = { x 1 , x 2 , … , x n } of positive integers and a real number α > 0 such that S possesses this structure and the power LCM matrix [ [ x i , x j ] α ] is singular. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
28. The behavior of Stanley depth under polarization.
- Author
-
Ichim, B., Katthän, L., and Moyano-Fernández, J.J.
- Subjects
- *
BREWSTER'S angle , *PROBLEM solving , *MATHEMATICAL analysis , *GROUP theory , *MATHEMATICAL functions - Abstract
Let K be a field, R = K [ X 1 , … , X n ] be the polynomial ring and J ⊊ I be two monomial ideals in R . In this paper we show that sdepth I / J − depth I / J = sdepth I p / J p − depth I p / J p , where sdepth I / J denotes the Stanley depth and I p denotes the polarization. This solves a conjecture by Herzog [9] and reduces the famous Stanley conjecture (for modules of the form I / J ) to the squarefree case. As a consequence, the Stanley conjecture for algebras of the form R / I and the well-known combinatorial conjecture that every Cohen–Macaulay simplicial complex is partitionable are equivalent. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
29. On forbidden submatrices.
- Author
-
Méroueh, Arès
- Subjects
- *
MATRICES (Mathematics) , *MATHEMATICAL analysis , *FIXED point theory , *SET theory , *MATHEMATICS - Abstract
Given a k × l ( 0 , 1 ) -matrix F , we denote by fs ( m , F ) the largest number for which there is an m × fs ( m , F ) ( 0 , 1 ) -matrix with no repeated columns and no induced submatrix equal to F . A conjecture of Anstee, Frankl, Füredi and Pach states that, regarding F as fixed, fs ( m , F ) = O ( m k ) . The main results of this paper are that for k = 2 , fs ( m , F ) = O ( m 2 + o m ( 1 ) ) and for k ≥ 3 that fs ( m , F ) = O ( m ( 5 / 3 ) k − 1 + o m ( 1 ) ) . [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
30. Proofs of two conjectures on truncated series.
- Author
-
Mao, Renrong
- Subjects
- *
MATHEMATICAL proofs , *LOGICAL prediction , *MATHEMATICAL series , *JACOBI identity , *MATHEMATICAL analysis - Abstract
In this paper, we prove two conjectures on truncated series. The first conjecture made by G.E. Andrews and M. Merca is related to Jacobi's triple product identity, while the second conjecture by V.J.W. Guo and J. Zeng is related to Jacobi's identity. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
31. On crown-free families of subsets.
- Author
-
Lu, Linyuan
- Subjects
- *
SET theory , *MATHEMATICAL proofs , *MATHEMATICAL analysis , *HASSE diagrams , *GRAPHIC methods for partially ordered sets - Abstract
Abstract: The crown is a height-2 poset whose Hasse diagram is a cycle of length 2t. A family of subsets of is -free if is not a weak subposet of . Let be the largest size of -free families of subsets of . De Bonis–Katona–Swanepoel proved . Griggs and Lu proved that for all even . In this paper, we prove for all odd . [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
32. A polynomial embedding of pairs of orthogonal partial Latin squares.
- Author
-
Donovan, Diane M. and ?ule Yaz?c?, Emine
- Subjects
- *
EMBEDDINGS (Mathematics) , *ORTHOGONAL polynomials , *MAGIC squares , *MATHEMATICAL analysis , *PARTIAL algebras - Abstract
Abstract: We show that a pair of orthogonal partial Latin squares of order n can be embedded in a pair of orthogonal Latin squares of order at most and all orders greater than or equal to . This paper provides the first direct polynomial order embedding construction for pairs of orthogonal partial Latin squares. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
33. Proof of Blum's conjecture on hexagonal dungeons.
- Author
-
Ciucu, Mihai and Lai, Tri
- Subjects
- *
TILING (Mathematics) , *MATHEMATICAL proofs , *NUMBER theory , *MATHEMATICAL analysis , *ABSTRACT algebra - Abstract
Abstract: Matt Blum conjectured that the number of tilings of the hexagonal dungeon of sides a, 2a, b, a, 2a, b (where ) is (Propp, 1999 [4]). In this paper we present a proof for this conjecture using Kuo's Graphical Condensation Theorem (Kuo, 2004 [2]). [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
34. On transversals of quasialgebraic families of sets.
- Author
-
Chelnokov, G.R. and Dol'nikov, V.L.
- Subjects
- *
SET theory , *GENERALIZATION , *INFINITY (Mathematics) , *FINITE fields , *MATHEMATICAL analysis - Abstract
Abstract: The main results of this paper are generalizations of some classical theorems about transversals for families of finite sets to some cases of families of infinite sets. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
35. Half-arc-transitive group actions with a small number of alternets.
- Author
-
Hujdurović, Ademir, Kutnar, Klavdija, and Marušič, Dragan
- Subjects
- *
MULTIPLY transitive groups , *NUMBER theory , *EQUIVALENCE classes (Set theory) , *GRAPH theory , *MATHEMATICAL analysis - Abstract
Abstract: A graph X is said to be G-half-arc-transitive if acts transitively on the set of vertices of X and on the set of edges of X but does not act transitively on the set of arcs of X. Such graphs can be studied via corresponding alternets, that is, equivalence classes of the so-called reachability relation, first introduced by Cameron, Praeger and Wormald (1993) in [5]. If the vertex sets of two adjacent alternets either coincide or have half of their vertices in common the graph is said to be tightly attached. In this paper graphs admitting a half-arc-transitive group action with at most five alternets are considered. In particular, it is shown that if the number of alternets is at most three, then the graph is necessarily tightly attached, but there exist graphs with four and graphs with five alternets which are not tightly attached. The exceptional graphs all admit a partition giving the rose window graph on 12 vertices as a quotient graph in case of four alternets, and a particular graph on 20 vertices in the case of five alternets. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
36. On balanced incomplete block designs with specified weak chromatic number.
- Author
-
Horsley, Daniel and Pike, David A.
- Subjects
- *
BLOCK designs , *MATHEMATICAL analysis , *NUMBER theory , *STRUCTURAL colors , *EXISTENCE theorems , *COMBINATORICS - Abstract
Abstract: A weak c-colouring of a balanced incomplete block design (BIBD) is a colouring of the points of the design with c colours in such a way that no block of the design has all of its vertices receive the same colour. A BIBD is said to be weakly c-chromatic if c is the smallest number of colours with which the design can be weakly coloured. In this paper we show that for all and with , the obvious necessary conditions for the existence of a -BIBD are asymptotically sufficient for the existence of a weakly c-chromatic -BIBD. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
37. Linking systems in nonelementary abelian groups.
- Author
-
Davis, James A., Martin, William J., and Polhill, John B.
- Subjects
- *
PARTIAL differential equations , *ABELIAN groups , *MATHEMATICAL analysis , *GROUP theory , *GROUP algebras , *DIFFERENTIAL equations - Abstract
Abstract: Linked systems of symmetric designs are equivalent to 3-class Q-antipodal association schemes. Only one infinite family of examples is known, and this family has interesting origins and is connected to important applications. In this paper, we define linking systems, collections of difference sets that correspond to systems of linked designs, and we construct linking systems in a variety of nonelementary abelian groups using Galois rings, partial difference sets, and a product construction. We include some partial results in the final section. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
38. Cayley compositions, partitions, polytopes, and geometric bijections.
- Author
-
Konvalinka, Matjaž and Pak, Igor
- Subjects
- *
CAYLEY graphs , *GEOMETRIC analysis , *POLYTOPES , *POLYNOMIALS , *MATHEMATICAL analysis , *HYPERSPACE - Abstract
Abstract: In 1857, Cayley showed that certain sequences, now called Cayley compositions, are equinumerous with certain partitions into powers of 2. In this paper we give a simple bijective proof of this result and a geometric generalization to equality of Ehrhart polynomials between two convex polytopes. We then apply our results to give a new proof of Braunʼs conjecture proved recently by the authors [15]. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
39. Resolvability of infinite designs.
- Author
-
Danziger, Peter, Horsley, Daniel, and Webb, Bridget S.
- Subjects
- *
INFINITE element method , *ORTHOGONAL functions , *MATHEMATICAL analysis , *NUMERICAL analysis , *FINITE element method , *FOURIER analysis - Abstract
Abstract: In this paper we examine the resolvability of infinite designs. We show that in stark contrast to the finite case, resolvability for infinite designs is fairly commonplace. We prove that every t- design with t finite, v infinite and is resolvable and, in fact, has α orthogonal resolutions for each . We also show that, while a t- design with t and λ finite, v infinite and may or may not have a resolution, any resolution of such a design must have v parallel classes containing v blocks and at most parallel classes containing fewer than v blocks. Further, a resolution into parallel classes of any specified sizes obeying these conditions is realisable in some design. When and and when and λ is infinite, we give various examples of resolvable and non-resolvable t- designs. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
40. Generalized frieze pattern determinants and higher angulations of polygons.
- Author
-
Bessenrodt, Christine, Holm, Thorsten, and Jørgensen, Peter
- Subjects
- *
POLYGONS , *COXETER graphs , *ALGORITHMS , *MATHEMATICAL analysis , *MATRICES (Mathematics) , *MATHEMATICAL models - Abstract
Abstract: Frieze patterns (in the sense of Conway and Coxeter) are in close connection to triangulations of polygons. Broline, Crowe and Isaacs have assigned a symmetric matrix to each polygon triangulation and computed the determinant. In this paper we consider d-angulations of polygons and generalize the combinatorial algorithm for computing the entries in the associated symmetric matrices; we compute their determinants and the Smith normal forms. It turns out that both are independent of the particular d-angulation, the determinant is a power of , and the elementary divisors only take values and 1. We also show that in the generalized frieze patterns obtained in our setting every adjacent -determinant is 0 or 1, and we give a combinatorial criterion for when they are 1, which in the case gives back the Conway–Coxeter condition on frieze patterns. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
41. An improved bound on the existence of Cameron–Liebler line classes.
- Author
-
Metsch, Klaus
- Subjects
- *
MATHEMATICAL bounds , *COMBINATORICS , *EXISTENCE theorems , *SET theory , *PARAMETER estimation , *MATHEMATICAL analysis - Abstract
Abstract: In this paper it is shown that there exists a constant such that there do not exist Cameron–Liebler line classes in with parameter x satisfying . This improves all known bounds except for small values of q. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
42. On the number of spanning trees of some irregular line graphs.
- Author
-
Yan, Weigen
- Subjects
- *
SPANNING trees , *MATHEMATICAL analysis , *MATHEMATICAL proofs , *NUMBER systems , *GROUP theory - Abstract
Abstract: Let G be a graph with n vertices and m edges and Δ and δ the maximum degree and minimum degree of G. Suppose is the graph obtained from G by attaching pendent edges to each vertex v of G. It is well known that if G is regular (i.e., , ), then the line graph of G, denoted by , has spanning trees, where is the number of spanning trees of G. In this paper, we prove that if G is irregular (i.e., ), then , where s is the number of vertices of degree one in . [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
43. Covering and packing for pairs.
- Author
-
Chee, Yeow Meng, Colbourn, Charles J., Ling, Alan C.H., and Wilson, Richard M.
- Subjects
- *
COMBINATORIAL packing & covering , *SET theory , *MATHEMATICAL bounds , *DIVISIBILITY groups , *MATHEMATICAL analysis - Abstract
Abstract: When a v-set can be equipped with a set of k-subsets so that every 2-subset of the v-set appears in exactly (or at most, or at least) one of the chosen k-subsets, the result is a balanced incomplete block design (or packing, or covering, respectively). For each k, balanced incomplete block designs are known to exist for all sufficiently large values of v that meet certain divisibility conditions. When these conditions are not met, one can ask for the packing with the most blocks and/or the covering with the fewest blocks. Elementary necessary conditions furnish an upper bound on the number of blocks in a packing and a lower bound on the number of blocks in a covering. In this paper it is shown that for all sufficiently large values of v, a packing and a covering on v elements exist whose numbers of blocks differ from the basic bounds by no more than an additive constant depending only on k. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
44. The Rogers–Ramanujan–Gordon identities, the generalized Göllnitz–Gordon identities, and parity questions.
- Author
-
Kim, Sun and Yee, Ae Ja
- Subjects
- *
ROGERS-Ramanujan identities , *GENERALIZATION , *PARTITIONS (Mathematics) , *MATHEMATICS theorems , *MATHEMATICAL analysis , *NUMERICAL analysis - Abstract
Recently, George Andrews investigated a variety of parity questions in classical partition identities. In particular, he involved parity restrictions in the Rogers–Ramanujan–Gordon identities. In this paper, we reveal the relationship of his results with Bressoudʼs generalization of the Rogers–Ramanujan–Gordon identities. In addition, Andrews observed that one case of his identities is related to the Göllnitz–Gordon identities. In the light of the fact that the Göllnitz–Gordon identities are special cases of a general partition theorem of Andrews, we extend Andrewsʼ identities by generalizing his observation. We also provide a generating function of the missing case of his identities. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
45. A complete solution to the two-table Oberwolfach problems.
- Author
-
Traetta, Tommaso
- Subjects
- *
PROBLEM solving , *NUMBER theory , *GRAPH theory , *PATHS & cycles in graph theory , *MATHEMATICAL analysis , *NUMERICAL analysis - Abstract
Abstract: Even though the Oberwolfach problem has been solved for infinitely many orders, no complete solution is known when the number t of tables is fixed, except for . In this paper we solve all Oberwolfach problems (even those with ) with two table lengths. The fundamental step consists of proving Frucht and Salinasʼ conjecture on the gracefulness of a graph that is a vertex-disjoint union of a cycle and a path. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
46. Minimal external representations of tropical polyhedra
- Author
-
Allamigeon, Xavier and Katz, Ricardo D.
- Subjects
- *
POLYHEDRA , *CONES , *COMBINATORICS , *MATHEMATICAL analysis , *INTERSECTION theory , *POLYTOPES - Abstract
Abstract: Tropical polyhedra are known to be representable externally, as intersections of finitely many tropical half-spaces. However, unlike in the classical case, the extreme rays of their polar cones provide external representations containing in general superfluous half-spaces. In this paper, we prove that any tropical polyhedral cone in (also known as “tropical polytope” in the literature) admits an essentially unique minimal external representation. The result is obtained by establishing a (partial) anti-exchange property of half-spaces. Moreover, we show that the apices of the half-spaces appearing in such non-redundant external representations are vertices of the cell complex associated with the polyhedral cone. We also establish a necessary condition for a vertex of this cell complex to be the apex of a non-redundant half-space. It is shown that this condition is sufficient for a dense class of polyhedral cones having “generic extremities”. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
47. Large sets of Kirkman triple systems and related designs
- Author
-
Chang, Yanxun and Zhou, Junling
- Subjects
- *
SET theory , *SYSTEM analysis , *PROBLEM solving , *COMBINATORIAL designs & configurations , *GEOMETRICAL constructions , *MATHEMATICAL analysis - Abstract
Abstract: The problem of the existence of large sets of Kirkman triple systems (LKTS) is one of the most celebrated open problems in design theory. Only a few sparsely distributed infinite classes have been determined, although LKTS have been investigated by many authors. The purpose of this paper is to survey constructions and results on LKTS and related designs. A systematic account of this work is provided. Most of the known constructions are unified and generalized; the approaches to LKTS are enriched; a couple of new constructions for related designs are also displayed. In particular, a new existence class of LKTS is demonstrated and some new results of overlarge sets of Kirkman triple systems are also produced. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
48. On diamond-free subposets of the Boolean lattice
- Author
-
Kramer, Lucas, Martin, Ryan R., and Young, Michael
- Subjects
- *
PARTIALLY ordered sets , *BOOLEAN algebra , *LATTICE theory , *MATHEMATICAL proofs , *DIMENSIONAL analysis , *MATHEMATICAL analysis - Abstract
Abstract: The Boolean lattice of dimension two, also known as the diamond, consists of four distinct elements with the following property: . A diamond-free family in the n-dimensional Boolean lattice is a subposet such that no four elements form a diamond. Note that elements B and C may or may not be related. There is a diamond-free family in the n-dimensional Boolean lattice of size . In this paper, we prove that any diamond-free family in the n-dimensional Boolean lattice has size at most . Furthermore, we show that the so-called Lubell function of a diamond-free family in the n-dimensional Boolean lattice which contains the empty set is at most , which is asymptotically best possible. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
49. Inversion-descent polynomials for restricted permutations
- Author
-
Chung, Fan and Graham, Ron
- Subjects
- *
MATRIX inversion , *POLYNOMIALS , *GENERATING functions , *ALGEBRAIC varieties , *PERMUTATIONS , *EULER'S numbers , *MATHEMATICAL analysis - Abstract
Abstract: We derive generating functions for a variety of distributions of joint permutation statistics all of which involve a bound on the maximum drop size of a permutation π, i.e., . Our main result treats the case for the joint distribution of the number of inversions, the number of descents and the maximum drop size of permutations on . A special case of this (ignoring the number of inversions) connects with earlier work of Claesson, Dukes and the authors on descent polynomials for permutations with bounded drop size. In that paper, the desired numbers of permutations were given by sampling the coefficients of certain polynomials . We find a natural interpretation of all the coefficients of the in terms of a restricted version of Eulerian numbers. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
50. Abelian returns in Sturmian words
- Author
-
Puzynina, Svetlana and Zamboni, Luca Q.
- Subjects
- *
ABELIAN groups , *DYNAMICAL systems , *SYMBOLIC computation , *RECURSIVE sequences (Mathematics) , *PERIODIC functions , *MATHEMATICAL analysis - Abstract
Abstract: Return words constitute a powerful tool for studying symbolic dynamical systems. They may be regarded as a discrete analogue of the first return map in dynamical systems. In this paper we investigate two abelian variants of the notion of return word, each of them gives rise to a new characterization of Sturmian words. We prove that a recurrent infinite word is Sturmian if and only if each of its factors has two or three abelian (or semi-abelian) returns. We study the structure of abelian returns in Sturmian words and give a characterization of those factors having exactly two abelian returns. Finally we discuss connections between abelian returns and periodicity in words. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.