Search results for "Maxima"
showing 10 items of 371 documents
On the chromatic number of disk graphs
1998
Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their different generalizations. For all these graphs including the most general class of the double disk (DD) graphs, it is shown that X(G) ≤ c.ω(G) for a constant c. Several coloring algorithms are analyzed for disk graphs, aiming to improve the bounds on X(G). We find that their worst-case performance expressed in the number of used colors is indeed reached in some instances.
Maximal Closed Substrings
2022
A string is closed if it has length 1 or has a nonempty border without internal occurrences. In this paper we introduce the definition of a maximal closed substring (MCS), which is an occurrence of a closed substring that cannot be extended to the left nor to the right into a longer closed substring. MCSs with exponent at least 2 are commonly called runs; those with exponent smaller than 2, instead, are particular cases of maximal gapped repeats. We show that a string of length n contains O(n1.5) MCSs. We also provide an output-sensitive algorithm that, given a string of length n over a constant-size alphabet, locates all m MCSs the string contains in O(nlog n+ m) time.
Pattern Matching and Pattern Discovery Algorithms for Protein Topologies
2001
We describe algorithms for pattern-matching and pattern-learning in TOPS diagrams (formal descriptions of protein topologies). These problems can be reduced to checking for subgraph isomorphism and finding maximal common subgraphs in a restricted class of ordered graphs. We have developed a subgraph isomorphism algorithm for ordered graphs, which performs well on the given set of data. The maximal common subgraph problem then is solved by repeated subgraph extension and checking for isomorphisms. Despite its apparent inefficiency, this approach yields an algorithm with time complexity proportional to the number of graphs in the input set and is still practical on the given set of data. As a…
On groups with abelian Sylow 2-subgroups
1970
Finite groups with abelian Sylow 2-subgroups have been classified by Walter [8]. In this note I want to describe an alternate proof of some partial result of Walter's work, namely the theorem stated below. It represents the first major reduction step in that classification. The approach used here is to some extent derived from [1]. ! Besides the groups L 2 (q)= PSL(2, q) another class of simple groups enters our discussion: We say that a simple group G with abelian Sz-subgroups is of type JR (Janko-Ree) if, for any involution t in G, CG (t) is a maximal subgroup of G isomorphic to ( t ) | E where PSL(2, q)~ E ~_ PFL(2, q) with odd q > 5. In fact, E = L 2 (q), as proved by Walter 1-7] ; and …
Nilpotent length and system permutability
2022
Abstract If C is a class of groups, a C -injector of a finite group G is a subgroup V of G with the property that V ∩ K is a C -maximal subgroup of K for all subnormal subgroups K of G. The classical result of B. Fischer, W. Gaschutz and B. Hartley states the existence and conjugacy of F -injectors in finite soluble groups for Fitting classes F . We shall show that for groups of nilpotent length at most 4, F -injectors permute with the members of a Sylow basis in the group. We shall exhibit the construction of a Fitting class and a group of nilpotent length 5, which fail to satisfy the result and show that the bound is the best possible.
S_Kernel: A New Symmetry Measure
2005
Symmetry is an important feature in vision. Several detectors or transforms have been proposed. In this paper we concentrate on a measure of symmetry. Given a transform S, the kernel SK of a pattern is defined as the maximal included symmetric sub-set of this pattern. It is easily proven that, in any direction, the optimal axis corresponds to the maximal correlation of a pattern with its flipped version. For the measure we compute a modified difference between respective surfaces of a pattern and its kernel. That founds an efficient algorithm to attention focusing on symmetric patterns.
On the Deskins index complex of a maximal subgroup of a finite group
1999
AbstractLet M be a maximal subgroup of a finite group G. A subgroup C of G is said to be a completion of M in G if C is not contained in M while every proper subgroup of C which is normal in G is contained in M. The set, I(M), of all completions of M is called the index complex of M in G. Set P(M) = {C ϵ I(M) ¦ C} is maximal in I(M) and G = CM. The purpose of this note is to prove: A finite group G is solvable if and only if, for each maximal subgroup M of G, P(M) contains element C with CK(C) nilpotent.
On the normal index of maximal subgroups in finite groups
1990
AbstractFor a maximal subgroup M of a finite group G, the normal index of M is the order of a chief factor H/K where H is minimal in the set of normal supplements of M in G. We use the primitive permutation representations of a finite group G and the normal index of its maximal subgroups to obtain results about the influence of the set of maximal subgroups in the structure of G.
OnF-Subnormal Subgroups andF-Residuals of Finite Soluble Groups
1996
All groups that we consider are finite and soluble. Recall that a formation is a class of groups which is closed under homomorphic images and subdirect products. Hence, if F is a formation and G is a group which is a direct product of the subgroups A and B, then G is in F if and only if A and B lie in F. More generally, Doerk and w x Hawkes 4, IV, 1.18 proved that if G is a group such that G s A = B, then G s A = B , where G is the F-residual of G, that is, the smallest normal subgroup of G with quotient in F. The main purpose of this paper is the development of this result by means of the concept of F-subnormal subgroup. Suppose that F is a saturated formation. A maximal subgroup M of a Ž …
The Variation of the Fractional Maximal Function of a Radial Function
2017
Abstract In this article, we study the regularity of the non-centered fractional maximal operator $M_{\beta}$. As the main result, we prove that there exists $C(n,\beta)$ such that if $q=n/(n-\beta)$ and $f$ is radial function, then $\|DM_{\beta}f\|_{L^{q}({\mathbb{R}^n})}\leq C(n,\beta)\|Df\|_{L^{1}({\mathbb{R}^n})}$. The corresponding result was previously known only if $n=1$ or $\beta=0$. Our proofs are almost free from one-dimensional arguments. Therefore, we believe that the new approach may be very useful when trying to extend the result for all $f\in W^{1,1}({\mathbb{R}^n})$.