共查询到20条相似文献,搜索用时 46 毫秒
1.
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 相似文献
2.
Fedor V. Fomin 《Graphs and Combinatorics》2003,19(1):91-99
We prove that for every 2-connected planar graph the pathwidth of its geometric dual is less than the pathwidth of its line
graph. This implies that pathwidth(H)≤ pathwidth(H
*)+1 for every planar triangulation H and leads us to a conjecture that pathwidth(G)≤pathwidth(G
*)+1 for every 2-connected graph G.
Received: May 8, 2001 Final version received: March 26, 2002
RID="*"
ID="*" I acknowledge support by EC contract IST-1999-14186, Project ALCOM-FT (Algorithms and Complexity - Future Technologies)
and support by the RFBR grant N01-01-00235.
Acknowledgments. I am grateful to Petr Golovach, Roland Opfer and anonymous referee for their useful comments and suggestions. 相似文献
3.
Let (M
n
,g) be a compact Riemannian manifold with a smooth boundary. In this paper, we give a Lichnerowicz-Obata type lower bound for
the first eigenvalue of the Laplacian of (M
n
,g) when M has a parallel p-form (2 ≤p≤n/2). This result follows from a new Bochner-Reilly's formula. Moreover, we give a characterization of the equality case when
(M
n
,g) is simply connected.
Received: 1 June 2001 相似文献
4.
T. S. Kopaliani 《Ukrainian Mathematical Journal》2008,60(12):2006-2014
We point out that if the Hardy–Littlewood maximal operator is bounded on the space L
p(t)(ℝ), 1 < a ≤ p(t) ≤ b < ∞, t ∈ ℝ, then the well-known characterization of the spaces L
p
(ℝ), 1 < p < ∞, by the Littlewood–Paley theory extends to the space L
p(t)(ℝ). We show that, for n > 1 , the Littlewood–Paley operator is bounded on L
p(t) (ℝ
n
), 1 < a ≤ p(t) ≤ b < ∞, t ∈ ℝ
n
, if and only if p(t) = const.
Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 12, pp. 1709–1715, December, 2008. 相似文献
5.
We say that n independent trajectories ξ1(t),…,ξ
n
(t) of a stochastic process ξ(t)on a metric space are asymptotically separated if, for some ɛ > 0, the distance between ξ
i
(t
i
) and ξ
j
(t
j
) is at least ɛ, for some indices i, j and for all large enough t
1,…,t
n
, with probability 1. We prove sufficient conitions for asymptotic separationin terms of the Green function and the transition
function, for a wide class of Markov processes. In particular,if ξ is the diffusion on a Riemannian manifold generated by
the Laplace operator Δ, and the heat kernel p(t, x, y) satisfies the inequality p(t, x, x) ≤ Ct
−ν/2 then n trajectories of ξ are asymptotically separated provided . Moreover, if for some α∈(0, 2)then n trajectories of ξ(α) are asymptotically separated, where ξ(α) is the α-process generated by −(−Δ)α/2.
Received: 10 June 1999 / Revised version: 20 April 2000 / Published online: 14 December 2000
RID="*"
ID="*" Supported by the EPSRC Research Fellowship B/94/AF/1782
RID="**"
ID="**" Partially supported by the EPSRC Visiting Fellowship GR/M61573 相似文献
6.
7.
We prove versions of the Dual Ramsey Theorem and the Dual Ellentuck Theorem for families of partitions which are defined
in terms of games.
Received: 8 July 1999 Published online: 19 December 2002
RID="*"
ID="*" The author wishes to thank the Swiss National Science Foundation for supporting him.
The authors thank the referee for helpful comments.
Mathematics Subject Classification (2000): 03E02, 05D10, 03E35
Key words or phrases: Dual Ramsey Theorem – Dual Ellentuck Theorem – Partitions – Games 相似文献
8.
In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs,
and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the
independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally
well-dominated graphs.
Received: September 13, 2001 Final version received: May 17, 2002
RID="*"
ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093)
RID="†"
ID="†" Supported by RUTCOR
RID="*"
ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093)
05C75, 05C69
Acknowledgments. The authors thank the referees for valuable suggestions. 相似文献
9.
Antonio J. Lozano Juan A. Mesa Frank Plastria 《Journal of Mathematical Modelling and Algorithms》2010,9(1):1-17
A line is sought in the plane which minimizes the sum of the k largest (Euclidean) weighted distances from n given points. This problem generalizes the known straight-line center and median problems and, as far as the authors are
aware, has not been tackled up to now. By way of geometric duality it is shown that such a line may always be found which
either passes through two of the given points or lying at equal weighted distance from three of these. This allows construction
of an algorithm to find all t-centrum lines for 1 ≤ t ≤ k in O((k + logn)n
3). Finally it is shown that both, the characterization of an optimal line and the algorithm, can be extended to any smooth
norm. 相似文献
10.
Maximal Energy Bipartite Graphs 总被引:1,自引:0,他引:1
Given a graph G, its energy E(G) is defined to be the sum of the absolute values of the eigenvalues of G. This quantity is used in chemistry to approximate the total π-electron energy of molecules and in particular, in case G is bipartite, alternant hydrocarbons. Here we show that if G is a bipartite graph with n vertices, then
must hold, characterize those bipartite graphs for which this bound is sharp, and provide an infinite family of maximal energy
bipartite graphs.
Received: December 1, 2000 Final version received: August 28, 2001
RID="*"
ID="*" The author thanks the Swedish Natural Science Research Council (NFR) – grant M12342-300 – for its support.
Acknowledgments. The authors would like to thank Ivan Gutman for encouraging them to write this paper, and for helpful discussions on this
topic. They also would like to thank Edwin van Dam for his reference concerning connected bipartite regular graphs with four
eigenvalues. 相似文献
11.
The Linear 2-Arboricity of Planar Graphs 总被引:2,自引:0,他引:2
Let G be a planar graph with maximum degree Δ and girth g. The linear 2-arboricity la
2(G) of G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose component trees are paths of length at most 2. We prove that (1) la
2(G)≤⌈(Δ+1)/2⌉+12; (2) la
2(G)≤⌈(Δ+1)/2⌉+6 if g≥4; (3) la
2(G)≤⌈(Δ+1)/2⌉+2 if g≥5; (4) la
2(G)≤⌈(Δ+1)/2⌉+1 if g≥7.
Received: June 28, 2001 Final version received: May 17, 2002
Acknowledgments. This work was done while the second and third authors were visiting the Institute of Mathematics, Academia Sinica, Taipei.
The financial support provided by the Institute is greatly appreciated. 相似文献
12.
We consider the M(t)/M(t)/m/m queue, where the arrival rate λ(t) and service rate μ(t) are arbitrary (smooth) functions of time. Letting pn(t) be the probability that n servers are occupied at time t (0≤ n≤ m, t > 0), we study this distribution asymptotically, for m→∞ with a comparably large arrival rate λ(t) = O(m) (with μ(t) = O(1)). We use singular perturbation techniques to solve the forward equation for pn(t) asymptotically. Particular attention is paid to computing the mean number of occupied servers and the blocking probability
pm(t). The analysis involves several different space-time ranges, as well as different initial conditions (we assume that at t = 0 exactly n0 servers are occupied, 0≤ n0≤ m). Numerical studies back up the asymptotic analysis.
AMS subject classification: 60K25,34E10
Supported in part by NSF grants DMS-99-71656 and DMS-02-02815 相似文献
13.
A metric space M is said to have the fibered approximation property in dimension n (briefly, M ∈ FAP(n)) if for any ɛ > 0, m ≥ 0 and any map g: $
\mathbb{I}
$
\mathbb{I}
m
× $
\mathbb{I}
$
\mathbb{I}
n
→ M there exists a map g′: $
\mathbb{I}
$
\mathbb{I}
m
× $
\mathbb{I}
$
\mathbb{I}
n
→ M such that g′ is ɛ-homotopic to g and dim g′ ({z} × $
\mathbb{I}
$
\mathbb{I}
n
) ≤ n for all z ∈ $
\mathbb{I}
$
\mathbb{I}
m
. The class of spaces having the FAP(n)-property is investigated in this paper. The main theorems are applied to obtain generalizations of some results due to Uspenskij
[11] and Tuncali-Valov [10]. 相似文献
14.
Sergei. S. Goncharov Valentina. S. Harizanov Julia. F. Knight Charles F. D. McCoy 《Archive for Mathematical Logic》2003,42(3):279-291
Let 𝒜 be a computable structure and let R be a new relation on its domain. We establish a necessary and sufficient condition for the existence of a copy ℬ of 𝒜 in
which the image of R (?R, resp.) is simple (immune, resp.) relative to ℬ. We also establish, under certain effectiveness conditions on 𝒜 and R, a necessary and sufficient condition for the existence of a computable copy ℬ of 𝒜 in which the image of R (?R, resp.) is simple (immune, resp.).
Received: 4 February 2001 Published online: 5 November 2002
RID="*"
ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899.
RID="*"
ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899.
RID="*"
ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899. 相似文献
15.
Michel Talagrand 《Israel Journal of Mathematics》1992,79(2-3):207-224
Consider a setA of symmetricn×n matricesa=(a
i,j)
i,j≤n
. Consider an independent sequence (g
i)
i≤n
of standard normal random variables, and letM=Esupa∈A|Σi,j⪯nai,jgigj|. Denote byN
2(A, α) (resp.N
t(A, α)) the smallest number of balls of radiusα for thel
2 norm ofR
n
2 (resp. the operator norm) needed to coverA. Then for a universal constantK we haveα(logN
2(A, α))1/4≤KM. This inequality is best possible. We also show that forδ≥0, there exists a constantK(δ) such thatα(logN
t≤K(δ)M.
Work partially supported by an N.S.F. grant. 相似文献
16.
Say that a function π:n
<ω
→n (henceforth called a predictor) k-constantly predicts a real xn
ω
if for almost all intervals I of length k, there is iI such that x(i)=π(x↾i). We study the k-constant prediction number v
n
const
(k), that is, the size of the least family of predictors needed to k-constantly predict all reals, for different values of n and k, and investigate their relationship.
Received: 27 June 2001 / Revised version: 10 September 2001 /
Published online: 10 October 2002
RID="*"
ID="*" Supported by Grant–in–Aid for Scientific Research (C)(2)12640124, Japan Society for the Promotion of Science
RID="†"
ID="†" Supported by The Israel Science Foundation founded by the Israel Academy of Sciences and Humanities. Publication 762 相似文献
17.
M.M. Cavalcanti V.N. Domingos Cavalcanti 《NoDEA : Nonlinear Differential Equations and Applications》2000,7(3):285-307
This paper is concerned to the existence, uniqueness and uniform decay for the solutions of the coupled Klein-Gordon-Schr?dinger
damped equations
where ω is a bounded domain of R
n
, n≤ 3, F : R
2→R is a C
1-function; γ, β; θ are constants such that γ, β > 0 and 1 ≤ 2θ≤ 2.
Received January 1999 – Accepted October 1999 相似文献
18.
Narong Punnim 《Graphs and Combinatorics》2002,18(4):781-785
Let ω(G) be the clique number of a graph G. We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values ω(G) completely cover a line segment [a,b] of positive integers. For an arbitrary graphic degree sequence d, we define min(ω,d) and max(ω,d) as follows:
where is the graph of realizations of d.
Thus the two invariants a:=min(ω,d) and b:=max(ω,d) naturally arise. For a graphic degree sequence d=r
n
:=(r,r,…,r) where r is the vertex degree and n is the number of vertices, the exact values of a and b are found in all situations. Since the independence number, α(G)=ω(Gˉ), we obtain parallel results for the independence number of graphs.
Received: October, 2001 Final version received: July 25, 2002
RID="*"
ID="*" Work supported by The Thailand Research Fund, under the grant number BRG/09/2545 相似文献
19.
Sung Y. Song 《Graphs and Combinatorics》2002,18(3):655-665
Fusion relations between the association schemes obtained by direct product and wreath product are established via a study
of their matrix representations. The character table of the scheme obtained by the wreath product is described and some algebraic
properties of the products are derived.
Received: May 7, 1999 Final version received: September 24, 1999
RID="*"
ID="*" 1991 Mathematics Subject Classification. Primary 05E30; Secondary 05B99
RID="*"
ID="*" Supported in part by Com 2MaC-KOSEF, POSTECH, Korea
Acknowledgments. The author is indebted to an anonymous referee who provided the complete proof of Theorem 4.2. 相似文献
20.
Let M
m
be a m-dimensional submanifold in the n-dimensional unit sphere S
n
without umbilic point. Two basic invariants of M
m
under the M?bius transformation group of S
n
are a 1-form Φ called M?bius form and a symmetric (0,2) tensor A called Blaschke tensor. In this paper, we prove the following rigidity theorem: Let M
m
be a m-dimensional (m≥3) submanifold with vanishing M?bius form and with constant M?bius scalar curvature R in S
n
, denote the trace-free Blaschke tensor by . If , then either ||?||≡0 and M
m
is M?bius equivalent to a minimal submanifold with constant scalar curvature in S
n
; or and M
m
is M?bius equivalent to in for some c≥0 and .
Received: 15 May 2002 / Revised version: 3 February 2003
Published online: 19 May 2003
RID="*"
ID="*" Partially supported by grants of CSC, NSFC and Outstanding Youth Foundation of Henan, China.
RID="†"
ID="†" Partially supported by the Alexander Humboldt von Stiftung and Zhongdian grant of NSFC.
Mathematics Subject Classification (2000): Primary 53A30; Secondary 53B25 相似文献