Search results for "combinatoric"

Highly irregular graphs with extreme numbers of edges

1997

Abstract A simple connected graph is highly irregular if each of its vertices is adjacent only to vertices with distinct degrees. In this paper we find: (1) the greatest number of edges of a highly irregular graph with n vertices, where n is an odd integer (for n even this number is given in [1]), (2) the smallest number of edges of a highly irregular graph of given order.

Nilpotent Lie algebras with 2-dimensional commutator ideals

2011

Abstract We classify all (finitely dimensional) nilpotent Lie k -algebras h with 2-dimensional commutator ideals h ′ , extending a known result to the case where h ′ is non-central and k is an arbitrary field. It turns out that, while the structure of h depends on the field k if h ′ is central, it is independent of k if h ′ is non-central and is uniquely determined by the dimension of h . In the case where k is algebraically or real closed, we also list all nilpotent Lie k -algebras h with 2-dimensional central commutator ideals h ′ and dim k h ⩽ 11 .

Quasi-conformal mapping theorem and bifurcations

1998

LetH be a germ of holomorphic diffeomorphism at 0 ∈ ℂ. Using the existence theorem for quasi-conformal mappings, it is possible to prove that there exists a multivalued germS at 0, such thatS(ze 2πi )=H○S(z) (1). IfH λ is an unfolding of diffeomorphisms depending on λ ∈ (ℂ,0), withH 0=Id, one introduces its ideal $$\mathcal{I}_H$$ . It is the ideal generated by the germs of coefficients (a i (λ), 0) at 0 ∈ ℂ k , whereH λ(z)−z=Σa i (λ)z i . Then one can find a parameter solutionS λ (z) of (1) which has at each pointz 0 belonging to the domain of definition ofS 0, an expansion in seriesS λ(z)=z+Σb i (λ)(z−z 0) i with $$(b_i ,0) \in \mathcal{I}_H$$ , for alli. This result may be applied to the…

A characterization of the Schur property through the disk algebra

2017

[EN] In this paper we give a new characterization of when a Banach space E has the Schur property in terms of the disk algebra. We prove that E has the Schur property if and only if A(D, E) = A(D,E-w). (C) 2016 Elsevier Inc. All rights reserved.

On Composition Ideals of Multilinear Mappings and Homogeneous Polynomials

2007

Given an operator ideal I, we study the multi-ideal I ο L and the polynomial ideal I ο P). The connection with the linearizations of these mappings on projective symmetric tensor products is investigated in detail. Applications to the ideals of strictly singular and absolutely summing linear operators are obtained.

Improved constructions of mixed state quantum automata

2009

Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A. Ambainis and R. Freivalds that quantum finite automata with pure states can have an exponentially smaller number of states than deterministic finite automata recognizing the same language. There was an unpublished ''folk theorem'' proving that quantum finite automata with mixed states are no more super-exponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable. We prove that there is an infinite sequence of distinct int…

Adjacent Vertices Can Be Hard to Find by Quantum Walks

2017

Quantum walks have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems. Most of the papers, however, consider a search space containing a single marked element only. We show that if the search space contains more than one marked element, their placement may drastically affect the performance of the search. More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk needs \(\varOmega (N)\) steps, that is, it has no speed-up over the classical exhaustive search. The demonstrated configurations occur for certain placements of …

2014

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate. First, we show that for any problem that is invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 9 th root of the classical randomized query complexity. This resolves a conjecture of Watrous from 2002. Second, inspired by recent work of O’Donnell et al. and Dinur et al., we conjecture that every bounded low-degree polynomial has a “highly influential” …

Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer

2007

Consider the problem of evaluating an AND-OR formula on an $N$-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time $N^{1/2+o(1)}$. In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.

Restriction of odd degree characters and natural correspondences

2016

Let $q$ be an odd prime power, $n > 1$, and let $P$ denote a maximal parabolic subgroup of $GL_n(q)$ with Levi subgroup $GL_{n-1}(q) \times GL_1(q)$. We restrict the odd-degree irreducible characters of $GL_n(q)$ to $P$ to discover a natural correspondence of characters, both for $GL_n(q)$ and $SL_n(q)$. A similar result is established for certain finite groups with self-normalizing Sylow $p$-subgroups. We also construct a canonical bijection between the odd-degree irreducible characters of $S_n$ and those of $M$, where $M$ is any maximal subgroup of $S_n$ of odd index; as well as between the odd-degree irreducible characters of $G = GL_n(q)$ or $GU_n(q)$ with $q$ odd and those of $N_{G}…