共查询到20条相似文献,搜索用时 46 毫秒
1.
Akira Hiraki 《Graphs and Combinatorics》2009,25(1):65-79
Let Γ be a distance-regular graph of diameter d ≥ 3 with c
2 > 1. Let m be an integer with 1 ≤ m ≤ d − 1. We consider the following conditions:
In [12] we have shown that the condition (SC)
m
holds if and only if both of the conditions (BB)
i
and (CA)
i
hold for i = 1,...,m. In this paper we show that if a
1 = 0 < a
2 and the condition (BB)
i
holds for i = 1,...,m, then the condition (CA)
i
holds for i = 1,...,m. In particular, the condition (SC)
m
holds. Applying this result we prove that a distance-regular graph with classical parameters (d, b, α, β) such that c
2 > 1 and a
1 = 0 < a
2 satisfies the condition (SC)
i
for i = 1,...,d − 1. In particular, either (b, α, β) = (− 2, −3, −1 − (−2)
d
) or holds. 相似文献
(SC) m : For any pair of vertices at distance m there exists a strongly closed subgraph of diameter m containing them. | |
(BB) m : Let (x, y, z) be a triple of vertices with ∂Γ(x, y) = 1 and ∂Γ(x, z) = ∂Γ(y, z) = m. Then B(x, z) = B(y, z). | |
(CA) m : Let (x, y, z) be a triple of vertices with and |C(z, x) ∩ C(z, y)| ≥ 2. Then C(x, z) ∪ A(x, z) = C(y, z) ∪ A(y, z). |
2.
Strongly Closed Subgraphs in a Distance-Regular Graph with <Emphasis Type="Italic">c</Emphasis><Subscript>2</Subscript> > 1 总被引:1,自引:1,他引:0
Akira Hiraki 《Graphs and Combinatorics》2008,24(6):537-550
Let Γ be a distance-regular graph of diameter d ≥ 3 with c
2 > 1. Let m be an integer with 1 ≤ m ≤ d − 1. We consider the following conditions:
Suppose that the condition (SC)
m
holds. Then it has been known that the condition (BB)
i
holds for all i with 1 ≤ i ≤ m. Similarly we can show that the condition (CA)
i
holds for all i with 1 ≤ i ≤ m. In this paper we prove that if the conditions (BB)
i
and (CA)
i
hold for all i with 1 ≤ i ≤ m, then the condition (SC)
m
holds. Applying this result we give a sufficient condition for the existence of a dual polar graph as a strongly closed subgraph
in Γ. 相似文献
(SC) m : For any pair of vertices at distance m there exists a strongly closed subgraph of diameter m containing them. | |
(BB) m : Let (x, y, z) be a triple of vertices with ∂ Γ (x, y) = 1 and ∂ Γ (x, z) = ∂ Γ (y, z) = m. Then B(x, z) = B(y, z). | |
(CA) m : Let (x, y, z) be a triple of vertices with ∂ Γ (x, y) = 2, ∂ Γ (x, z) = ∂ Γ (y, z) = m and |C(z, x) ∩ C(z, y)| ≥ 2. Then C(x, z) ∪ A(x, z) = C(y, z) ∪ A(y, z). |
3.
In this paper we consider the problem of determining whether an unknown arithmetic circuit, for which we have oracle access,
computes the identically zero polynomial. This problem is known as the black-box polynomial identity testing (PIT) problem.
Our focus is on polynomials that can be written in the form f([`(x)]) = ?i = 1k hi ([`(x)]) ·gi ([`(x)])f(\bar x) = \sum\nolimits_{i = 1}^k {h_i (\bar x) \cdot g_i (\bar x)} , where each h
i
is a polynomial that depends on only ρ linear functions, and each g
i
is a product of linear functions (when h
i
= 1, for each i, then we get the class of depth-3 circuits with k multiplication gates, also known as ΣΠΣ(k) circuits, but the general case is much richer). When max
i
(deg(h
i
· g
i
)) = d we say that f is computable by a ΣΠΣ(k; d;ρ) circuit. We obtain the following results.
1. |
A deterministic black-box identity testing algorithm for ΣΠΣ(k; d;ρ) circuits that runs in quasi-polynomial time (for ρ=polylog(n+d)). In particular this gives the first black-box quasi-polynomial time PIT algorithm for depth-3 circuits with k multiplication gates. 相似文献
4.
A. Yu. Volovikov 《Journal of Mathematical Sciences》2009,159(6):790-793
Let G be a finite group and X be a G-space. For a map f: X → ℝ
m
, the partial coincidence set A(f, k), k ≤ |G|, is the set of points x ∈ X such that there exist k elements g
1,…, g
k
of the group G, for which f(g
1
x) = ⋅⋅⋅ = f(g
k
x) holds. We prove that the partial coincidence set is nonempty for G = ℤ
p
n
under some additional assumptions.
Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 8, pp. 61–67, 2007. 相似文献
5.
Hans Peter Schlickewei Wolfgang M. Schmidt Michel Waldschmidt 《manuscripta mathematica》1999,98(2):225-241
Let be an exponential polynomial over a field of zero characteristic. Assume that for each pair i,j with i≠j, α
i
/α
j
is not a root of unity. Define . We introduce a partition of into subsets (1≤i≤m), which induces a decomposition of f into , so that, for 1≤i≤m, , while for , the number either is transcendental or else is algebraic with not too small a height. Then we show that for all but at most solutions x∈ℤ of f(x)= 0, we have
6.
Let gzs(m, 2k) (gzs(m, 2k+1)) be the minimal integer such that for any coloring Δ of the integers from 1, . . . , gzs(m, 2k) by (the integers from 1 to gzs(m, 2k+1) by ) there exist integers
such that
1. there exists jx such that Δ(xi) ∈ for each i and ∑i=1m Δ(xi) = 0 mod m (or Δ(xi)=∞ for each i);
2. there exists jy such that Δ(yi) ∈ for each i and ∑i=1m Δ(yi) = 0 mod m (or Δ(yi)=∞ for each i); and
1. 2(xm−x1)≤ym−x1.
In this note we show gzs(m, 2)=5m−4 for m≥2, gzs(m, 3)=7m+−6 for m≥4, gzs(m, 4)=10m−9 for m≥3, and gzs(m, 5)=13m−2 for m≥2.
Supported by NSF grant DMS 0097317 相似文献
7.
In a symmetrizable Kac–Moody algebra g(A), let α=∑i=1nkiαi be an imaginary root satisfying ki>0 and α,αi<0 for i=1,2,…,n. In this paper, it is proved that for any xαgα{0}, satisfying [xα,fn]≠0 and [xα,fi]=0 for i=1,2,…,n−1, there exists a vector y such that the subalgebra generated by xα and y contains g′(A), the derived subalgebra of g(A). 相似文献
8.
Maks A. Akivis Vladislav V. Goldberg Valentin V. Lychagin 《Selecta Mathematica, New Series》2005,10(4):431-451
We find d − 2 relative differential invariants for a d-web, d ≥ 4, on a two-dimensional manifold and prove that their vanishing is necessary and sufficient for a d-web to be linearizable. If one writes the above invariants in terms of web functions f(x, y) and g
4(x, y),..., g
d
(x, y), then necessary and sufficient conditions for the linearizabilty of a d-web are two PDEs of the fourth order with respect to f and g
4, and d − 4 PDEs of the second order with respect to f and g
4,..., g
d
. For d = 4, this result confirms Blaschke’s conjecture on the nature of conditions for the linearizabilty of a 4-web. We also give
the Mathematica codes for testing 4- and d-webs (d > 4) for linearizability and examples of their usage. 相似文献
9.
How Close to Regular Must a Semicomplete Multipartite Digraph Be to Secure Hamiltonicity? 总被引:1,自引:0,他引:1
Anders Yeo 《Graphs and Combinatorics》1999,15(4):481-493
Let D be a semicomplete multipartite digraph, with partite sets V
1, V
2,…, V
c, such that |V
1|≤|V
2|≤…≤|V
c|. Define f(D)=|V(D)|−3|V
c|+1 and . We define the irregularity i(D) of D to be max|d
+(x)−d
−(y)| over all vertices x and y of D (possibly x=y). We define the local irregularity i
l(D) of D to be max|d
+(x)−d
−(x)| over all vertices x of D and we define the global irregularity of D to be i
g(D)=max{d
+(x),d
−(x) : x∈V(D)}−min{d
+(y),d
−(y) : y∈V(D)}. In this paper we show that if i
g(D)≤g(D) or if i
l(D)≤min{f(D), g(D)} then D is Hamiltonian. We furthermore show how this implies a theorem which generalizes two results by Volkmann and solves a stated
problem and a conjecture from [6]. Our result also gives support to the conjecture from [6] that all diregular c-partite tournaments (c≥4) are pancyclic, and it is used in [9], which proves this conjecture for all c≥5. Finally we show that our result in some sense is best possible, by giving an infinite class of non-Hamiltonian semicomplete
multipartite digraphs, D, with i
g(D)=i(D)=i
l(D)=g(D)+?≤f(D)+1.
Revised: September 17, 1998 相似文献
10.
Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integer-valuated functions defined on V(G) such that g(x) ≤f(x) for all x∈V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤d
H
(x) ≤f(x) for all x∈V(G). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let
= {F
1, F
2, ..., F
m
} be a factorization of G and H be a subgraph of G with mr edges. If F
i
, 1 ≤i≤m, has exactly r edges in common with H, then
is said to be r-orthogonal to H. In this paper it is proved that every (mg + kr, mf−kr)-graph, where m, k and r are positive integers with k < m and g≥r, contains a subgraph R such that R has a (g, f)-factorization which is r-orthogonal to a given subgraph H with kr edges.
This research is supported by the National Natural Science Foundation of China (19831080) and RSDP of China 相似文献
11.
Aregression is a functiong from a partially ordered set to itself such thatg(x)≦x for allz. Amonotone k-chain is a chain ofk elementsx
1<x
2 <...<x
k
such thatg(x
1)≦g(x
2)≦...≦g(x
k
). If a partial order has sufficiently many elements compared to the size of its largest antichain, every regression on it
will have a monotone (k + 1)-chain. Fixingw, letf(w, k) be the smallest number such that every regression on every partial order with size leastf(w, k) but no antichain larger thanw has a monotone (k + 1)-chain. We show thatf(w, k)=(w+1)
k
.
Dedicated to Paul Erdős on his seventieth birthday
Research supported in part by the National Science Foundation under ISP-80-11451. 相似文献
12.
Vincenzo De Filippis 《Israel Journal of Mathematics》2007,162(1):93-108
Let R be a prime ring with extended centroid C, g a nonzero generalized derivation of R, f (x
1,..., x
n) a multilinear polynomial over C, I a nonzero right ideal of R.
If [g(f(r
1,..., r
n)), f(r
1,..., r
n)] = 0, for all r
1, ..., r
n ∈ I, then either g(x) = ax, with (a − γ)I = 0 and a suitable γ ∈ C or there exists an idempotent element e ∈ soc(RC) such that IC = eRC and one of the following holds:
13.
Simple graphs are considered. Let G be a graph andg(x) andf(x) integer-valued functions defined on V(G) withg(x)⩽f(x) for everyxɛV(G). For a subgraphH ofG and a factorizationF=|F
1,F
2,⃛,F
1| ofG, if |E(H)∩E(F
1)|=1,1⩽i⩽j, then we say thatF orthogonal toH. It is proved that for an (mg(x)+k,mf(x) -k)-graphG, there exists a subgraphR ofG such that for any subgraphH ofG with |E(H)|=k,R has a (g,f)-factorization orthogonal toH, where 1⩽k<m andg(x)⩾1 orf(x)⩾5 for everyxɛV(G).
Project supported by the Chitia Postdoctoral Science Foundation and Chuang Xin Foundation of the Chinese Academy of Sciences. 相似文献
14.
V. G. Krotov 《Ukrainian Mathematical Journal》2010,62(3):441-451
We prove the following statement, which is a quantitative form of the Luzin theorem on C-property: Let (X, d, μ) be a bounded metric space with metric d and regular Borel measure μ that are related to one another by the doubling condition. Then, for any function f measurable on X, there exist a positive increasing function η ∈ Ω (η(+0) = 0 and η(t)t
−a
decreases for a certain a > 0), a nonnegative function g measurable on X, and a set E ⊂ X, μE = 0 , for which
|