Search

Let $R$ and $S$ be two sequences of positive integers in nonincreasing order having the same sum. We denote by ${\cal A}(R,S)$ the class of all $(0,1)$-matrices having row sum vector $R$ and column sum vector $S$. Brualdi and Deaett (More on the Bruhat order for $(0,1)$-matrices, Linear Algebra Appl., 421:219--232, 2007) suggested the study of the secondary Bruhat order on ${\cal A}(R,S)$ but with some constraints. In this paper, we study the cover relation and the minimal elements for this partial order relation, which we call the little secondary Bruhat order, on certain classes ${\cal A}(R,S)$. Moreover, we show that this order is different from the Bruhat order and the secondary Bruhat order. We also study a variant of this order on certain classes of symmetric matrices of ${\cal A}(R,S)$.

UIBD/MAT/00297/2020 In a previous paper, the authors introduced and studied the Bruhat order in the class of Latin squares of order n. In this paper, we investigate the restriction of the Bruhat order in a class of isotopic Latin squares. We present equivalent conditions for two Latin squares be related by the Bruhat order when one of them is obtained from the other by interchanging rows or columns or symbols. The cover relation is also addressed, and we present orthogonal isotopic Latin squares related by the Bruhat order. authorsversion published

UID/MAT/00297/2019 UID/MAT/04721/2019 We consider the class (Formula presented.) of symmetric (Formula presented.) -matrices with zero trace and constant row sums k which can be identified with the class of the adjacency matrices of k-regular undirected graphs. In a previous paper, two partial orders, the Bruhat and the Bruhat-graph order, have been introduced in this class. In fact, when k = 1 or k = 2, it was shown that the two orders coincide, while for (Formula presented.) the two orders are distinct. In this paper we give general properties of minimal and maximal matrices for these orders on (Formula presented.) and study the minimal and maximal matrices when k = 1, 2 or 3. publishersversion published

An abelian antipower of order k (or simply an abelian k-antipower) is a concatenation of k consecutive words of the same length having pairwise distinct Parikh vectors. This definition generalizes to the abelian setting the notion of a k-antipower, as introduced in Fici et al. (2018) [7] , that is a concatenation of k pairwise distinct words of the same length. We aim to study whether a word contains abelian k-antipowers for arbitrarily large k. S. Holub proved that all paperfolding words contain abelian powers of every order (Holub, 2013 [8] ). We show that they also contain abelian antipowers of every order.

Submitted by Isabel Melo (imelo@sa.isel.pt) on 2020-05-13T18:05:16Z No. of bitstreams: 1 Ranks_TMQuinteiro.pdf: 404654 bytes, checksum: db135bf332f766653a2b0e9c4e96ef20 (MD5) Made available in DSpace on 2020-05-13T18:05:16Z (GMT). No. of bitstreams: 1 Ranks_TMQuinteiro.pdf: 404654 bytes, checksum: db135bf332f766653a2b0e9c4e96ef20 (MD5) Previous issue date: 2019-04-19 info:eu-repo/semantics/publishedVersion

Let $$\mathcal {M}_{X(\mathbb {R})}$$ be the Banach algebra of all Fourier multipliers on a Banach function space $$X(\mathbb {R})$$ such that the Hardy–Littlewood maximal operator is bounded on $$X(\mathbb {R})$$ and on its associate space $$X'(\mathbb {R})$$ . For two sets $$\varPsi ,\varOmega \subset \mathcal {M}_{X(\mathbb {R})}$$ , let $$\varPsi _\varOmega$$ be the set of those $$c\in \varPsi$$ for which there exists $$d\in \varOmega$$ such that the multiplier norm of $$\chi _{\mathbb {R}\setminus [-N,N]}(c-d)$$ tends to zero as $$N\rightarrow \infty$$ . In this case, we say that the Fourier multiplier c is equivalent at infinity to the Fourier multiplier d. We show that if $$\varOmega$$ is a unital Banach subalgebra of $$\mathcal {M}_{X(\mathbb {R})}$$ consisting of nice Fourier multipliers (for instance, continuous or slowly oscillating in certain sense) and $$\varPsi$$ is an arbitrary unital Banach subalgebra of $$\mathcal {M}_{X(\mathbb {R})}$$ , then $$\varPsi _\varOmega$$ is a also a unital Banach subalgebra of $$\mathcal {M}_{X(\mathbb {R})}$$ .

In the theory of multiplicities for eigenvalues of symmetric matrices whose graph is a tree, it proved very useful to understand the change in status (Parter, neutral, or downer) of one vertex upon removal of another vertex of given status (both in case the two vertices are adjacent or non-adjacent). As the subject has evolved toward the study of more general matrices, over more general fields, with more general graphs, it is appropriate to resolve the same type of question in the more general settings. “Multiplicity” now means geometric multiplicity. Here, we give a complete resolution in three more general settings and compare these with the classical case (216 “Yes” or “No” results). As a consequence, several unexpected insights are recorded. authorsversion published

Let $G_{k}$ G k be a bouquet of circles, i.e., the quotient space of the interval $[0,k]$ [ 0 , k ] obtained by identifying all points of integer coordinates to a single point, called the branching point of $G_{k}$ G k . Thus, $G_{1}$ G 1 is the circle, $G_{2}$ G 2 is the eight space, and $G_{3}$ G 3 is the trefoil. Let $f: G_{k} \to G_{k}$ f : G k → G k be a continuous map such that, for $k>1$ k > 1 , the branching point is fixed.If $\operatorname{Per}(f)$ Per ( f ) denotes the set of periods of f, the minimal set of periods of f, denoted by $\operatorname{MPer}(f)$ MPer ( f ) , is defined as $\bigcap_{g\simeq f} \operatorname{Per}(g)$ ⋂ g ≃ f Per ( g ) where $g:G_{k}\to G_{k}$ g : G k → G k is homological to f.The sets $\operatorname{MPer}(f)$ MPer ( f ) are well known for circle maps. Here, we classify all the sets $\operatorname{MPer}(f)$ MPer ( f ) for self-maps of the eight space.

For an arbitrary set X and an equivalence relation $$\mu$$ on X, denote by $$P_\mu (X)$$ the semigroup of partial transformations $$\alpha$$ on X such that $$x\mu \subseteq x(\ker (\alpha ))$$ for every $$x\in {{\,\mathrm{dom}\,}}(\alpha )$$ , and the image of $$\alpha$$ is a partial transversal of $$\mu$$ . Every transversal K of $$\mu$$ defines a subgroup $$G=G_{K}$$ of $$P_\mu (X)$$ . We study subsemigroups $$\langle G,U\rangle$$ of $$P_\mu (X)$$ generated by $$G\cup U$$ , where U is any set of elements of $$P_\mu (X)$$ of rank less than $$|X/\mu |$$ . We show that each $$\langle G,U\rangle$$ is a regular semigroup, describe Green’s relations and ideals in $$\langle G,U\rangle$$ , and determine when $$\langle G,U\rangle$$ is an inverse semigroup and when it is a completely regular semigroup. For a finite set X, the top $$\mathcal {J}$$ -class J of $$P_\mu (X)$$ is a right group. We find formulas for the ranks of the semigroups J, $$G\cup I$$ , $$J\cup I$$ , and I, where I is any proper ideal of $$P_\mu (X)$$ .

FCT (UID/MAT/00212/2019) FCT (UID/MAT/00297/2019) Given two nonincreasing integral vectors R and S, with the same sum, we denote by A(R, S) the class of all (0,1)-matrices with row sum vector R, and column sum vector S. The Bruhat order and the Secondary Bruhat order on A(R, S) are both extensions of the classical Bruhat order on Sn, the symmetric group of degree n. These two partial orders on A(R, S) are, in general, different. In this paper we prove that if R = (2,2,…,2) or R = (1,1,…,1), then the Bruhat order and the Secondary Bruhat order on A(R, S) coincide. authorsversion published

We show that the Hardy-Littlewood maximal operator is bounded on a reflexive variable Lebesgue space $L^{p(\cdot)}$ over a space of homogeneous type $(X,d,\mu)$ if and only if it is bounded on its dual space $L^{p'(\cdot)}$, where $1/p(x)+1/p'(x)=1$ for $x\in X$. This result extends the corresponding result of Lars Diening from the Euclidean setting of $\mathbb{R}^n$ to the setting of spaces of homogeneous type $(X,d,\mu)$., Comment: Accepted for publication in Studia Mathematica

A zig-zag (or fence) order is a special partial order on a (finite) set. In this paper, we consider the semigroup $$\mathscr {TF}_{n}$$ of all order-preserving transformations on an n-element zig-zag-ordered set. We determine the rank of $$\mathscr {TF}_{n}$$ and provide a minimal generating set for $$ \mathscr {TF}_{n}$$ . Moreover, a formula for the number of idempotents in $$\mathscr {TF}_{n}$$ is given.

The cyclic shift graph of a monoid is the graph whose vertices are elements of the monoid and whose edges link elements that differ by a cyclic shift. This paper examines the cyclic shift graphs of `plactic-like' monoids, whose elements can be viewed as combinatorial objects of some type: aside from the plactic monoid itself (the monoid of Young tableaux), examples include the hypoplactic monoid (quasi-ribbon tableaux), the sylvester monoid (binary search trees), the stalactic monoid (stalactic tableaux), the taiga monoid (binary search trees with multiplicities), and the Baxter monoid (pairs of twin binary search trees). It was already known that for many of these monoids, connected components of the cyclic shift graph consist of elements that have the same evaluation (that is, contain the same number of each generating symbol). This paper focusses on the maximum diameter of a connected component of the cyclic shift graph of these monoids in the rank-$n$ case. For the hypoplactic monoid, this is $n-1$; for the sylvester and taiga monoids, at least $n-1$ and at most $n$; for the stalactic monoid, $3$ (except for ranks $1$ and $2$, when it is respectively $0$ and $1$); for the plactic monoid, at least $n-1$ and at most $2n-3$. The current state of knowledge, including new and previously-known results, is summarized in a table., Comment: 61 pages. Complete proofs of results previously announced in arXiv:1611.04152

The second author’s work was partially supported by the Fundação para a Ciência e a Tecnologia through the project UID/MAT/00297/2013 . The third author’s work was partially supported by the Fundação para a Ciência e a Tecnologia through the project UID/MAT/04721/2013 . We investigate two Bruhat (partial) orders on graphs with vertices labeled 1,2,…,n and with a specified degree sequence R, equivalently, symmetric (0,1)-matrices with zero trace and a specified row sum vector R (adjacency matrices of such graphs). One is motivated by the classical Bruhat order on permutations while the other one, more restrictive, is defined by a switch of a pair of disjoint edges. In the Bruhat order, one seeks to concentrate the edges of a graph with a given degree sequence among the vertices with smallest labels, thereby producing a minimal graph in this order. We begin with a discussion of graphs whose isomorphism class does not change under a switch. Then we are interested in when the two Bruhat orders are identical. For labeled graphs of regular degree k, we show that the two orders are identical for k≤2 but not for k=3. authorsversion published

The authors would like to thank anonymous referees for their helpful comments and suggestions which considerably improved the presentation of the paper. The authors except the third one were supported by Portuguese Funds through the Portuguese Foundation for Science and Technology (FCT). The first, second, and fifth authors were supported by FCT (Fundacao para a Ciencia e Tecnologia), under the project UIDB/04721/2020 (CEAFEL - Centro de Analise Funcional e Estruturas Lineares). The fourth author was supported within the scope of the project UIDB/00297/2020 (CMA - Centro de Matematica e Aplicacoes). This work was started in August 2017 while the third author was visiting CEAFEL at the Faculty of Sciences in the University of Lisbon. He is sincerely grateful to CEAFEL for the hospitality and support in August 2017 and March 2018. He also wishes to express his gratitude for the travel grant he received from the Institute for Research in Fundamental Sciences (IPM) in August 2017. A vertex v of the underlying graph of a symmetric matrix A is called ‘Parter’ if the nullity of the matrix obtained from A by removing the row and column indexed by v is more than the nullity of A. Let A be a singular symmetric matrix with rank r whose underlying graph is a tree. It is known that the number of Parter vertices of A is at most r−1. We prove that when r is odd this number is at most r−2. We characterize the trees where these bounds are achieved. authorsversion published

Foundation for Science and Technology (UID/MAT/00212/2013) Let p be a positive integer and let A((p)) (R, S) be the class of nonnegative integral matrices with entries less than or equal to p, with row-sum partition R, and column-sum partition S. In this paper we state a new necessary and sufficient condition for A((p)) (R, S) not equal empty set. This condition generalizes the well known Gale-Ryser theorem. We also present a canonical construction for matrices in A((p)) (R, S). authorsversion published

Let $\mathcal{E}(X,d,\mu)$ be a Banach function space over a space of homogeneous type $(X,d,\mu)$. We show that if the Hardy-Littlewood maximal operator $M$ is bounded on the space $\mathcal{E}(X,d,\mu)$, then its boundedness on the associate space $\mathcal{E}'(X,d,\mu)$ is equivalent to a certain condition $\mathcal{A}_\infty$. This result extends a theorem by Andrei Lerner from the Euclidean setting of $\mathbb{R}^n$ to the setting of spaces of homogeneous type., Comment: 17 pages

This paper makes a combinatorial study of the two monoids and the two types of tableaux that arise from the two possible generalizations of the Patience Sorting algorithm from permutations (or standard words) to words. For both types of tableaux, we present Robinson--Schensted--Knuth-type correspondences (that is, bijective correspondences between word arrays and certain pairs of semistandard tableaux of the same shape), generalizing two known correspondences: a bijective correspondence between standard words and certain pairs of standard tableaux, and an injective correspondence between words and pairs of tableaux. We also exhibit formulas to count both the number of each type of tableaux with given evaluations (that is, containing a given number of each symbol). Observing that for any natural number $n$, the $n$-th Bell number is given by the number of standard tableaux containing $n$ symbols, we restrict the previous formulas to standard words and extract a formula for the Bell numbers. Finally, we present a `hook length formula' that gives the number of standard tableaux of a given shape and deduce some consequences., Comment: 36 pages

Crystal graphs, in the sense of Kashiwara, carry a natural monoid structure given by identifying words labelling vertices that appear in the same position of isomorphic components of the crystal. In the particular case of the crystal graph for the $q$-analogue of the special linear Lie algebra $\mathfrak{sl}_{n}$, this monoid is the celebrated plactic monoid, whose elements can be identified with Young tableaux. The crystal graph and the so-called Kashiwara operators interact beautifully with the combinatorics of Young tableaux and with the Robinson--Schensted--Knuth correspondence and so provide powerful combinatorial tools to work with them. This paper constructs an analogous `quasi-crystal' structure for the hypoplactic monoid, whose elements can be identified with quasi-ribbon tableaux and whose connection with the theory of quasi-symmetric functions echoes the connection of the plactic monoid with the theory of symmetric functions. This quasi-crystal structure and the associated quasi-Kashiwara operators are shown to interact just as neatly with the combinatorics of quasi-ribbon tableaux and with the hypoplactic version of the Robinson--Schensted--Knuth correspondence. A study is then made of the interaction of the crystal graph of the plactic monoid and the quasi-crystal graph for the hypoplactic monoid. Finally, the quasi-crystal structure is applied to prove some new results about the hypoplactic monoid., Comment: 55 pages. Minor revision to fix typos, add references, and discuss an open question

This research was partially supported by the Fundacao de Ciencia e Tecnologia, and was undertaken within the "Centro de Estruturas Lineares e Combinatorias da Universidade de Lisboa". In previous work, the authors describe certain configurations which give rise to standard and to non-standard subgroups for linear recurrences of order k=2, while in subsequent work, a number of families of non-standard subgroups for recurrences of order k greater or equal to 2 are described. Here we exhibit two infinite families of standard groups for k greater or equal to 2. preprint published

The cyclic shift graph of a monoid is the graph whose vertices are elements of the monoid and whose edges link elements that differ by a cyclic shift. For certain monoids connected with combinatorics, such as the plactic monoid (the monoid of Young tableaux) and the sylvester monoid (the monoid of binary search trees), connected components consist of elements that have the same evaluation (that is, contain the same number of each generating symbol). This paper discusses new results on the diameters of connected components of the cyclic shift graphs of the finite-rank analogues of these monoids, showing that the maximum diameter of a connected component is dependent only on the rank. The proof techniques are explained in the case of the sylvester monoid., Comment: 12 pages. Substantial revision; survey of related results added

This paper considers whether non-trivial identities are satisfied by certain `plactic-like' monoids that, like the plactic monoid, are closely connected to combinatorics. New results show that the hypoplactic, sylvester, Baxter, stalactic, and taiga monoids satisfy identities, and indeed give shortest identities satisfied by these monoids. The existing state of knowledge is discussed for the plactic monoid and left and right patience sorting monoids., Comment: 19 pages. Minor updates and corrections

We consider the Moran process in a graph called the ``star'' and obtain the asymptotic expression for the fixation probability of a single mutant when the size of the graph is large. The expression obtained corrects the previously known expression announced in reference [E Lieberman, C Hauert, and MA Nowak. Evolutionary dynamics on graphs. Nature, 433(7023):312–316, 2005] and further studied in [M. Broom and J. Rychtar. An analysis of the fixation probability of a mutant on special classes of non-directed graphs. Proc. R. Soc. A-Math. Phys. Eng. Sci., 464(2098):2609–2627, 2008]. We also show that the star graph is an accelerator of evolution, if the graph is large enough. publishersversion published

The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree, M1, was understood fully (froma combinatorial perspective) by C.R. Johnson, A. Leal-Duarte (Linear Algebra and Multilinear Algebra 46 (1999) 139-144). Among the possible multiplicity lists for the eigenvalues of Hermitian matrices whose graph is a tree, we focus upon M2, the maximum value of the sum of the two largest multiplicities when the largest multiplicity is M1. Upper and lower bounds are given for M2. Using a combinatorial algorithm, cases of equality are computed for M2.

Work partially supported by the Sub-programa Ciência e Tecnologia do 2o Quadro Comunitário de Apoio (grant number BD/18012/98) and project POCTI/32440/MAT/2000 (CAUL) of FCT and FEDER. A transformation semigroup over a set X with N elements is said to be a near permutation semigroup if it is generated by a group of permutations on N elements and by a set of transformations of rank N −1. In this paper we make a summary of the author’s thesis, in which are exhibited ways of checking whether those specific transformation semigroups belong to various structural classes of semigroups, just by analysis of the generators and without first having to generate them. proof published

An important theorem about the existence of principal submatrices of a Hermitian matrixwhose graph is a tree, in which the multiplicity of an eigenvalue increases, was largely developed in separate papers by Parter and Wiener. Here, the prior work is fully stated, then generalized with a self-contained proof. The more complete result is then used to better understand the eigenvalue possibilities of reducible principal submatrices of Hermitian tridiagonal matrices. Sets of vertices, for which the multiplicity increases, are also studied. publishersversion published

Research supported in part by Fundação para a Ciência e a Tecnologia, Portugal, through the research grant SFRH/BD/899/2000. Part of the research was done while visiting the College of William and Mary. The maximum multiplicity among eigenvalues of matrices with a given graph cannot generally be expressed in terms of the degrees of the vertices (even when the graph is a tree). Given are best possible lower and upper bounds, and characterization of the cases of equality in these bounds. A by-product is a sequential algorithm to calculate the exact maximum multiplicity by simple counting. publishersversion published

Among those real symmetric matrices whose graph is a given tree $T$, the maximum multiplicity is known to be the path cover number of $T$. An explicit characterization is given for those trees for which whenever the maximum multiplicity is attained, all other multiplicities are $1$. publishersversion published

There is remarkable and distinctive structure among Hermitian matrices, whose graph is a given tree T and that have an eigenvalue of multiplicity that is a maximum for T. Among such structure, we give several new results: (1) no vertex of T may be "neutral"; (2) neutral vertices may occur if the largest multiplicity is less than the maximum; (3) every Parter vertex has at least two downer branches; (4) removal of a Parter vertex changes the status of no other vertex; and (5) every set of Parter vertices forms a Parter set. Statements (3), (4) and (5) are also not generally true when the multiplicity is less than the maximum. Some of our results are used to give further insights into prior results, and both the review of necessary background and the development of new structural lemmas may be of independent interest. http://www.sciencedirect.com/science/article/B6V0R-4SMF2K9-2/1/e80ee40f33898e52f517c5d58dbfa5bc