Search results for "combinatoric"
showing 10 items of 1776 documents
A class of imprimitive groups
2010
We classify imprimitive groups inducing the alternating group A4 on the set of blocks, with the inertia subgroup satisfying some very natural geometrical conditions which force the group to operate linearly.
Overlapping self-affine sets of Kakeya type
2009
We compute the Minkowski dimension for a family of self-affine sets on the plane. Our result holds for every (rather than generic) set in the class. Moreover, we exhibit explicit open subsets of this class where we allow overlapping, and do not impose any conditions on the norms of the linear maps. The family under consideration was inspired by the theory of Kakeya sets.
Positive Versions of Polynomial Time
1998
Abstract We show that restricting a number of characterizations of the complexity class P to be positive (in natural ways) results in the same class of (monotone) problems, which we denote by posP . By a well-known result of Razborov, posP is a proper subclass of the class of monotone problems in P . We exhibit complete problems for posP via weak logical reductions, as we do for other logically defined classes of problems. Our work is a continuation of research undertaken by Grigni and Sipser, and subsequently Stewart; indeed, we introduce the notion of a positive deterministic Turing machine and consequently solve a problem posed by Grigni and Sipser.
Fast Matrix Multiplication
2015
Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time O(n2.3755). Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le~Gall has led to an improved algorithm running in time O(n2.3729). These algorithms are obtained by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd. We show that this exact approach cannot result in an algorithm with running time O(n2.3725), and identify a wide class of variants of this approach which cannot result in an algorithm with running time $O(n^{2.3078}); in particular, this approach cannot prove the conjecture that for every e > 0, …
On a class of supersoluble groups
2014
A subgroup H of a finite group G is said to be S-semipermutable in G if H permutes with every Sylow q-subgroup of G for all primes q not dividing |H|. A finite group G is an MS-group if the maximal subgroups of all the Sylow subgroups of G are S-semipermutable in G. The aim of the present paper is to characterise the finite MS-groups.
Primitive subgroups and PST-groups
2014
AbstractAll groups considered in this paper are finite. A subgroup $H$ of a group $G$ is called a primitive subgroup if it is a proper subgroup in the intersection of all subgroups of $G$ containing $H$ as a proper subgroup. He et al. [‘A note on primitive subgroups of finite groups’, Commun. Korean Math. Soc. 28(1) (2013), 55–62] proved that every primitive subgroup of $G$ has index a power of a prime if and only if $G/ \Phi (G)$ is a solvable PST-group. Let $\mathfrak{X}$ denote the class of groups $G$ all of whose primitive subgroups have prime power index. It is established here that a group $G$ is a solvable PST-group if and only if every subgroup of $G$ is an $\mathfrak{X}$-group.
The arithmetic decomposition of central Cantor sets
2018
Abstract Every central Cantor set of positive Lebesgue measure is the arithmetic sum of two central Cantor sets of Lebesgue measure zero. Under some mild condition this result can be strengthened by stating that the summands can be chosen to be C s regular if the initial set is of this class.
On Horn spectra
1991
Abstract A Horn spectrum is a spectrum of a Horn sentence. We show that to solve Asser's problem, and consequently the EXPTIME = ? NEXPTIME question it suffices to consider the class of Horn spectra. We also pose the problem whether or not the generator of every Horn spectrum is a spectrum. We prove that from a negative solution of the generator problem, a negative answer for the EXPTIME = ? NEXPTIME question follows. Some other relations between the generator problem and Asser's problem are given. Finally, the relativized version of the generator problem is formulated and it is shown that it has an affirmative solution for some oracles, and a negative solution for some others.
Relaxation for a Class of Control Systems with Unilateral Constraints
2019
We consider a nonlinear control system involving a maximal monotone map and with a priori feedback. We assume that the control constraint multifunction $U(t,x)$ is nonconvex valued and only lsc in the $x \in \mathbb{R}^{N}$ variable. Using the Q-regularization (in the sense of Cesari) of $U(t,\cdot )$, we introduce a relaxed system. We show that this relaxation process is admissible.
The identity type weak factorisation system
2008
We show that the classifying category C(T) of a dependent type theory T with axioms for identity types admits a non-trivial weak factorisation system. We provide an explicit characterisation of the elements of both the left class and the right class of the weak factorisation system. This characterisation is applied to relate identity types and the homotopy theory of groupoids.