共查询到20条相似文献,搜索用时 500 毫秒
1.
Jian Shen 《Graphs and Combinatorics》2002,18(3):645-654
It was conjectured by Caccetta and H?ggkvist in 1978 that every digraph G with n vertices and minimum outdegree at least r contains a directed cycle of length at most ⌈n/r⌉. By refining an argument of Chvátal and Szemerédi, we prove that such G contains a directed cycle of length at most n/r+73.
Received: September 13, 1999 Final version received: June 19, 2000
Acknowledgment. I want to thank a referee for many valuable suggestions leading to the clear presentation of the paper. 相似文献
2.
The existence of group divisible designs of type g
t
with block sizes three and n, 4≤ n≤10, is completely settled for all values of g and t.
Received: July 21, 1999 Final version received: September 10, 2001
RID="*"
ID="*" This work was done in 1995 while the authors were graduate students at the University of Waterloo, Waterloo, Ontario
N2L 3G1, Canada
Acknowledgments. The authors would like to thank the referee for his careful reading and for pointing out some errors in an earlier draft
of the paper. 相似文献
3.
Dhruv?Mubayi 《Graphs and Combinatorics》2002,18(3):583-589
We prove that for every family of n pairwise intersecting simple closed planar curves in general position, at least (4/5)n
2−O(n) points lie on more than one curve. This improves the previous lower bound of (3/4)n
2−O(n) due to Richter and Thomassen.
Received: March 29, 2000 Final version received: August 30, 2001
RID="*"
ID="*" Research supported in part by NSF grant DMS-9970325
Acknowledgments. I thank Bruce Richter for informing me about this problem, Gelasio Salazar for reading a preliminary version of the paper,
and a Referee for useful comments.
Current Address: Microsoft Research, One Microsoft Way, Redmond, WA 98052-6399, USA. e-mail: mubayi@microsoft.com
1991 Mathematics Subject Classification. 05C35, 52C10 相似文献
4.
Narong Punnim 《Graphs and Combinatorics》2002,18(3):597-603
We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values χ(G) of the function chromatic number completely cover a line segment [a,b] of positive integers. Thus for an arbitrary graphical sequence d, two invariants minχ(d):=a and maxχ(d):=b naturally arise. For a regular graphical sequence d=r
n
:=(r,r,…,r) where r is the degree and n is the number of vertices, the exact values of a and b are found in all situations, except the case where n and r are both even and n<2r.
Received: September 16, 2000 Final version received: December 13, 2001
Acknowledgments. We would like to thank Professor Tommy R. Jensen for his useful comment and editing thorough the paper. 相似文献
5.
MingChu Li 《Graphs and Combinatorics》2000,16(2):177-198
Some known results on claw-free graphs are generalized to the larger class of almost claw-free graphs. In this paper, we prove
several properties on longest cycles in almost claw-free graphs. In particular, we show the following two results.? (1) Every
2-connected almost claw-free graph on n vertices contains a cycle of length at least min {n, 2δ+4} and the bound 2δ+ 4 is best possible, thereby fully generalizing a result of Matthews and Sumner.? (2) Every 3-connected
almost claw-free graph on n vertices contains a cycle of length at least min {n, 4δ}, thereby fully generalizing a result of MingChu Li.
Received: September 17, 1996 Revised: September 22, 1998 相似文献
6.
A classical result of Wagner states that any two (unlabelled) planar triangulations with the same number of vertices can
be transformed into each other by a finite sequence of diagonal flips. Recently Komuro gives a linear bound on the maximum
number of diagonal flips needed for such a transformation. In this paper we show that any two labelled triangulations can be transformed into each other using at most O(nlogn) diagonal flips. We will also show that any planar triangulation with n>4 vertices has at least n− 2 flippable edges. Finally, we prove that if the minimum degree of a triangulation is at least 4, then it contains at least
2n + 3 flippable edges. These bounds can be achieved by an infinite class of triangulations.
Received: June 3, 1998 Final version received: January 26, 2001 相似文献
7.
In this paper we consider the problem
where B is a ball in R
n
. For a small d>0, we show the uniqueness (up to rotation) of the one-bubbling solution which concentrates at a point of the boundary.
Received: 12 December 2001 / Published online: 10 February 2003
RID="⋆"
ID="⋆" Supported by M.U.R.S.T., project: ``Variational methods and nonlinear differential equations'
RID="⋆⋆"
ID="⋆⋆" Partial supported by National Center for Theoretical Sciences of NSC, Taiwan
Mathematics Subject Classification (2000): 35J60 相似文献
8.
Gábor Hetyei 《Graphs and Combinatorics》2002,18(3):533-564
9.
Amir Dembo Nina Gantert Yuval Peres Ofer Zeitouni 《Probability Theory and Related Fields》2002,122(2):241-288
In the study of large deviations for random walks in random environment, a key distinction has emerged between quenched asymptotics, conditional on the environment, and annealed asymptotics, obtained from averaging over environments. In this paper we consider a simple random walk {X
n
} on a Galton–Watson tree T, i.e., on the family tree arising from a supercritical branching process. Denote by |X
n
| the distance between the node X
n
and the root of T. Our main result is the almost sure equality of the large deviation rate function for |X
n
|/n under the “quenched measure” (conditional upon T), and the rate function for the same ratio under the “annealed measure” (averaging on T according to the Galton–Watson distribution). This equality hinges on a concentration of measure phenomenon for the momentum of the walk. (The momentum at level n, for a specific tree T, is the average, over random walk paths, of the forward drift at the hitting point of that level). This concentration, or
certainty, is a consequence of the uncertainty in the location of the hitting point. We also obtain similar results when {X
n
} is a λ-biased walk on a Galton–Watson tree, even though in that case there is no known formula for the asymptotic speed.
Our arguments rely at several points on a “ubiquity” lemma for Galton–Watson trees, due to Grimmett and Kesten (1984).
Received: 15 November 2000 / Revised version: 27 February 2001 / Published online: 19 December 2001 相似文献
10.
The bandwidth of a graph is the minimum, over vertex labelings with distinct integers, of the maximum difference between
labels on adjacent vertices. Kuang and McDiarmid proved that almost all n-vertex graphs have bandwidth . Thus the sum of the bandwidths of a graph and its complement is almost always at least ; we prove that it is always at most 2n−4 log 2
n+o(log n). The proofs involve improving the bounds on the Ramsey and Turán numbers of the “halfgraph”.
Received: September 2, 1998?Final version received: November 29, 1999 相似文献
11.
, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes.
1. monotone-NC ≠ monotone-P.
2. For every i≥1, monotone-≠ monotone-.
3. More generally: For any integer function D(n), up to (for some ε>0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone
Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circuits of depth less than Const·D(n) (for some constant Const).
Only a separation of monotone- from monotone- was previously known.
Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART
games, and we prove a tight lower bound for the communication complexity of every member of this class. As a result we get
lower bounds for the monotone depth of many functions. In particular, we get the following bounds:
1. For st-connectivity, we get a tight lower bound of . That is, we get a new proof for Karchmer–Wigderson's theorem, as an immediate corollary of our general result.
2. For the k-clique function, with , we get a tight lower bound of Ω(k log n). This lower bound was previously known for k≤ log n [1]. For larger k, however, only a bound of Ω(k) was previously known.
Received: December 19, 1997 相似文献
12.
We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear
integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block
of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For
the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating
the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that
seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the
results of some computational experiments.
Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002
Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral
bound – Fischer's inequality – branch-and-bound – dynamic programming
Mathematics Subject Classification (2000): 52B12, 90C10
Send offprint requests to: Jon Lee
Correspondence to: Jon Lee 相似文献
13.
We study the robustness under perturbations of mixing times, by studying mixing times of random walks in percolation clusters
inside boxes in Z
d
. We show that for d≥2 and p>p
c
(Z
d
), the mixing time of simple random walk on the largest cluster inside is Θ(n
2
) – thus the mixing time is robust up to a constant factor. The mixing time bound utilizes the Lovàsz-Kannan average conductance
method. This is the first non-trivial application of this method which yields a tight result.
Received: 16 December 2001 / Revised version: 13 August 2002 / Published online: 19 December 2002 相似文献
14.
Let G
m,n be the class of strategic games with n players, where each player has m≥2 pure strategies. We are interested in the structure of the set of correlated equilibria of games in G
m,n when n→∞. As the number of equilibrium constraints grows slower than the number of pure strategy profiles, it might be conjectured
that the set of correlated equilibria becomes large. In this paper, we show that (1) the average relative measure of the set
of correlated equilibria is smaller than 2−n; and (2) for each 1<c<m, the solution set contains c
n correlated equilibria having disjoint supports with a probability going to 1 as n grows large. The proof of the second result hinges on the following inequality: Let c
1, …, c
l be independent and symmetric random vectors in R
k, l≥k. Then the probability that the convex hull of c
1, …, c
l intersects R
k
+ is greater than or equal to .
Received: December 1998/Final version: March 2000 相似文献
15.
Byeong-Kweon Oh 《Mathematische Zeitschrift》2003,244(2):399-413
In this article, we prove that there are only finitely many positive definite integral quadratic forms of rank n+3(n≥2) that represent all positive definite integral quadratic forms of rank n but finitely many exceptions. Furthermore we determine all diagonal quadratic forms having such property and its exceptions
remaining four as candidates.
Received: 29 November 2000 ; in final form: 8 August 2002 /
Published online: 1 April 2003
Mathematics Subject Classification (2000): 11E12, 11E20. 相似文献
16.
Franc Forstneric 《Journal of Geometric Analysis》1999,9(1):93-117
Let n > 1 and let
C
n
denote the complex n-dimensional Euclidean space. We prove several jet-interpolation results for nowhere degenerate entire
mappings F:C
n →C
n
and for holomorphic automorphisms of
C
n
on discrete subsets of
C
n.We also prove an interpolation theorem for proper holomorphic embeddings of Stein manifolds into
C
n.For each closed complex submanifold (or subvariety) M ⊂
C
n
of complex dimension m < n we construct a domain Ω ⊂C
n
containing M and a biholomorphic map F: Ω →
C
n
onto
C
n
with J F ≡ 1such that F(M) intersects the image of any nondegenerate entire map G:C
n−m →C
n
at infinitely many points. If m = n − 1, we construct F as above such that
C
n ∖F(M) is hyperbolic. In particular, for each m ≥ 1we construct proper holomorphic embeddings F:C
m →C
m−1
such that the complement
C
m+1 ∖F(C
m
)is hyperbolic. 相似文献
17.
Our main result states that for each finite complex L the category TOP of topological spaces possesses a model category structure (in the sense of Quillen) whose weak equivalences are precisely
maps which induce isomorphisms of all [L]-homotopy groups. The concept of [L]-homotopy has earlier been introduced by the first author and is based on Dranishnikov’s notion of extension dimension. As
a corollary we obtain an algebraic characterization of [L]-homotopy equivalences between [L]-complexes. This result extends two classical theorems of J. H. C. Whitehead. One of them – describing homotopy equivalences
between CW-complexes as maps inducing isomorphisms of all homotopy groups – is obtained by letting L = {point}. The other – describing n-homotopy equivalences between at most (n+1)-dimensional CW-complexes as maps inducing isomorphisms of k-dimensional homotopy groups with k ⩽ n – by letting L = S
n+1
, n ⩾ 0. 相似文献
18.
Preemptive scheduling with rejection 总被引:8,自引:0,他引:8
We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby
incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize
the preemptive makespan on the m machines plus the sum of the penalties of the jobs rejected.
We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main
results are on the variant with an arbitrary number of unrelated machines. This variant is APX-hard, and we design a 1.58-approximation
algorithm for it. All other considered variants are weakly -hard, and we provide fully polynomial time approximation schemes
for them. Finally, we argue that our results for unrelated machines can be carried over to the corresponding preemptive open
shop scheduling problem with rejection.
Received: October 30, 2000 / Accepted: September 26, 2001 Published online: September 5, 2002
Key words. scheduling – preemption – approximation algorithm – worst case ratio – computational complexity – in-approximability
Supported in part by the EU Thematic Network APPOL, Approximation and Online Algorithms, IST-1999-14084
Supported by the START program Y43-MAT of the Austrian Ministry of Science. 相似文献
19.
Toshinori Sakai 《Graphs and Combinatorics》2002,18(1):169-192
Let n≥2 be an integer and let μ1 and μ2 be measures in ℝ2 such that each μ
i
is absolutely continuous with respect to the Lebesgue measure and μ1(ℝ2)=μ2(ℝ2)=n. Let u≠0 be a vector on the plane. We show that if μ1(B)=μ2(B)=n for some bounded domain B, then there exist positive integers n
1,n
2 with n
1+n
2=n and disjoint open half-planes D
1,D
2 such that , μ1(D
1)=μ2(D
1)=n
1 and μ1(D
2)=μ2(D
2)=n
2; or there exist positive integers n
1,n
2,n
3 with n
1+n
2+n
3=n and disjoint open convex domains D
1,D
2,D
3 such that , μ1(D
1)=μ2(D
1)=n
1, μ1(D
2)= μ2(D
2)=n
2, μ1(D
3)=μ2(D
3)=n
3 and such that the ray is parallel to u. We also show a similar result for partitioning of point sets on the plane.
Received: November 24, 1999 Final version received: February 9, 2001 相似文献
20.
Raffaele Mosca 《Graphs and Combinatorics》2001,17(3):517-528
Let G be a graph with n vertices, and denote as γ(G) (as θ(G)) the cardinality of a minimum edge cover (of a minimum clique cover) of G. Let E (let C) be the edge-vertex (the clique-vertex) incidence matrix of G; write then P(E)={x∈ℜ
n
:Ex≤1,x≥0}, P(C)={x∈ℜ
n
:Cx≤1,x≥0}, α
E
(G)=max{1
T
x subject to x∈P(E)}, and α
C
(G)= max{1
T
x subject to x∈P(C)}. In this paper we prove that if α
E
(G)=α
C
(G), then γ(G)=θ(G).
Received: May 20, 1998?Final version received: April 12, 1999 相似文献