共查询到20条相似文献,搜索用时 31 毫秒
1.
P. D. Seymour 《Combinatorica》1982,2(1):91-97
De Bruijn and Erdős proved that ifA
1, ...,A
k
are distinct subsets of a set of cardinalityn, and |A
i
∩A
j
|≦1 for 1≦i<j ≦k, andk>n, then some two ofA
1, ...,A
k
have empty intersection. We prove a strengthening, that at leastk /n ofA
1, ...,A
k
are pairwise disjoint. This is motivated by a well-known conjecture of Erdőds, Faber and Lovász of which it is a corollary.
Partially supported by N. S. F. grant No. MCS—8103440 相似文献
2.
M. Ahsanullah 《Annals of the Institute of Statistical Mathematics》1978,30(1):163-166
Summary LetX be a non-negative random variable with probability distribution functionF. SupposeX
i,n (i=1,…,n) is theith smallest order statistics in a random sample of sizen fromF. A necessary and sufficient condition forF to be exponential is given which involves the identical distribution of the random variables (n−i)(X
i+1,n−Xi,n) and (n−j)(X
j+1,n−Xj,n) for somei, j andn, (1≦i<j<n).
The work was partly completed when the author was at the Dept. of Statistics, University of Brasilia, Brazil. 相似文献
3.
Tobias Müller 《Combinatorica》2008,28(5):529-545
A random geometric graph G
n
is constructed by taking vertices X
1,…,X
n
∈ℝ
d
at random (i.i.d. according to some probability distribution ν with a bounded density function) and including an edge between
X
i
and X
j
if ‖X
i
-X
j
‖ < r where r = r(n) > 0. We prove a conjecture of Penrose ([14]) stating that when r=r(n) is chosen such that nr
d
= o(lnn) then the probability distribution of the clique number ω(G
n
) becomes concentrated on two consecutive integers and we show that the same holds for a number of other graph parameters
including the chromatic number χ(G
n
).
The author was partially supported by EPSRC, the Department of Statistics, Bekkerla-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch
fonds, and Prins Bernhard Cultuurfonds. 相似文献
4.
Let α be a rational-valued set-function on then-element sexX i.e. α(B) εQ for everyB ⫅X. We say that α defines a 0-configuration with respect toA⫅2
x
if for everyA εA we have
α(B)=0. The 0-configurations form a vector space of dimension 2
n
− |A| (Theorem 1). Let 0 ≦t<k ≦n and letA={A ⫅X: |A| ≦t}. We show that in this case the 0-configurations satisfying α(B)=0 for |B|>k form a vector space of dimension
, we exhibit a basis for this space (Theorem 4). Also a result of Frankl, Wilson [3] is strengthened (Theorem 6). 相似文献
5.
Melvin Hausner 《Combinatorica》1985,5(3):215-225
Ifμ is a positive measure, andA
2, ...,A
n
are measurable sets, the sequencesS
0, ...,S
n
andP
[0], ...,P
[n] are related by the inclusion-exclusion equalities. Inequalities among theS
i
are based on the obviousP
[k]≧0. Letting
=the average average measure of the intersection ofk of the setsA
i
, it is shown that (−1)
k
Δ
k
M
i
≧0 fori+k≦n. The casek=1 yields Fréchet’s inequalities, andk=2 yields Gumbel’s and K. L. Chung’s inequalities. Generalizations are given involvingk-th order divided differences. Using convexity arguments, it is shown that forS
0=1,
whenS
1≧N−1, and
for 1≦k<N≦n andv=0, 1, .... Asymptotic results asn → ∞ are obtained. In particular it is shown that for fixedN,
for all sequencesM
0, ...,M
n
of sufficiently large length if and only if
for 0<t<1. 相似文献
6.
David Mejzler 《Israel Journal of Mathematics》1987,57(1):1-27
LetX
1, ...,X
n be independent random variables, letF
i be the distribution function ofX
i (1≦i≦n) and letX
1n
≦... ≦X
nn be the corresponding order statistics. We consider the statisticsX
kn, wherek=k(n),k/n → 1 andn−k → ∞. Under some additional restrictions concerning the behaviour of the sequences {a
n>0,b
n,k(n),F
n} we characterize the class of all distribution functionsH such that Prob{(X
kn
−b
n
)/a
n
<x)}→H.
Dedicated to the Memory of N. V. Smirnov (1900–1966) 相似文献
7.
A matrixA=(a
ij
) has theEdmonds—Johnson property if, for each choice of integral vectorsd
1,d
2,b
1,b
2, the convex hull of the integral solutions ofd
1≦x≦d
2,b
1≦Ax≦b
2 is obtained by adding the inequalitiescx≦|δ|, wherec is an integral vector andcx≦δ holds for each solution ofd
1≦x≦d
2,b
1≦Ax≦b
2. We characterize the Edmonds—Johnson property for integral matricesA which satisfy
for each (row index)i. A corollary is that ifG is an undirected graph which does not contain any homeomorph ofK
4 in which all triangles ofK
4 have become odd circuits, thenG ist-perfect. This extends results of Boulala, Fonlupt, Sbihi and Uhry.
First author’s research supported by the Netherlands Organization for the Advancement of Pure Research (Z.W.O.). 相似文献
8.
Zheng Zukang 《数学学报(英文版)》1994,10(4):337-347
LetX
1,X
2, ...,X
n
be a sequence of nonnegative independent random variables with a common continuous distribution functionF. LetY
1,Y
2, ...,Y
n
be another sequence of nonnegative independent random variables with a common continuous distribution functionG, also independent of {X
i
}. We can only observeZ
i
=min(X
i
,Y
i
), and
. LetH=1−(1−F)(1−G) be the distribution function ofZ. In this paper, the limit theorems for the ratio of the Kaplan-Meier estimator
or the Altshuler estimator
to the true survival functionS(t) are given. It is shown that (1)P(δ(n)=1 i.o.)=0 ifF(τ
H
) < 1 andP(δ
n
=0 i.o. )=0 ifG(τH) > 1 where δ(n) is the corresponding indicator function of
and
have the same order
a.s., where {T
n
} is a sequence of constants such that 1−H(T
n
)=n
−α(logn)β(log logn)γ. 相似文献
9.
We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on
a series of 2-lift operations. Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map π :H →G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n “new” eigenvalues. We conjecture that every d-regular graph has a 2-lift such that all new eigenvalues are in the range
(if true, this is tight, e.g. by the Alon–Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all “new” eigenvalues are in the range
for some constant c. This leads to a deterministic polynomial time algorithm for constructing arbitrarily large d-regular graphs, with second eigenvalue
.
The proof uses the following lemma (Lemma 3.3): Let A be a real symmetric matrix with zeros on the diagonal. Let d be such that the l1 norm of each row in A is at most d. Suppose that
for every x,y ∈{0,1}n with ‹x,y›=0. Then the spectral radius of A is O(α(log(d/α)+1)). An interesting consequence of this lemma is a converse to the Expander Mixing Lemma.
* This research is supported by the Israeli Ministry of Science and the Israel Science Foundation. 相似文献
10.
A system of setsE
1,E
2, ...,E
k ⊂X is said to be disjointly representable if there existx
1,x
2, ...,x
k
teX such thatx
i
teE
j
⇔i=j. Letf(r, k) denote the maximal size of anr-uniform set-system containing nok disjointly representable members. In the first section the exact value off(r, 3) is determined and (asymptotically sharp) bounds onf(r, k),k>3 are established. The last two sections contain some generalizations, in particular we prove an analogue of Sauer’ theorem
[16] for uniform set-systems.
Dedicated to Paul Erdős on his seventieth birthday 相似文献
11.
A. J. W. Hilton 《Combinatorica》1982,2(1):37-51
A variety of results on edge-colourings are proved, the main one being the following: ifG is a graph without loops or multiple edges and with maximum degree Δ=Δ(G), and if ν is a given integer 1≦ν≦Δ(G), thenG can be given a proper edge-colouring with the coloursc
1, ...,c
Δ+1 with the additional property that any edge colouredc
μ with μ≧ν is on a vertex which has on it edges coloured with at least ν − 1 ofc
1, ...,c
v
. 相似文献
12.
A theorem of Deza asserts that ifH
1, ...,H
m
ares-sets any pair of which intersects in exactlyd elements and ifm ≧s
2 −s+2, then theH
i
form aΔ-system, i.e.
. In other words, every large equidistant (0, 1)-code of constant weight is trivial. We give a (0, +1, −1) analogue of this
theorem. 相似文献
13.
F. Zhao 《Acta Mathematica Hungarica》2010,126(3):279-293
We prove that almost all integers N satisfying some necessary congruence conditions are the sum of j almost equal prime cubes with j = 5; 6; 7; 8, i.e., N = p
13 + ... + p
j
3 with |p
i
− (N/j)1/3| ≦ $
N^{1/3 - \delta _j + \varepsilon }
$
N^{1/3 - \delta _j + \varepsilon }
(1 ≦ i ≦ j), for δ
j
= 1/45; 1/30; 1/25; 2/45, respectively. 相似文献
14.
Given a graphG onn vertices and a total ordering ≺ ofV(G), the transitive orientation ofG associated with ≺, denotedP(G; ≺), is the partial order onV(G) defined by settingx<y inP(G; ≺) if there is a pathx=x
1
x
2…x
r=y inG such thatx
1 ≺x
j for 1≦i<j≦r. We investigate graphsG such that every transitive orientation ofG contains
2
n
−o(n
2) relations. We prove that almost everyG
n,p satisfies this requirement if
, but almost noG
n,p satisfies the condition if (pn log log logn)/(logn log logn) is bounded. We also show that every graphG withn vertices and at mostcn logn edges has some transitive orientation with fewer than
2
n
−δ(c)n
2 relations.
Partially supported by MCS Grant 8104854. 相似文献
15.
Intersection theorems with geometric consequences 总被引:3,自引:0,他引:3
In this paper we prove that ifℱ is a family ofk-subsets of ann-set, μ0, μ1, ..., μs are distinct residues modp (p is a prime) such thatk ≡ μ0 (modp) and forF ≠ F′ ≠ℱ we have |F ∩F′| ≡ μi (modp) for somei, 1 ≦i≦s, then |ℱ|≦(
s
n
).
As a consequence we show that ifR
n
is covered bym sets withm<(1+o(1)) (1.2)
n
then there is one set within which all the distances are realised.
It is left open whether the same conclusion holds for compositep. 相似文献
16.
Hari Bercovici 《Complex Analysis and Operator Theory》2007,1(3):335-339
Consider a domain
, and two analytic matrix-valued functions functions
. Consider also points
and positive integers n
1, n
2, . . . , n
N
. We are interested in the existence of an analytic function
such that X(ω) is invertible, and G(ω) coincides with X(ω)F(ω)X(ω)−1 up to order n
j
at the point ω
j
. We will see that such a function exists provided that F(ω
j
),G(ω
j
) have cyclic vectors, and the characteristic polynomials of F,G coincide up to order n
j
at ω
j
. This allows one to give a short proof to a result of Huang, Marcantognini and Young concerning spectral interpolation in
the unit disk.
The author was partially supported by a grant from the National Science Foundation.
Received: September 8, 2006. Accepted: January 11, 2007. 相似文献
17.
Let G be a connected graph. We denote by σ(G,x) and δ(G) respectively the σ-polynomial and the edge-density of G, where
. If σ(G,x) has at least an unreal root, then G is said to be a σ-unreal graph. Let δ(n) be the minimum edgedensity over all n vertices graphs with σ-unreal roots. In this paper, by using the theory of adjoint polynomials, a negative answer to a problem posed by Brenti et
al. is given and the following results are obtained: For any positive integer a and rational number 0≤c≤1, there exists at least a graph sequence {G
i}1≤i≤a
such that G
i is σ-unreal and δ(G
i)→c as n→∞ for all 1 ≤i≤a, and moreover, δ(n)→0 as n→∞.
Supported by the National Natural Science Foundation of China (10061003) and the Science Foundation of the State Education
Ministry of China. 相似文献
18.
Given independent random points X
1,...,X
n
∈ℝ
d
with common probability distribution ν, and a positive distance r=r(n)>0, we construct a random geometric graph G
n
with vertex set {1,..., n} where distinct i and j are adjacent when ‖X
i
−X
j
‖≤r. Here ‖·‖ may be any norm on ℝ
d
, and ν may be any probability distribution on ℝ
d
with a bounded density function. We consider the chromatic number χ(G
n
) of G
n
and its relation to the clique number ω(G
n
) as n→∞. Both McDiarmid [11] and Penrose [15] considered the range of r when $r \ll \left( {\tfrac{{\ln n}}
{n}} \right)^{1/d}$r \ll \left( {\tfrac{{\ln n}}
{n}} \right)^{1/d} and the range when $r \gg \left( {\tfrac{{\ln n}}
{n}} \right)^{1/d}$r \gg \left( {\tfrac{{\ln n}}
{n}} \right)^{1/d}, and their results showed a dramatic difference between these two cases. Here we sharpen and extend the earlier results,
and in particular we consider the ‘phase change’ range when $r \sim \left( {\tfrac{{t\ln n}}
{n}} \right)^{1/d}$r \sim \left( {\tfrac{{t\ln n}}
{n}} \right)^{1/d} with t>0 a fixed constant. Both [11] and [15] asked for the behaviour of the chromatic number in this range. We determine constants
c(t) such that $\tfrac{{\chi (G_n )}}
{{nr^d }} \to c(t)$\tfrac{{\chi (G_n )}}
{{nr^d }} \to c(t) almost surely. Further, we find a “sharp threshold” (except for less interesting choices of the norm when the unit ball tiles
d-space): there is a constant t
0>0 such that if t≤t
0 then $\tfrac{{\chi (G_n )}}
{{\omega (G_n )}}$\tfrac{{\chi (G_n )}}
{{\omega (G_n )}} tends to 1 almost surely, but if t>t
0 then $\tfrac{{\chi (G_n )}}
{{\omega (G_n )}}$\tfrac{{\chi (G_n )}}
{{\omega (G_n )}} tends to a limit >1 almost surely. 相似文献
19.
J. Spencer 《Combinatorica》1986,6(1):55-65
Let v1, ..., v
n
be vectors inR
n
of max norm at most one. It is proven that there exists a choice of signs for which all partial sums have max norm at mostKn
1/2. It is further shown that such a choice of signs must be anticipatory—there is no way to choose thei-th sign without knowledge of v
j
forj>i. 相似文献
20.
Wei-Min Huang 《Annals of the Institute of Statistical Mathematics》1986,38(1):137-144
Summary Let the random variablesX
1,X
2, ...,X
n
be generated by the first-order autoregressive modelX
i
=θX
i−1
+e
i
wheree
i
,i=1, 2, ...,n, are i.i.d. random variables with mean zero, variance σ2, and with unspecified density functiong(·). In the present paper we obtain a characterization of limiting distributions of nonparametric and parametric estimators
of θ as well as a local asymptotic minimax bound of the risks of estimators. 相似文献