共查询到20条相似文献,搜索用时 31 毫秒
1.
The Monodromy Conjecture asserts that if c is a pole of the local topological zeta function of a hypersurface, then exp(2πic) is an eigenvalue of the monodromy on the cohomology of the Milnor fiber. A stronger version of the conjecture asserts that
every such c is a root of the Bernstein-Sato polynomial of the hypersurface. In this note we prove the weak version of the conjecture
for hyperplane arrangements. Furthermore, we reduce the strong version to the following conjecture: −n/d is always a root of the Bernstein-Sato polynomial of an indecomposable essential central hyperplane arrangement of d hyperplanes in C
n
. 相似文献
2.
We present an application of the topological approach of Kahn, Saks and Sturtevant to the evasiveness conjecture for monotone graph properties. Although they proved evasiveness for every prime power of vertices, the best asymtotic lower bound for the (decision tree) complexity c(n) known so far is ¼n 2, proved in the same paper. In case that the evasiveness conjecture holds, it is ½n(n?1).We demonstrate some techniques to improve the 1/4 bound and show $ c(n) \geqslant \tfrac{8} {{25}}n^2 - o(n^2 ) We present an application of the topological approach of Kahn, Saks and Sturtevant to the evasiveness conjecture for monotone
graph properties. Although they proved evasiveness for every prime power of vertices, the best asymtotic lower bound for the
(decision tree) complexity c(n) known so far is ?n
2, proved in the same paper. In case that the evasiveness conjecture holds, it is ?n(n−1).We demonstrate some techniques to improve the 1/4 bound and show $
c(n) \geqslant \tfrac{8}
{{25}}n^2 - o(n^2 )
$
c(n) \geqslant \tfrac{8}
{{25}}n^2 - o(n^2 )
. 相似文献
3.
A. V. Kostochka 《Combinatorica》1982,2(2):187-192
Letf(n) denote the minimal number of edges of a 3-uniform hypergraphG=(V, E) onn vertices such that for every quadrupleY ⊂V there existsY ⊃e ∈E. Turán conjectured thatf(3k)=k(k−1)(2k−1). We prove that if Turán’s conjecture is correct then there exist at least 2
k−2 non-isomorphic extremal hypergraphs on 3k vertices. 相似文献
4.
We prove a new, tight upper bound on the number of incidences between points and hyperplanes in Euclidean d-space. Given n points, of which k are colored red, there are O
d
(m
2/3
k
2/3
n
(d−2)/3+kn
d−2+m) incidences between the k red points and m hyperplanes spanned by all n points provided that m=Ω(n
d−2). For the monochromatic case k=n, this was proved by Agarwal and Aronov (Discrete Comput. Geom. 7(4):359–369, 1992). 相似文献
5.
M. Stiebitz 《Combinatorica》1987,7(3):303-312
Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed.
In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc
k
n
2 edges must be removed.
In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph. 相似文献
6.
M. R. Emamy-K 《Annals of Operations Research》2011,188(1):141-153
A cut-complex is a cubical complex whose vertices are strictly separable from the rest of the vertices of the n-cube by a hyperplane of R
n
. These objects render geometric presentations for threshold Boolean functions, the core objects of study in threshold logic.
By applying cubical lattices and geometry of rotating hyperplanes, we prove necessary and sufficient conditions to recognize
the cut-complexes with 2 or 3 maximal faces. This result confirms a positive answer to an old conjecture of Metropolis-Rota
concerning cubical lattices. 相似文献
7.
By introducing redundant Klee–Minty examples, we have previously shown that the central path can be bent along the edges of
the Klee–Minty cubes, thus having 2
n
−2 sharp turns in dimension n. In those constructions the redundant hyperplanes were placed parallel with the facets active at the optimal solution. In
this paper we present a simpler and more powerful construction, where the redundant constraints are parallel with the coordinate-planes.
An important consequence of this new construction is that one of the sets of redundant hyperplanes is touching the feasible
region, and N, the total number of the redundant hyperplanes is reduced by a factor of n
2, further tightening the gap between iteration-complexity upper and lower bounds. 相似文献
8.
Let ℝ
n
be the n-dimensional Euclidean space. Let ∧ be a lattice of determinant 1 such that there is a sphere |X| < R which contains no point of ∧ other than the origin O and has n linearly independent points of ∧ on its boundary. A well known conjecture in the geometry of numbers asserts that any closed
sphere in ℝ
n
of radius $
\sqrt {n/4}
$
\sqrt {n/4}
contains a point of ∧. This is known to be true for n ≤ 8. Here we give estimates on a more general conjecture of Woods for n ≥ 9. This leads to an improvement for 9 ≤ n ≤ 22 on estimates of Il’in (1991) to the long standing conjecture of Minkowski on product of n non-homogeneous linear forms. 相似文献
9.
S. I. Tsupiy 《Journal of Mathematical Sciences》2007,144(2):4023-4029
In this paper, the set of quivers of semi-maximal rings is investigated. It is proved that the elements of this set are formed
by the elements of the set of quivers of tiled orders and that the set of quivers of tiled orders with n vertices is determined by the integer points of a convex polyhedral domain that lie in the nonnegative part of the space
. It is also proved that the set of quivers of tiled orders with n vertices contains all simple, oriented, strongly connected graphs with n vertices and n loops, does not contain any graphs with n vertices and n − 1 loops, and contains only a part of the graphs with n vertices and m (m < n − 1) loops.
__________
Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 11, No. 3, pp. 215–223, 2005. 相似文献
10.
Ervin Győri 《Combinatorica》1981,1(4):377-380
The problem is the following: How many questions are necessary in the worst case to determine whether a pointX in then-dimensional Euclidean spaceR
n
belongs to then-dimensional unit cubeQ
n, where we are allowed to ask which halfspaces of (n−1)-dimensional hyperplanes contain the pointX? It is known that ⌌3n/2⌍ questions are sufficient. We prove here thatcn questions are necessary, wherec≈1.2938 is the solution of the equationx log2
x−(x−1) log2 (x−1)=1. 相似文献
11.
V. A. Voblyi 《Mathematical Notes》1977,21(1):36-39
Let t(r, n) be the number of trees with n vertices of which r are hanging and q are internal (r=n−9). For a fixed r or q we
prove the validity of the asymptotic formulas (r > 2)t(r, n)≈t/r|(r−2)| 22−r
n
2r−4 (n→∞)t(n−q, n)≈1/q|(q−1)|q
q−2
n
q−1 (n→∞) In the derivation of these formulas we do not use the expression for the enumerator of the trees with respect to the number
of hanging vertices.
Translated from Matematicheskie Zametki, Vol. 21, No. 1, pp. 65–70, January, 1977. 相似文献
12.
We define a centrally symmetric analogue of the cyclic polytope and study its facial structure. We conjecture that our polytopes
provide asymptotically the largest number of faces in all dimensions among all centrally symmetric polytopes with n vertices of a given even dimension d=2k when d is fixed and n grows. For a fixed even dimension d=2k and an integer 1≤j<k we prove that the maximum possible number of j-dimensional faces of a centrally symmetric d-dimensional polytope with n vertices is at least
for some c
j
(d)>0 and at most
as n grows. We show that c
1(d)≥1−(d−1)−1 and conjecture that the bound is best possible.
Research of A. Barvinok partially supported by NSF grant DMS 0400617.
Research of I. Novik partially supported by Alfred P. Sloan Research Fellowship and NSF grant DMS-0500748. 相似文献
13.
H. Guggenheimer 《Israel Journal of Mathematics》1965,3(2):104-112
A complete proof is given for Schnirelmann’s theorem on the existence of a square inC
2 Jordan curves. The following theorems are then proved, using the same method: 1. On every hypersurface inR
n,C
3-diffeomorphic toS
n−1, there exist 2n points which are the vertices of a regular 2
n
-cellC
n. 2. Every planeC′ Jordan curve can beC′ approximated by a curve on which there are 2N distinct points which are the vertices of a centrally symmetric 2N-gon (anglesπ not excluded). 3. On every planeC
2 curve there exist 5 distinct points which are the vertices of an axially symmetric pentagon with given base anglesa, π/2≦a<π. (The angle at the vertex on the axis of symmetry might beπ).
Research supported by Grant AF-AFOSR-664-64, Air Force Office of Scientific Research. 相似文献
14.
Let λK
m,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A P
v-factorization of λK
m,n is a set of edge-disjoint P
v
-factors of λK
m,n which partition the set of edges of λK
m,n. When v is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence
of a P
v
-factorization of λK
m,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true for v = 3. In this paper we will show that the conjecture is true when v = 4k − 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P
4k−1-factorization of λK
m,n is (1) (2k − 1)m ⩽ 2kn, (2) (2k − 1)n ⩽ 2km, (3) m + n ≡ 0 (mod 4k − 1), (4) λ(4k − 1)mn/[2(2k − 1)(m + n)] is an integer. 相似文献
15.
A collection of n hyperplanes in
d
forms a hyperplane arrangement. The depth of a point is the smallest number of hyperplanes crossed by any ray emanating from θ . For d=2 we prove that there always exists a point θ with depth at least . For higher dimensions we conjecture that the maximal depth is at least . For arrangements in general position, an upper bound on the maximal depth is also established. Finally, we discuss algorithms
to compute points with maximal depth.
Received December 1, 1997, and in revised form June 6, 1998. 相似文献
16.
The convexity theory for oriented matroids, first developed by Las Vergnas [17], provides the framework for a new computational
approach to the Steinitz problem [13]. We describe an algorithm which, for a given combinatorial (d − 2)-sphereS withn vertices, determines the setC
d,n(S) of rankd oriented matroids withn points and face latticeS. SinceS is polytopal if and only if there is a realizableM εC
d,n(S), this method together with the coordinatizability test for oriented matroids in [10] yields a decision procedure for the
polytopality of a large class of spheres. As main new result we prove that there exist 431 combinatorial types of neighborly
5-polytopes with 10 vertices by establishing coordinates for 98 “doubted polytopes” in the classification of Altshuler [1].
We show that for alln ≧k + 5 ≧8 there exist simplicialk-spheres withn vertices which are non-polytopal due to the simple fact that they fail to be matroid spheres. On the other hand, we show
that the 3-sphereM
963
9
with 9 vertices in [2] is the smallest non-polytopal matroid sphere, and non-polytopal matroidk-spheres withn vertices exist for alln ≧k + 6 ≧ 9. 相似文献
17.
We show that the total number of faces bounding any one cell in an arrangement ofn (d−1)-simplices in ℝ
d
isO(n
d−1 logn), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational
motion planning in polyhedral environments. We than extend our analysis to derive other results on complexity in arrangements
of simplices. For example, we show that in such an arrangement the total number of vertices incident to the same cell on more
than one “side” isO(n
d−1
logn). We, also show that the number of repetitions of a “k-flap,” formed by intersectingd−k given simplices, along the boundary of the same cell, summed over all cells and allk-flaps, isO(n
d−1
log2
n). We use this quantity, which we call theexcess of the arrangement, to derive bounds on the complexity ofm distinct cells of such an arrangement.
Work on this paper by the first author has been partially supported by National Science Foundation Grant CCR-92-11541. Work
on this paper by the second author has been supported by Office of Naval Research Grant N00014-90-J-1284, by National Science
Foundation Grants CCR-89-01484 and CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F.—the
German-Israeli Foundation for Scientific Reseach and Development, and the Fund for Basic Research administered by the Israeli
Academy of Sciences. 相似文献
18.
Joseph E. Bonin 《Annals of Combinatorics》2011,15(4):619-624
A matroid is sticky if any two of its extensions by disjoint sets can be glued together along the common restriction (that
is, they have an amalgam). The sticky matroid conjecture asserts that a matroid is sticky if and only if it is modular. Poljak
and Turzík proved that no rank-3 matroid having two disjoint lines is sticky. We show that, for r ≥ 3, no rank−r matroid having two disjoint hyperplanes is sticky. These and earlier results show that the sticky matroid conjecture for
finite matroids would follow from a positive resolution of the rank-4 case of a conjecture of Kantor. 相似文献
19.
(2,k)-Factor-Critical Graphs and Toughness 总被引:1,自引:0,他引:1
A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. with an r-regular spanning subgraph). We show that every τ-tough graph of order n with τ≥2 is (2,k)-factor-critical for every non-negative integer k≤min{2τ−2, n−3}, thus proving a conjecture as well as generalizing the main result of Liu and Yu in [4].
Received: December 16, 1996 / Revised: September 17, 1997 相似文献
20.
Jinfeng Feng 《Graphs and Combinatorics》2009,25(3):299-307
An arc in a tournament T with n ≥ 3 vertices is called pancyclic, if it is in a cycle of length k for all 3 ≤ k ≤ n. Yeo (Journal of Graph Theory, 50 (2005), 212–219) proved that every 3-strong tournament contains two distinct vertices whose all out-arcs are pancyclic, and
conjectured that each 2-strong tournament contains 3 such vertices. In this paper, we confirm Yeo’s conjecture for 3-strong
tournaments.
The author is an associate member of “Graduiertenkolleg: Hierarchie und Symmetrie in mathematischen Modellen (DFG)” at RWTH
Aachen University, Germany. 相似文献