Search results for "combinatoric"
showing 10 items of 1776 documents
On generalised FC-groups in which normality is a transitive relation
2016
We extend to soluble FC∗ -groups, the class of generalised FC-groups introduced in [F. de Giovanni, A. Russo, G. Vincenzi, Groups with restricted conjugacy classes , Serdica Math. J. 28(3) (2002), 241 254], the characterisation of finite soluble T-groups obtained recently in [G. Kaplan, On T-groups, supersolvable groups and maximal subgroups , Arch. Math. 96 (2011), 19 25].
Generalized Riesz systems and quasi bases in Hilbert space
2019
The purpose of this article is twofold. First of all, the notion of $(D, E)$-quasi basis is introduced for a pair $(D, E)$ of dense subspaces of Hilbert spaces. This consists of two biorthogonal sequences $\{ \varphi_n \}$ and $\{ \psi_n \}$ such that $\sum_{n=0}^\infty \ip{x}{\varphi_n}\ip{\psi_n}{y}=\ip{x}{y}$ for all $x \in D$ and $y \in E$. Secondly, it is shown that if biorthogonal sequences $\{ \varphi_n \}$ and $\{ \psi_n \}$ form a $(D ,E)$-quasi basis, then they are generalized Riesz systems. The latter play an interesting role for the construction of non-self-adjoint Hamiltonians and other physically relevant operators.
Circular law for sparse random regular digraphs
2020
Fix a constant $C\geq 1$ and let $d=d(n)$ satisfy $d\leq \ln^{C} n$ for every large integer $n$. Denote by $A_n$ the adjacency matrix of a uniform random directed $d$-regular graph on $n$ vertices. We show that, as long as $d\to\infty$ with $n$, the empirical spectral distribution of appropriately rescaled matrix $A_n$ converges weakly in probability to the circular law. This result, together with an earlier work of Cook, completely settles the problem of weak convergence of the empirical distribution in directed $d$-regular setting with the degree tending to infinity. As a crucial element of our proof, we develop a technique of bounding intermediate singular values of $A_n$ based on studyi…
Geometry and quasisymmetric parametrization of Semmes spaces
2014
We consider decomposition spaces R/G that are manifold factors and admit defining sequences consisting of cubes-with-handles. Metrics on R/G constructed via modular embeddings of R/G into Euclidean spaces promote the controlled topology to a controlled geometry. The quasisymmetric parametrizability of the metric space R/G×R by R for any m ≥ 0 imposes quantitative topological constraints, in terms of the circulation and the growth of the cubes-with-handles, to the defining sequences for R/G. We give a necessary condition and a sufficient condition for the existence of parametrization. The necessary condition answers negatively a question of Heinonen and Semmes on quasisymmetric parametrizabi…
Motzkin subposets and Motzkin geodesics in Tamari lattices
2014
The Tamari lattice of order n can be defined by the set D n of Dyck words endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we study this rotation on the restricted set of Motzkin words. An upper semimodular join semilattice is obtained and a shortest path metric can be defined. We compute the corresponding distance between two Motzkin words in this structure. This distance can also be interpreted as the length of a geodesic between these Motzkin words in a Tamari lattice. So, a new upper bound is obtained for the classical rotation distance between two Motzkin words in a Tamari lattice. For some specific pairs of Motzkin words, this b…
Gray code for permutations with a fixed number of cycles
2007
AbstractWe give the first Gray code for the set of n-length permutations with a given number of cycles. In this code, each permutation is transformed into its successor by a product with a cycle of length three, which is optimal. If we represent each permutation by its transposition array then the obtained list still remains a Gray code and this allows us to construct a constant amortized time (CAT) algorithm for generating these codes. Also, Gray code and generating algorithm for n-length permutations with fixed number of left-to-right minima are discussed.
On the Non-uniform Redundancy of Representations for Grammatical Evolution: The Influence of Grammars
2018
The representation used in grammatical evolution (GE) is non-uniformly redundant as some phenotypes are represented by more genotypes than others. This article studies how the non-uniform redundancy of the GE representation depends on various types of grammars. When constructing the phenotype tree from a genotype, the used grammar determines Bavg, the average branching factor. Bavg measures the expected number of non-terminals chosen when mapping one genotype codon to a phenotype tree node. First, the paper illustrates that the GE representation induces a bias towards small trees. This bias gets stronger with lower Bavg. For example, when using a grammar with Bavg = 0.5, 75% of all genotype…
Radio Labelings of Distance Graphs
2013
A radio $k$-labeling of a connected graph $G$ is an assignment $c$ of non negative integers to the vertices of $G$ such that $$|c(x) - c(y)| \geq k+1 - d(x,y),$$ for any two vertices $x$ and $y$, $x\ne y$, where $d(x,y)$ is the distance between $x$ and $y$ in $G$. In this paper, we study radio labelings of distance graphs, i.e., graphs with the set $\Z$ of integers as vertex set and in which two distinct vertices $i, j \in \Z$ are adjacent if and only if $|i - j| \in D$.
A trace partitioned Gray code forq-ary generalized Fibonacci strings
2015
AbstractWe provide a trace partitioned Gray code for the set of q-ary strings avoiding a pattern constituted by k consecutive equal symbols. The definition of this Gray code is based on two different constructions, according to the parity of q. This result generalizes, and is based on, a Gray code for binary strings avoiding k consecutive 0's.
Two Reflected Gray Code-Based Orders on Some Restricted Growth Sequences
2014
We consider two order relations: that induced by the m-ary reflected Gray code and a suffix partitioned variation of it. We show that both of them when applied to some sets of restricted growth sequences still yield Gray codes. These sets of sequences are: subexcedant and ascent sequences, restricted growth functions and staircase words. In particular, we give the first suffix partitioned Gray codes for restricted growth f unctions and ascent sequences; these latter sequences code various combinatorial classes as interval orders, upper triangular matrices without zero rows and zero columns whose non-negative integer entries sum up to n, and certain pattern-avoiding permutations. For each Gr…