共查询到20条相似文献,搜索用时 46 毫秒
1.
We raise the following problem. For natural numbers m, n ≥ 2, determine pairs d′, d″ (both depending on m and n only) with the property that in every pair of set systems A, B with |A| ≤ m, |B| ≤ n, and A ∩ B ≠ 0 for all A ∈ A, B ∈ B, there exists an element contained in at least d′ |A| members of A and d″ |B| members of B. Generalizing a previous result of Kyureghyan, we prove that all the extremal pairs of (d′, d″) lie on or above the line (n − 1) x + (m − 1) y = 1. Constructions show that the pair (1 + ɛ / 2n − 2, 1 + ɛ / 2m − 2) is infeasible in general, for all m, n ≥ 2 and all ɛ > 0. Moreover, for m = 2, the pair (d′, d″) = (1 / n, 1 / 2) is feasible if and only if 2 ≤ n ≤ 4.
The problem originates from Razborov and Vereshchagin’s work on decision tree complexity.
Research supported in part by the Hungarian Research Fund under grant OTKA T-032969. 相似文献
2.
Igor E. Shparlinski 《Archiv der Mathematik》2005,85(6):508-513
We give lower bounds on the number of distinct values of the Ramanujan function τ(n), n ≦ x, and on the number of distinct residues of τ(n), n ≦ x, modulo a prime ℓ. We also show that for any prime ℓ the values τ(n), n ≦ ℓ4, form a finite additive basis modulo ℓ.
Received: 6 October 2004 相似文献
3.
Vladimir I. Danilov Alexander V. Karzanov Gleb A. Koshevoy 《Journal of Algebraic Combinatorics》2010,32(4):497-531
For a permutation ω∈S
n
, Leclerc and Zelevinsky in Am. Math. Soc. Transl., Ser. 2 181, 85–108 (1998) introduced the concept of an ω-chamber weakly separated collection of subsets of {1,2,…,n} and conjectured that all inclusionwise maximal collections of this sort have the same cardinality ℓ(ω)+n+1, where ℓ(ω) is the length of ω. We answer this conjecture affirmatively and present a generalization and additional results. 相似文献
4.
Yeow Meng Chee Gennian Ge Lijun Ji San Ling Jianxing Yin 《Designs, Codes and Cryptography》2011,61(2):151-166
A′(n, d, e), the smallest ℓ for which every binary error-correcting code of length n and minimum distance d is decodable with a list of size ℓ up to radius e, is determined for all d ≥ 2e − 3. As a result, A′(n, d, e) is determined for all e ≤ 4, except for 42 values of n. 相似文献
5.
Matthias Kriesell 《Graphs and Combinatorics》2006,22(4):481-485
Let κ(G) denote the (vertex) connectivity of a graph G. For ℓ≥0, a noncomplete graph of finite connectivity is called ℓ-critical if κ(G−X)=κ(G)−|X| for every X⊆V(G) with |X|≤ℓ.
Mader proved that every 3-critical graph has diameter at most 4 and asked for 3-critical graphs having diameter exceeding
2. Here we give an affirmative answer by constructing an ℓ-critical graph of diameter 3 for every ℓ≥3. 相似文献
6.
For a strongly connected digraph D the minimum ,cardinality of an arc-cut over all arc-cuts restricted arc-connectivity λ′(D) is defined as the S satisfying that D - S has a non-trivial strong component D1 such that D - V(D1) contains an arc. Let S be a subset of vertices of D. We denote by w+(S) the set of arcs uv with u ∈ S and v S, and by w-(S) the set of arcs uv with u S and v ∈ S. A digraph D = (V, A) is said to be λ′-optimal if λ′(D) =ξ′(D), where ξ′(D) is the minimum arc-degree of D defined as ξ(D) = min {ξ′(xy) : xy ∈ A}, and ξ′(xy) = min(|ω+({x,y})|, |w-({x,y})|, |w+(x) ∪ w- (y) |, |w- (x) ∪ω+ (y)|}. In this paper a sufficient condition for a s-geodetic strongly connected digraph D to be λ′-optimal is given in terms of its diameter. Furthermore we see that the h-iterated line digraph Lh(D) of a s-geodetic digraph is λ′-optimal for certain iteration h. 相似文献
7.
M. B. Khripunova 《Mathematical Notes》1998,63(5):658-669
The asymptotics of sums of the form Στ(|bn−a|) (summation overn<N, ω(n)=k) is studied, whereω(n) is the number of distinct prime divisors ofn, andτ(n) is the number of all divisors.
Translated fromMatematicheskie Zametki, Vol. 63, No. 5, pp. 749–762, May, 1998.
In conclusion, the author wishes to express his gratitude to Professor N. M. Timofeev for valuable advice.
This research was supported by the Russian Foundation for Basic Research under grant No. 96-01-00502. 相似文献
8.
We study the asymptotic behaviour of the trace (the sum of the diagonal parts) τ
n
= τ
n
(ω) of a plane partition ω of the positive integer n, assuming that ω is chosen uniformly at random from the set of all such partitions. We prove that (τ
n
− c
0
n
2/3)/c
1
n
1/3 log1/2
n converges weakly, as n → ∞, to the standard normal distribution, where c
0 = ζ(2)/ [2ζ(3)]2/3, c
1 = √(1/3/) [2ζ(3)]1/3 and ζ(s) = Σ
j=1∞
j
−s
.
Partial support given by the National Science Fund of the Bulgarian Ministry of Education and Science, grant No. VU-MI-105/2005. 相似文献
9.
An extension of a classical theorem of Rellich to the exterior of a closed proper convex cone is proved: Let Γ be a closed
convex proper cone inR
n and −Γ′ be the antipodes of the dual cone of Γ. Let
be a partial differential operator with constant coefficients inR
n, whereQ(ζ)≠0 onR
n−iΓ′ andP
i is an irreducible polynomial with real coefficients. Assume that the closure of each connected component of the set {ζ∈R
n−iΓ′;P
j(ζ)=0, gradP
j(ζ)≠0} contains some real point on which gradP
j≠0 and gradP
j∉Γ∪(−Γ). LetC be an open cone inR
n−Γ containing both normal directions at some such point, and intersecting each normal plane of every manifold contained in
{ξ∈R
n;P(ξ)=0}. Ifu∈ℒ′∩L
loc
2
(R
n−Γ) and the support ofP(−i∂/∂x)u is contained in Γ, then the condition
implies that the support ofu is contained in Γ. 相似文献
10.
An extension of Ezeilo's result 总被引:1,自引:0,他引:1
Rolf Reissig 《Annali di Matematica Pura ed Applicata》1972,92(1):199-209
Summary In a recent paper[1] Ezeilo considered the nonlinear third order differential equation x‴ + ω(x′)x″ + ω(x)x′ + ϑ(x, x′, x″)=p(t). He proved the
ultimate boundedness of the solutions on rather general conditions for the nonlinear terms ϕ, ϕ, ϑ. These conditions (in a
little weaker form) are also sufficient in order to prove the existence of forced oscillations in the case when the excitation
is ω-periodic. For this purpose the Lerag-Schauder principle in a form suggested by G. Güssefeldt[2] is applicable.
Dedicated to ProfessorKarl Klotter on his 70th birthday
Entrata in Redazione il 21 ottobre 1971. 相似文献
11.
孙乐平 《高校应用数学学报(英文版)》2003,18(4):390-402
§ 1 IntroductionFunctional differential equations have a wide range of applications in science andengineering.The simplestand perhapsmostnatural type of functional differential equationis a“delay differential equation”,that is,differential equation with dependence on the paststate.The simplest type of pastdependence is thatit is carried through the state variablebut not through its derivative.Then the equation can be expressed as delay differentialequations(DDEs) .There are also a number… 相似文献
12.
Peter Frankl 《Combinatorica》1984,4(2-3):141-148
LetX be a finite set ofn elements and ℓ a family ofk-subsets ofX. Suppose that for a given setL of non-negative integers all the pairwise intersections of members of ℓ have cardinality belonging toL. Letm(n, k, L) denote the maximum possible cardinality of ℓ. This function was investigated by many authors, but to determine its exact
value or even its correct order of magnitude appears to be hopeless. In this paper we investigate the case |L|=3. We give necessary and sufficient conditions form(n, k, L)=O(n) andm(n, k, L)≧O(n
2), and show that in some casesm(n, k, L)=O(n
3/2), which is quite surprising. 相似文献
13.
For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented.
Received: August 19, 1998 Final version received: May 17, 2000 相似文献
14.
N. M. Timofeev 《Mathematical Notes》1997,61(3):321-332
Let τk(n) be the number of representations ofn as the product ofk positive factors, τ(n)=τ(n). The asymptotics of Σ
n≤x
τ
k
(n)τ(n+1) for 80k
10 (lnlnx)3≤lnx is shown to be uniform with respect tok.
Translated fromMatematicheskie Zametki, Vol. 61, No. 3, pp. 391–406, March, 1997.
Translated by N. K. Kulman 相似文献
15.
Let X be an infinite-dimensional Banach space with weight τ. By Cld
AW
(X), we denote the hyperspace of nonempty closed sets in X with the Attouch—Wets topology. By Fin
AW
(X), Comp
AW
(X) and Bdd
AW
(X), we denote the subspaces of Cld
AW
(X) consisting of finite sets, compact sets and bounded closed sets, respectively. In this paper, it is proved that
Fin
AW
(X)≈Comp
AW
(X)≈ℓ2(τ)×ℓ2
f
ℓandℓBdd
AW
(X)≈ℓ2(2τ)×ℓ2
f
where ≈ means ‘is homeomorphic to’, ℓ2(τ) is the Hilbert space with weight τ (ℓ2(ℵ0)=ℓ2 the separable Hilbert space) and
ℓ2
f
={(x
i
)
iεN
εℓ2∣x
i
=0 except for finitely many iεN}. 相似文献
16.
Nils Svanstedt 《Applications of Mathematics》2008,53(2):143-155
Multiscale stochastic homogenization is studied for convection-diffusion problems. More specifically, we consider the asymptotic
behaviour of a sequence of realizations of the form ∂u
ɛ
ω
/ ∂t+1 / ɛ
3
C(T
3(x/ɛ
3)ω
3) · ∇u
ɛ
ω
− div(α(T
2(x/ɛ
2)ω
2, t) ∇u
ɛ
ω
) = f. It is shown, under certain structure assumptions on the random vector field C(ω
3) and the random map α(ω
1, ω
2, t), that the sequence {u
ɛ
ω
} of solutions converges in the sense of G-convergence of parabolic operators to the solution u of the homogenized problem ∂u/∂t − div (B(t)∇u= f). 相似文献
17.
Michel Talagrand 《Probability Theory and Related Fields》1998,112(4):545-563
Consider 0<α<1 and the Gaussian process Y(t) on ℝ
N
with covariance E(Y(s)Y(t))=|t|2α+|s|2α−|t−s|2α, where |t| is the Euclidean norm of t. Consider independent copies X
1,…,X
d
of Y and␣the process X(t)=(X
1(t),…,X
d
(t)) valued in ℝ
d
. When kN≤␣(k−1)αd, we show that the trajectories of X do not have k-multiple points. If N<αd and kN>(k−1)αd, the set of k-multiple points of the trajectories X is a countable union of sets of finite Hausdorff measure associated with the function ϕ(ɛ)=ɛ
k
N
/α−(
k
−1)
d
(loglog(1/ɛ))
k
. If N=αd, we show that the set of k-multiple points of the trajectories of X is a countable union of sets of finite Hausdorff measure associated with the function ϕ(ɛ)=ɛ
d
(log(1/ɛ) logloglog 1/ɛ)
k
. (This includes the case k=1.)
Received: 20 May 1997 / Revised version: 15 May 1998 相似文献
18.
Let G be a locally compact group with a weight function ω. Recently, we have shown that the Banach space L0∞ (G,1/ω) can be identified with the strong dual of L1(G, ω)equipped with some locally convex topologies τ. Here we use this duality to introduce an Arens multiplication on (L1(G, ω), τ)**, and prove that the topological center of (L1(G, ω), τ)** is (L1(G, ω); this enables us to conclude that (L1(G, ω), τ) is Arens regular if and only if G is discrete. We also give a characterization for Arens regularity of L0∞ (G, 1/ω)1.
Received: 8 March 2005 相似文献
19.
F. Luca I. E. Shparlinski 《Abhandlungen aus dem Mathematischen Seminar der Universit?t Hamburg》2006,76(1):143-156
Let (un)n≥0 be a non-degenerate linear recurrence sequence of integers. We show that the set of positive integersn such that either ω)(n) orΩ(n) dividesu
n
is of asymptotic density zero, where ω(n) and Ω(n) are the numbers of prime and prime power divisors ofn, respectively. The same also holds for the set of positive integersn such that τ(n)u
n
, where τ(n) is the number of the positive integer divisors of n, provided thatu
n
satisfies some mild technical conditions. 相似文献
20.
Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()α≤≤ ()
n
−ω. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour
number μ(G) of G: n− (n−ω)()
n
−ω≤μ(G)≤n−α() α.
Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002 相似文献