Search results for "Combinatorics"
showing 10 items of 1770 documents
Pizza-cutter’s problem and Hamiltonian paths
2019
Summary. The pizza-cutter’s problem is to determine the maximum number of pieces that can be made with n straight cuts through a circular pizza, regardless of the size and shape of the pieces. For ...
The Poincaré inequality is an open ended condition
2008
Let p > 1 and let (X,d,µ) be a complete metric measure space with µ Borel and doubling that admits a (1,p)-Poincare inequality. Then there exists e > 0 such that (X,d,µ) admits a (1,q)-Poincare inequality for every q > p - e, quantitatively.
Error Bounds for the Numerical Evaluation of Integrals with Weights
1988
This paper is concerned with a procedure of obtaining error bounds for numerically evaluated integrals with weights. If \( - \infty \mathop < \limits_ = a < b\mathop < \limits_ = \infty \), w integrable over [a,b] and positive almost everywhere, then an approximation of \({I_W}f: = \int\limits_a^b {w\left( t \right)f\left( t \right)dt} \) by a quadrature rule \({Q_n}f: = \sum\limits_{i = 0}^n {{\alpha _i}f\left( {{t_i}} \right)} \) is leading to the error Enf ≔ Iwf ‒ Qnf. An algorithm is derived for the computation of bounds for |Enf| depending on the smoothness of the integrand f and on the degree of exactness of Q. As initial values this algorithm needs moments of the weighting function w…
Some Hadamard designs with parameters (71,35,17)
2002
Up to isomorphisms there are precisely eight symmetric designs with parameters (71, 35, 17) admitting a faithful action of a Frobenius group of order 21 in such a way that an element of order 3 fixes precisely 11 points. Five of these designs have 84 and three have 420 as the order of the full automorphism group G. If |G| = 420, then the structure of G is unique and we have G = (Frob21 × Z5):Z4. In this case Z(G) = 〈1〉, G′ has order 35, and G induces an automorphism group of order 6 of Z7. If |G| = 84, then Z(G) is of order 2, and in precisely one case a Sylow 2-subgroup is elementary abelian. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 144–149, 2002; DOI 10.1002/jcd.996
Transposed-Letter Priming Effects for Close Versus Distant Transpositions
2009
Transposing two internal letters of a word produces a perceptually similar item (e.g., CHOLOCATE being processed as CHOCOLATE). To determine the precise nature of the encoding of letter position within a word, we examined the effect of the number of intervening letters in transposed-letter effects with a masked priming procedure. In Experiment 1, letter transposition could involve adjacent letters (chocloate-CHOCOLATE) and nonadjacent letters with two intervening letters (choaolcte-CHOCOLATE). Results showed that the magnitude of the transposed-letter priming effect – relative to the appropriate control condition – was greater when the transposition involved adjacent letters than when it i…
Sylow permutable subnormal subgroups of finite groups
2002
[EN] An extension of the well-known Frobenius criterion of p-nilpotence in groups with modular Sylow p-subgroups is proved in the paper. This result is useful to get information about the classes of groups in which every subnormal subgroup is permutable and Sylow permutable.
Linear-size suffix tries
2016
Suffix trees are highly regarded data structures for text indexing and string algorithms [MCreight 76, Weiner 73]. For any given string w of length n = | w | , a suffix tree for w takes O ( n ) nodes and links. It is often presented as a compacted version of a suffix trie for w, where the latter is the trie (or digital search tree) built on the suffixes of w. Here the compaction process replaces each maximal chain of unary nodes with a single arc. For this, the suffix tree requires that the labels of its arcs are substrings encoded as pointers to w (or equivalent information). On the contrary, the arcs of the suffix trie are labeled by single symbols but there can be Θ ( n 2 ) nodes and lin…
Computation of Yvon-Villarceau circles on Dupin cyclides and construction of circular edge right triangles on tori and Dupin cyclides
2014
Ring Dupin cyclides are non-spherical algebraic surfaces of degree four that can be defined as the image by inversion of a ring torus. They are interesting in geometric modeling because: (1) they have several families of circles embedded on them: parallel, meridian, and Yvon-Villarceau circles, and (2) they are characterized by one parametric equation and two equivalent implicit ones, allowing for better flexibility and easiness of use by adopting one representation or the other, according to the best suitability for a particular application. These facts motivate the construction of circular edge triangles lying on Dupin cyclides and exhibiting the aforementioned properties. Our first contr…
Descriptive Complexity, Lower Bounds and Linear Time
1999
This paper surveys two related lines of research: Logical characterizations of (non-deterministic) linear time complexity classes, and non-expressibility results concerning sublogics of existential second-order logic. Starting from Fagin’s fundamental work there has been steady progress in both fields with the effect that the weakest logics that are used in characterizations of linear time complexity classes are closely related to the strongest logics for which inexpressibility proofs for concrete problems have been obtained. The paper sketches these developments and highlights their connections as well as the obstacles that prevent us from closing the remaining gap between both kinds of lo…
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?
2012
It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n / loglog n), and we exhibit quantum algorithms for two functions where this bound is achieved.