Search results for "Combinatorics"

On a Linear Diophantine Problem of Frobenius: Extending the Basis

1998

LetXk={a1, a2, …, ak},k>1, be a subset of N such that gcd(Xk)=1. We shall say that a natural numbernisdependent(onXk) if there are nonnegative integersxisuch thatnhas a representationn=∑ki=1 xiai, elseindependent. The Frobenius numberg(Xk) ofXkis the greatest integer withnosuch representation. Selmer has raised the problem of extendingXkwithout changing the value ofg. He showed that under certain conditions it is possible to add an elementc=a+kdto the arithmetic sequencea,a+d,a+2d, …, a+(k−1) d, gcd(a, d)=1, without alteringg. In this paper, we give the setCof all independent numberscsatisfyingg(A, c)=g(A), whereAcontains the elements of the arithmetic sequence. Moreover, ifa>kthen we give …

Completion of partially ordered sets

2007

The Zahorski theorem is valid in Gevrey classes

1996

Let {Ω,F,G} be a partition of R such that Ω is open, F is Fσ and of the first category, and G is Gδ . We prove that, for every γ ∈ ]1,∞[, there is an element of the Gevrey class Γγ which is analytic on Ω, has F as its set of defect points and has G as its set of divergence points.

On the number of prime divisors of the order of elliptic curves modulo p

2005

Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification

2013

We study search by quantum walk on a finite two dimensional grid. The algorithm of Ambainis, Kempe, Rivosh [AKR05] uses \(O(\sqrt{N \log{N}})\) steps and finds a marked location with probability O(1 / logN) for grid of size \(\sqrt{N} \times \sqrt{N}\). This probability is small, thus [AKR05] needs amplitude amplification to get Θ(1) probability. The amplitude amplification adds an additional \(O(\sqrt{\log{N}})\) factor to the number of steps, making it \(O(\sqrt{N} \log{N})\).

Differential equations over polynomially bounded o-minimal structures

2002

We investigate the asymptotic behavior at +∞ of non-oscillatory solutions to differential equations y' = G(t, y), t > a, where G: R 1+l → R l is definable in a polynomially bounded o-minimal structure. In particular, we show that the Pfaffian closure of a polynomially bounded o-minimal structure on the real field is levelled.

Blocking sets and partial spreads in finite projective spaces

1980

A t-blocking set in the finite projective space PG(d, q) with d≥t+1 is a set $$\mathfrak{B}$$ of points such that any (d−t)-dimensional subspace is incident with a point of $$\mathfrak{B}$$ and no t-dimensional subspace is contained in $$\mathfrak{B}$$ . It is shown that | $$\mathfrak{B}$$ |≥q t +...+1+q t−1√q and the examples of minimal cardinality are characterized. Using this result it is possible to prove upper and lower bounds for the cardinality of partial t-spreads in PG(d, q). Finally, examples of blocking sets and maximal partial spreads are given.

Sylow normalizers and character tables, II

2002

Suppose thatG is a finitep-solvable group and letPe Syl p (G). In this note, we prove that the character table ofG determines ifN G(itP)/P is abelian.

Estimating norms inC*-algebras of discrete groups

1976

LetG be a discrete group, letK be a finite subset ofG and let χ K be the characteristic function ofK. Then χ K acts by convolution as a bounded operator onL2(G). We will prove that the norm |||χ K ||| of this operator always satisfies the following estimate: $$|||\chi _{\rm K} |||^2 \leqq k + 2\sqrt {w\left( {k - 1} \right)\left( {k - w} \right)} + \left( {k - 2} \right)\left( {k - w} \right)$$ . Here .

The irregularity strength of circulant graphs

2005

AbstractThe irregularity strength of a simple graph is the smallest integer k for which there exists a weighting of the edges with positive integers at most k such that all the weighted degrees of the vertices are distinct. In this paper we study the irregularity strength of circulant graphs of degree 4. We find the exact value of the strength for a large family of circulant graphs.