Search results for "Combinatorics"

Boolean Functions of Low Polynomial Degree for Quantum Query Complexity Theory

2007

The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. This is why Boolean functions are needed with a high number of essential variables and a low polynomial degree. Unfortunately, it is a well-known problem to construct such functions. The best separation between these two complexity measures of a Boolean function was exhibited by Ambai- nis [5]. He constructed functions with polynomial degree M and number of variables Omega(M2). We improve such a separation to become exponenti…

On the construction of classes of suffix trees for square matrices: Algorithms and applications

1995

Given an n × n TEXT matrix with entries defined over an ordered alphabet σ, we introduce 4n−1 classes of index data structures for TEXT. Those indices are informally the two-dimensional analog of the suffix tree of a string [15], allowing on-line searches and statistics to be performed on TEXT. We provide one simple algorithm that efficiently builds any chosen index in those classes in O(n2 log n) worst case time using O(n2) space. The algorithm can be modified to require optimal O(n2) expected time for bounded σ.

Asymptotics for thenth-degree Laguerre polynomial evaluated atn

1992

We investigate the asymptotic behaviour of ? n (n),n?? where ? n (x) denotes the Laguerre polynomial of degreen. Our results give a partial answer to the conjecture ?? n (n)>1 forn>6, made in 1984 by van Iseghem. We also show the connection between this conjecture and the continued fraction approximants of $$6\sqrt {{3 \mathord{\left/ {\vphantom {3 \pi }} \right. \kern-\nulldelimiterspace} \pi }} $$ .

An algorithm to find all paths between two nodes in a graph

1990

On Brauer’s Height Zero Conjecture

2014

In this paper, the unproven half of Richard Brauer’s Height Zero Conjecture is reduced to a question on simple groups.

Das Traveling Salesman Problem

1970

Unter den Reihenfolgeproblemen hat das Traveling Salesman Problem eine besondere Bedeutung. Aus diesem Grund ist ihm der meiste Platz dieses Buches gewidmet. Haufig werden sogar die Begriffe Reihenfolgeproblem und Traveling Salesman Problem synonym verwendet.

On finite products of groups and supersolubility

2010

Two subgroups X and Y of a group G are said to be conditionally permutable in G if X permutes with Y(g) for some element g E G. i.e., XY(g) is a subgroup of G. Using this permutability property new criteria for the product of finite supersoluble groups to be supersoluble are obtained and previous results are recovered. Also the behaviour of the supersoluble residual in products of finite groups is studied.

On conditional permutability and saturated formations

2011

Two subgroups A and B of a group G are said to be totally completely conditionally permutable (tcc-permutable) in G if X permutes with Yg for some g ¿ ¿X, Y¿ for all X ¿ A and Y ¿ B. We study the belonging of a finite product of tcc-permutable subgroups to a saturated formation of soluble groups containing all finite supersoluble groups. © 2011 Edinburgh Mathematical Society.

Homogeneous products of characters

2004

I. M. Isaacs has conjectured (see \cite{isa00}) that if the product of two faithful irreducible characters of a solvable group is irreducible, then the group is cyclic. In this paper we prove a special case of the following conjecture, which generalizes Isaacs conjecture. Suppose that $G$ is solvable and that $\psi,\phi\in\Irr(G)$ are faithful. If $\psi \phi=m\chi$ where $m$ is a positive integer and $\chi \in \Irr(G)$ then $\psi$ and $\phi$ vanish on $G- Z(G)$. In particular we prove that the above conjecture holds for $p$-groups.

Brauer’s Height Zero Conjecture for principal blocks

2021

Abstract We prove the other half of Brauer’s Height Zero Conjecture in the case of principal blocks.