Search results for "combinatoric"

The Jordan-Hölder theorem and prefrattini subgroups of finite groups

1995

by A. BALLESTER-BOLINCHES and L. M. EZQUERRO(Received 26 January, 1994)Introduction. All groups considered are finite. In recent years a number ofgeneralizations of the classic Jordan-Holder Theorem have been obtained (see [7],Theorem A.9.13): in a finite group G a one-to-one correspondence as in the Jordan-Holder Theorem can be defined preserving not only G-isomorphic chief factors but eventheir property of being Frattini or non-Frattini chief factors. In [2] and [13] a newdirection of generalization is presented: the above correspondence can be defined in sucha way that the corresponding non-Frattini chief factors have the same complement(supplement).In this paper we present a necessary a…

Tighter Relations between Sensitivity and Other Complexity Measures

2014

The sensitivity conjecture of Nisan and Szegedy [12] asks whether the maximum sensitivity of a Boolean function is polynomially related to the other major complexity measures of Boolean functions. Despite major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004 [11].

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.