Search results for "Combinatorics"
showing 10 items of 1770 documents
Periodicity and repetitions in parameterized strings
2008
AbstractOne of the most beautiful and useful notions in the Mathematical Theory of Strings is that of a Period, i.e., an initial piece of a given string that can generate that string by repeating itself at regular intervals. Periods have an elegant mathematical structure and a wealth of applications [F. Mignosi and A. Restivo, Periodicity, Algebraic Combinatorics on Words, in: M. Lothaire (Ed.), Cambridge University Press, Cambridge, pp. 237–274, 2002]. At the hearth of their theory, there are two Periodicity Lemmas: one due to Lyndon and Schutzenberger [The equation aM=bNcP in a free group, Michigan Math. J. 9 (1962) 289–298], referred to as the Weak Version, and the other due to Fine and …
Embedding finite linear spaces in projective planes, II
1987
Abstract It is shown that a finite linear space with maximal point degree n + 1 can be embedded in a projective plane of order n, provided that the line sizes are big enough.
PI-algebras with slow codimension growth
2005
Let $c_n(A),\ n=1,2,\ldots,$ be the sequence of codimensions of an algebra $A$ over a field $F$ of characteristic zero. We classify the algebras $A$ (up to PI-equivalence) in case this sequence is bounded by a linear function. We also show that this property is closely related to the following: if $l_n(A), \ n=1,2,\ldots, $ denotes the sequence of colengths of $A$, counting the number of $S_n$-irreducibles appearing in the $n$-th cocharacter of $A$, then $\lim_{n\to \infty} l_n(A)$ exists and is bounded by $2$.
Finite linear spaces in which any n-gon is euclidean
1986
Abstract An n-gon of a linear space is a set S of n points no three of which are collinear. By a diagonal point of S we mean a point p off S with the property that at least two lines through p intersect S in two points. The number of diagonal points is called the type of S. For example, a 4-gon has at most three diagonal points. We call an n-gon euclidean if (roughly speaking) it contains the maximal possible number of 4-gons of type 3. In this paper, we characterize all finite linear spaces in which, for a fixed number n ⩾ 5, any n-gon is euclidean. It turns out that these structures are essentially projective spaces or punctured projective spaces.
Spatial reasoning withRCC8and connectedness constraints in Euclidean spaces
2014
The language RCC 8 is a widely-studied formalism for describing topological arrangements of spatial regions. The variables of this language range over the collection of non-empty, regular closed sets of n-dimensional Euclidean space, here denoted RC + ( R n ) , and its non-logical primitives allow us to specify how the interiors, exteriors and boundaries of these sets intersect. The key question is the satisfiability problem: given a finite set of atomic RCC 8 -constraints in m variables, determine whether there exists an m-tuple of elements of RC + ( R n ) satisfying them. These problems are known to coincide for all n � 1 , so that RCC 8 -satisfiability is independent of dimension. This c…
Subgroups of $$SF(\omega )$$ S F ( ω ) and the relation of almost containedness
2016
The relations of almost containedness and orthogonality in the lattice of groups of finitary permutations are studied in the paper. We define six cardinal numbers naturally corresponding to these relations by the standard scheme of $$P(\omega )$$P(ź). We obtain some consistency results concerning these numbers and some versions of the Ramsey theorem.
Logics with counting and equivalence
2014
We consider the two-variable fragment of first-order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NEXPTIME-complete. We further show that the corresponding problems for two-variable first-order logic with counting and two equivalences are both undecidable.
Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound
2014
In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends on. This is a generalisation of the Bernstein-Vazirani problem (when h is the XOR function) and the combinatorial group testing problem (when h is the OR function). We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (compl…
Time-Efficient Quantum Walks for 3-Distinctness
2013
We present two quantum walk algorithms for 3-Distinctness. Both algorithms have time complexity $\tilde{O}(n^{5/7})$, improving the previous $\tilde{O}(n^{3/4})$ and matching the best known upper bound for query complexity (obtained via learning graphs) up to log factors. The first algorithm is based on a connection between quantum walks and electric networks. The second algorithm uses an extension of the quantum walk search framework that facilitates quantum walks with nested updates.
Homomorphisms and composition operators on algebras of analytic functions of bounded type
2005
Abstract Let U and V be convex and balanced open subsets of the Banach spaces X and Y, respectively. In this paper we study the following question: given two Frechet algebras of holomorphic functions of bounded type on U and V, respectively, that are algebra isomorphic, can we deduce that X and Y (or X * and Y * ) are isomorphic? We prove that if X * or Y * has the approximation property and H wu ( U ) and H wu ( V ) are topologically algebra isomorphic, then X * and Y * are isomorphic (the converse being true when U and V are the whole space). We get analogous results for H b ( U ) and H b ( V ) , giving conditions under which an algebra isomorphism between H b ( X ) and H b ( Y ) is equiv…