共查询到20条相似文献,搜索用时 15 毫秒
1.
We study rings and K-algebras in which all elements or all noncentral elements have smallest possible centralizer. Our principal result asserts
that a ring R must be either finite or commutative if each noncentral element a has centralizer equal to the subring generated by a. 相似文献
2.
LetG be a quasisimple Chevalley group. We give an upper bound for the covering number cn(G) which is linear in the rank ofG, i.e. we give a constantd such that for every noncentral conjugacy classC ofG we haveC
rd
=G, wherer=rankG.
Research supported in part by NSERC Canada Grant A7251.
Research supported in part by the Hermann Minkowski-Minerva Center for Geometry at Tel Aviv University. 相似文献
3.
We prove the following theorem for a finitely generated field K: Let M be a Galois extension of K which is not separably closed. Then M is not PAC over K.
Research supported by the Minkowski Center for Geometry at Tel Aviv University, established by the Minerva Foundation.
This work constitutes a part of the Ph.D. dissertation of L. Bary-Soroker done at Tel Aviv University under the supervision
of Prof. Dan Haran. 相似文献
4.
The overlay of 2≤m≤d minimization diagrams of n surfaces in ℝ
d
is isomorphic to a substructure of a suitably constructed minimization diagram of mn surfaces in ℝ
d+m−1. This elementary observation leads to a new bound on the complexity of the overlay of minimization diagrams of collections
of d-variate semi-algebraic surfaces, a tight bound on the complexity of the overlay of minimization diagrams of collections of
hyperplanes, and faster algorithms for constructing such overlays. Further algorithmic implications are discussed.
Work by V. Koltun was supported by NSF CAREER award CCF-0641402.
Work by M. Sharir was supported by NSF Grants CCR-00-98246 and CCF-05-14079, by a grant from the Israeli Academy of Sciences
for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski Minerva Center for
Geometry at Tel Aviv University. 相似文献
5.
L. J. Guibas D. Halperin J. Matoušek M. Sharir 《Discrete and Computational Geometry》1995,14(1):113-122
We show that, for any collection ℋ ofn hyperplanes in ℜ4, the combinatorial complexity of thevertical decomposition of the arrangementA(ℋ) of ℋ isO(n
4 logn). The proof relies on properties of superimposed convex subdivisions of 3-space, and we also derive some other results concerning
them.
Work on this paper by Leonidas Guibas and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science
Foundation. Work by Leonidas Guibas was also supported by National Science Foundation Grant CCR-9215219. Work by Micha Sharir
was also supported by National Science Foundation Grant CCR-91-22103, and by grants from the G.I.F.—the German Isreali Foundation
for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.
Work by Jiří Matouŝek was done while he was visiting Tel Aviv University, and its was partially supported by a Humboldt Research
Fellowship. Work on this paper by Dan Halperin was carried out while he was at Tel Aviv University. 相似文献
6.
This paper describes an optimization algorithm which uses up torth-order derivatives to find the optimum of anr-times continuously differentiable function of many variables. The algorithm, developed by Kalaba and Tishler (Ref. 1), obtains the exact values of the derivatives required for the optimization from the table algorithm presented in Kalabaet al. (Ref. 2) and Kalaba and Tishler (Ref. 3). The optimization algorithm described here reduces to the well-known Newton-Raphson algorithm when only first-order and second-order derivatives are used.on leave from the Faculty of Management, Tel Aviv University, Tel Aviv, Israel. 相似文献
7.
The co-degrees of irreducible characters 总被引:1,自引:0,他引:1
LetG be a finite group. The co-degree of an irreducible character χ ofG is defined to be the number |G|/χ(1). The set of all prime divisors of all the co-degrees of the nonlinear irreducible characters ofG is denoted by Σ(G). First we show that Σ(G)=π(G) (the set of all prime divisors of |G|) unlessG is nilpotent-by-abelian. Then we make Σ(G) a graph by adjoining two elements of Σ(G) if and only if their product divides a co-degree of some nonlinear character ofG. We show that the graph Σ(G) is connected and has diameter at most 2. Additional information on the graph is given. These results are analogs to theorems
obtained for the graph corresponding to the character degrees (by Manz, Staszewski, Willems and Wolf) and for the graph corresponding
to the class sizes (by Bertram, Herzog and Mann). Finally, we investigate groups with some restriction on the co-degrees.
Among other results we show that ifG has a co-degree which is ap-power for some primep, then the corresponding character is monomial andO
p
(G)≠1. Also we describe groups in which each co-degree of a nonlinear character is divisible by at most two primes. These results
generalize results of Chillag and Herzog. Other results are proved as well.
The paper was written during this author’s visit at the Technion and the University of Tel Aviv. He would like to thank the
departments of mathematics at the Technion and the University of Tel Aviv for their hospitality and support. 相似文献
8.
Let G be a topological graph with n vertices, i.e., a graph drawn in the plane with edges drawn as simple Jordan curves. It is shown that, for any constants
k,l, there exists another constant C(k,l), such that if G has at least C(k,l)n edges, then it contains a k×l-gridlike configuration, that is, it contains k+l edges such that each of the first k edges crosses each of the last l edges. Moreover, one can require the first k edges to be incident to the same vertex.
Received: April, 2003
Janos Pach and Micha Sharir has been supported by NSF Grants CCR-97-32101 and CCR-00-98246, and by a joint grant from the
U.S.–Israel Binational Science Foundation. János Pach has also been supported by PSC-CUNY Research Award 63382-0032 and by
OTKA T-032452. Micha Sharir has also been supported by a grant from the Israeli Academy of Sciences for a Center of Excellence
in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University.
Géza Tóth has been supported by OTKA-T-038397 and by an award from the New York University Research Challenge Fund. 相似文献
9.
One of the main problems in the theory of quaternion quantum mechanics has been the construction of a tensor product of quaternion Hilbert modules. A solution to this problem is given by studying the tensor product of quaternion algebras (over the reals) and some of its quotient modules. Real, complex, and (covariant) quaternion scalar products are found in the tensor product spaces. Annihilationcreation operators are constructed, corresponding to the second quantization of the quaternion quantum theory with Bose-Einstein or Fermi-Dirac statistics. The gauge transformations of a tensor product vector and the gauge fields are studied.On Sabbatical leave from the School of Physics and Astronomy, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel. Work supported in part by a fellowship from the Ambrose Monell Foundation. 相似文献
10.
Following the construction of tensor product spaces of quaternion Hilbert modules in our previous paper, we define the analogue of a ray (in a complex quantum mechanics) and the corresponding projection operator, and through these the notion of a state and density operators. We find that there is a one-to-one correspondence between a state and an equivalence class of vectors from the tensor product space, which gives us another method to define the gauge transformations.On sabbatical leave from the School of Physics and Astronomy, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel. Work supported in part by a fellowship from the Ambrose Monell Foundation. 相似文献
11.
We describe an explicit construction whicy, for some fixed absolute positive constant ε, produces, for every integers>1 and all sufficiently largem, a graph on at least
vertices containing neither a clique of sizes nor an independent set of sizem.
Part of this work was done at the Institute for Advanced Study, Princeton, NJ 08540, USA. Research supported in part by a
USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry
at Tel Aviv University.
Research supported in part by a grant A1019901 of the Academy of Sciences of the Czech Republic and by a cooperative research
grant INT-9600919/ME-103 from the NSF (USA) and the MŠMT (Czech Republic). 相似文献
12.
M. Sharir 《Israel Journal of Mathematics》1976,24(3-4):320-328
We give examples of extreme operators in the unit ball ofL(C(X),C(Y)) which are not nice operators (i.e., their adjoints do not carry extreme points into extreme points in the corresponding
unit balls.) Such counterexamples exist in fact for every non-dispersed compact Hausdorff spaceX when the scalars are complex.
This is part of the author’s Ph.D. thesis, prepared at Tel Aviv University under the supervision of Prof. A. J. Lazar. 相似文献
13.
Pankaj K. Agarwal Rolf Klein Christian Knauer Stefan Langerman Pat Morin Micha Sharir Michael Soss 《Discrete and Computational Geometry》2008,39(1-3):17-37
The detour and spanning ratio of a graph G embedded in
measure how well G approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe O(nlog n) time algorithms for computing the detour and spanning ratio of a planar polygonal path. By generalizing these algorithms,
we obtain O(nlog 2
n)-time algorithms for computing the detour or spanning ratio of planar trees and cycles. Finally, we develop subquadratic
algorithms for computing the detour and spanning ratio for paths, cycles, and trees embedded in
, and show that computing the detour in
is at least as hard as Hopcroft’s problem.
This research was partly funded by CRM, FCAR, MITACS, and NSERC. P.A. was supported by NSF under grants CCR-00-86013 EIA-99-72879,
EIA-01-31905, and CCR-02-04118, by ARO grants W911NF-04-1-0278 and DAAD19-03-1-0352, and by a grant from the U.S.-Israeli
Binational Science Foundation. R.K. was supported by DFG grant Kl 655/14-1. M.S. was supported by NSF Grants CCR-97-32101
and CCR-00-98246, by a grant from the U.S.-Israeli Binational Science Foundation (jointly with P.A.), by a grant from the
Israeli Academy of Sciences for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski–MINERVA
Center for Geometry at Tel Aviv University.
Some of these results have appeared in a preliminary form in [2, 20]. 相似文献
14.
Nir Halman 《Discrete and Computational Geometry》2008,39(4):690-719
Helly’s theorem says that if every d+1 elements of a given finite set of convex objects in ℝ
d
have a common point, then there is a point common to all of the objects in the set. We define three new types of Helly theorems:
discrete Helly theorems—where the common point should belong to an a-priori given set, lexicographic Helly theorems—where
the common point should not be lexicographically greater than a given point, and lexicographic-discrete Helly theorems. We
study the relations between the different types of the Helly theorems. We obtain several new discrete and lexicographic Helly
numbers.
An extended abstract containing parts of this work appeared in the proceedings of the Forty-Fifth Annual Symposium on Foundations
of Computer Science (FOCS) 2004.
This work is part of the author’s Ph.D. thesis, prepared in the school of mathematical sciences at Tel Aviv University, under
the supervision of Professor Arie Tamir. 相似文献
15.
Marc van Kreveld Joseph S. B. Mitchell Peter Rousseeuw Micha Sharir Jack Snoeyink Bettina Speckmann 《Discrete and Computational Geometry》2008,39(4):656-677
We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(n
d
) time and O(n
d−1) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog 2
n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299–309, [2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric
and algorithmic results.
A preliminary version of this paper appeared in the proceedings of the 15th Annual ACM Symposium on Computational Geometry
(1999)
M. van Kreveld partially funded by the Netherlands Organization for Scientific Research (NWO) under FOCUS/BRICKS grant number
642.065.503.
J.S.B. Mitchell’s research largely conducted while the author was a Fulbright Research Scholar at Tel Aviv University. The
author is partially supported by NSF (CCR-9504192, CCR-9732220), Boeing, Bridgeport Machines, Sandia, Seagull Technology,
and Sun Microsystems.
M. Sharir supported by NSF Grants CCR-97-32101 and CCR-94-24398, by grants from the U.S.–Israeli Binational Science Foundation,
the G.I.F., the German–Israeli Foundation for Scientific Research and Development, and the ESPRIT IV LTR project No. 21957
(CGAL), and by the Hermann Minkowski—MINERVA Center for Geometry at Tel Aviv University.
J. Snoeyink supported in part by grants from NSERC, the Killam Foundation, and CIES while at the University of British Columbia. 相似文献
16.
Noga Alon 《Israel Journal of Mathematics》2000,117(1):125-130
We prove that for every odd primep, everyk≤p
and every two subsets
A={a
1, …,a
k
} andB={b
1, …,b
k
} of cardinalityk each ofZ
p
, there is a permutationπ ∈S
k
such that the sumsa
i
+b
π(i) (inZ
p
) are pairwise distinct. This partially settles a question of Snevily. The proof is algebraic, and implies several related
results as well.
Research supported in part by a State of New Jersey grant and by the Hermann Minkowski Minerva Center for Geometry at Tel
Aviv University. 相似文献
17.
O. Palmon 《Israel Journal of Mathematics》1992,80(3):337-349
We can extend the Banach-Mazur distance to be a distance between non-symmetric sets by allowing affine transformations instead
of linear transformations. It was proved in [J] that for every convex bodyK we haved(K, D)≤n. It is proved that ifK is a convex body in ℝ
n
such thatd(K, D)=n, thenK is a simplex.
This article is an M.Sc. thesis written under the supervision of E. Gluskin and V.D. Milman at Tel Aviv University.
Partially supported by a G.I.F. grant. 相似文献
18.
Dedicated to the memory of Paul Erdős
A graph is called H-free if it contains no induced copy of H. We discuss the following question raised by Erdős and Hajnal. Is it true that for every graph H, there exists an such that any H-free graph with n vertices contains either a complete or an empty subgraph of size at least ? We answer this question in the affirmative for a special class of graphs, and give an equivalent reformulation for tournaments.
In order to prove the equivalence, we establish several Ramsey type results for tournaments.
Received August 22, 1999
RID="*"
ID="*" Supported by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva
Center for Geometry at Tel Aviv University.
RID="†"
ID="†" Supported by NSF grant CR-9732101, PSC-CUNY Research Award 663472, and OTKA-T-020914.
RID="‡"
ID="‡" Supported by TKI grant Stochastics@TUB, and OTKA-T-026203. 相似文献
19.
In this paper, we take advantage of the availability of higher-order derivatives through the table method (see Ref. 1) and suggest a simple variant of the Lagrangian method for constrained optimization. Our method, and the software that we currently have can be used to minimize functions with many variables subject to an arbitrary number of constraints.On leave from the Faculty of Management, Tel Aviv University, Tel Aviv, Israel. 相似文献
20.
We consider the problem of planning the motion of an arbitraryk-sided polygonal robotB, free to translate and rotate in a polygonal environmentV bounded byn edges. We present an algorithm that constructs a single component of the free configuration space ofB in timeO((kn)
2+ɛ), for any ɛ>0. This algorithm, combined with some standard techniques in motion planning, yields a solution to the underlying
motion-planning problem, within the same running time.
Work on this paper by Dan Halperin has been supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford
Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. Work on this paper
by Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-93-11127, by a Max-Planck Research Award, and by grants
from the U.S.-Israeli Binational Science Foundation, the Israel Science Fund administered by the Israeli Academy of Sciences,
and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. A preliminary and extended version
of the paper has appeared as: D. Halperin and M. Sharir, Near-quadratic bounds for the motion planning problem for a polygon
in a polygonal environment,Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993, pp. 382–391. Part of the work on the paper was carried out while Dan Halperin was at Tel Aviv University. 相似文献