共查询到20条相似文献,搜索用时 240 毫秒
1.
Yufei Zhao 《Journal of Number Theory》2010,130(5):1212-1220
A more sums than differences (MSTD) set is a finite subset S of the integers such that |S+S|>|S−S|. We construct a new dense family of MSTD subsets of {0,1,2,…,n−1}. Our construction gives Θ(n2/n) MSTD sets, improving the previous best construction with Ω(n2/n4) MSTD sets by Miller, Orosz, and Scheinerman. 相似文献
2.
Yufei Zhao 《Journal of Number Theory》2010,130(10):2308-2322
In an abelian group G, a more sums than differences (MSTD) set is a subset A⊂G such that |A+A|>|A−A|. We provide asymptotics for the number of MSTD sets in finite abelian groups, extending previous results of Nathanson. The proof contains an application of a recently resolved conjecture of Alon and Kahn on the number of independent sets in a regular graph. 相似文献
3.
Text
We explicitly construct infinite families of MSTD (more sums than differences) sets, i.e., sets where |A+A|>|A−A|. There are enough of these sets to prove that there exists a constant C such that at least C/r4 of the r2 subsets of {1,…,r} are MSTD sets; thus our family is significantly denser than previous constructions (whose densities are at most f(r)/2r/2 for some polynomial f(r)). We conclude by generalizing our method to compare linear forms ?1A+?+?nA with ?i∈{−1,1}.Video
For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=vIDDa1R2. 相似文献4.
5.
Vít Jelínek 《Discrete Applied Mathematics》2010,158(7):841-2876
Rank-width is a graph width parameter introduced by Oum and Seymour. It is known that a class of graphs has bounded rank-width if, and only if, it has bounded clique-width, and that the rank-width of G is less than or equal to its branch-width.The n×nsquare grid, denoted by Gn,n, is a graph on the vertex set {1,2,…,n}×{1,2,…,n}, where a vertex (x,y) is connected by an edge to a vertex (x′,y′) if and only if |x−x′|+|y−y′|=1.We prove that the rank-width of Gn,n is equal to n−1, thus solving an open problem of Oum. 相似文献
6.
Shaofang Hong 《Linear algebra and its applications》2008,428(4):1001-1008
Let a,b and n be positive integers and the set S={x1,…,xn} of n distinct positive integers be a divisor chain (i.e. there exists a permutation σ on {1,…,n} such that xσ(1)|…|xσ(n)). In this paper, we show that if a|b, then the ath power GCD matrix (Sa) having the ath power (xi,xj)a of the greatest common divisor of xi and xj as its i,j-entry divides the bth power GCD matrix (Sb) in the ring Mn(Z) of n×n matrices over integers. We show also that if a?b and n?2, then the ath power GCD matrix (Sa) does not divide the bth power GCD matrix (Sb) in the ring Mn(Z). Similar results are also established for the power LCM matrices. 相似文献
7.
Let e and n be positive integers and S={x1,…,xn} a set of n distinct positive integers. For x∈S, define . The n×n matrix whose (i,j)-entry is the eth power (xi,xj)e of the greatest common divisor of xi and xj is called the eth power GCD matrix on S, denoted by (Se). Similarly we can define the eth power LCM matrix [Se]. Bourque and Ligh showed that (S)∣[S] holds in the ring of n×n matrices over the integers if S is factor closed. Hong showed that for any gcd-closed set S with |S|≤3, (S)∣[S]. Meanwhile Hong proved that there is a gcd-closed set S with maxx∈S{|GS(x)|}=2 such that (S)?[S]. In this paper, we introduce a new method to study systematically the divisibility for the case maxx∈S{|GS(x)|}≤2. We give a new proof of Hong’s conjecture and obtain necessary and sufficient conditions on the gcd-closed set S with maxx∈S{|GS(x)|}=2 such that (Se)|[Se]. This partially solves an open question raised by Hong. Furthermore, we show that such factorization holds if S is a gcd-closed set such that each element is a prime power or the product of two distinct primes, and in particular if S is a gcd-closed set with every element less than 12. 相似文献
8.
Karola Mészáros 《Discrete Mathematics》2008,308(12):2366-2378
A generalized Latin square of type (n,k) is an n×n array of symbols 1,2,…,k such that each of these symbols occurs at most once in each row and each column. Let d(n,k) denote the cardinality of the minimal set S of given entries of an n×n array such that there exists a unique extension of S to a generalized Latin square of type (n,k). In this paper we discuss the properties of d(n,k) for k=2n-1 and k=2n-2. We give an alternate proof of the identity d(n,2n-1)=n2-n, which holds for even n, and we establish the new result . We also show that the latter bound is tight for n divisible by 10. 相似文献
9.
Demetres Christofides 《Journal of Combinatorial Theory, Series A》2007,114(5):906-918
A line in d[n] is a set {x(1),…,x(n)} of n elements of d[n] such that for each 1?i?d, the sequence is either strictly increasing from 1 to n, or strictly decreasing from n to 1, or constant. How many lines can a set S⊆d[n] of a given size contain?One of our aims in this paper is to give a counterexample to the Ratio Conjecture of Patashnik, which states that the greatest average degree is attained when S=d[n]. Our other main aim is to prove the result (which would have been strongly suggested by the Ratio Conjecture) that the number of lines contained in S is at most |S|2−ε for some ε>0.We also prove similar results for combinatorial, or Hales-Jewett, lines, i.e. lines such that only strictly increasing or constant sequences are allowed. 相似文献
10.
Igor E. Shparlinski 《Indagationes Mathematicae》2004,15(2):283-289
For a real x ≥ 1 we denote by S[x] the set of squarefull integers n ≤x, that is, the set of positive integers n ≤ such that l2|n for any prime divisor l|n. We estimate exponential sums of the form
11.
M. Zhao 《Operations Research Letters》2008,36(6):726-733
The continuous mixing set is , where w1,…,wn>0 and f1,…,fn∈ℜ. Let m=|{w1,…,wn}|. We show that when w1|?|wn, optimization over S can be performed in time O(nm+1), and in time O(nlogn) when w1=?=wn=1. 相似文献
12.
Yong Zhou 《Journal of Mathematical Analysis and Applications》2005,303(2):365-375
New oscillation and nonoscillation theorems are obtained for the second order quasilinear difference equation
Δ(|Δxn−1|ρ−1Δxn−1)+pn|xn|ρ−1xn=0, 相似文献
13.
In this paper we present a new combinatorial class enumerated by Catalan numbers. More precisely, we establish a bijection between the set of partitions π1π2?πn of [n] such that πi+1−πi≤1 for all i=,1,2…,n−1, and the set of Dyck paths of semilength n. Moreover, we find an explicit formula for the generating function for the number of partitions π1π2?πn of [n] such that either πi+?−πi≤1 for all i=1,2,…,n−?, or πi+1−πi≤m for all i=1,2,…,n−1. 相似文献
14.
A circulant C(n;S) with connection set S={a1,a2,…,am} is the graph with vertex set Zn, the cyclic group of order n, and edge set E={{i,j}:|i−j|∈S}. The chromatic number of connected circulants of degree at most four has been previously determined completely by Heuberger [C. Heuberger, On planarity and colorability of circulant graphs, Discrete Math. 268 (2003) 153-169]. In this paper, we determine completely the chromatic number of connected circulants C(n;a,b,n/2) of degree 5. The methods used are essentially extensions of Heuberger’s method but the formulae developed are much more complex. 相似文献
15.
S. Butler 《Journal of Mathematical Analysis and Applications》2005,307(2):465-479
q-Functions provide a method for constructing topological measures. We give necessary and sufficient conditions for a composition of a q-function and a topological measure to be a topological measure. Regular and extreme step q-functions are characterized by certain regions in Rn. Then extreme q-functions are used to study extreme topological measures. For example, we prove (under some assumptions on the underlying set) that given n, there are different types of extreme topological measures with values 0,1/n,…,1. In contrast, in the case of measures the only extreme points are {0,1}-valued, i.e., point masses. 相似文献
16.
Zhongli Wei 《Journal of Mathematical Analysis and Applications》2005,306(2):619-636
This paper investigates the existence of positive solutions for 2nth-order (n>1) singular sub-linear boundary value problems. A necessary and sufficient condition for the existence of C2n−2[0,1] as well as C2n−1[0,1] positive solutions is given by constructing lower and upper solutions and with the maximal theorem. Our nonlinearity f(t,x1,x2,…,xn) may be singular at xi=0, i=1,2,…,n, t=0 and/or t=1. 相似文献
17.
Let Ξ0=[−1,1], and define the segments Ξn recursively in the following manner: for every n=0,1,…, let Ξn+1=Ξn∩[an+1−1,an+1+1], where the point an+1 is chosen randomly on the segment Ξn with uniform distribution. For the radius ρn of Ξn, we prove that n(ρn−1/2) converges in distribution to an exponential law, and we show that the centre of the limiting unit interval has arcsine distribution. 相似文献
18.
Huy Vui Hà 《Journal of Pure and Applied Algebra》2009,213(11):2167-2176
Let f,gi,i=1,…,l,hj,j=1,…,m, be polynomials on Rn and S?{x∈Rn∣gi(x)=0,i=1,…,l,hj(x)≥0,j=1,…,m}. This paper proposes a method for finding the global infimum of the polynomial f on the semialgebraic set S via sum of squares relaxation over its truncated tangency variety, even in the case where the polynomial f does not attain its infimum on S. Under a constraint qualification condition, it is demonstrated that: (i) The infimum of f on S and on its truncated tangency variety coincide; and (ii) A sums of squares certificate for nonnegativity of f on its truncated tangency variety. These facts imply that we can find a natural sequence of semidefinite programs whose optimal values converge, monotonically increasing to the infimum of f on S. 相似文献
19.
Grzegorz Malewicz 《Discrete Applied Mathematics》2006,154(6):1028-1031
A latin square is a matrix of size n×n with entries from the set {1,…,n}, such that each row and each column is a permutation on {1,…,n}. We show how to construct a latin square such that for any two distinct rows, the prefixes of length h of the two rows share at most about h2/n elements. This upper bound is close to optimal when contrasted with a lower bound derived from the Second Johnson bound [6]. 相似文献
20.
We say that a matrix R∈Cn×n is k-involutary if its minimal polynomial is xk-1 for some k?2, so Rk-1=R-1 and the eigenvalues of R are 1,ζ,ζ2,…,ζk-1, where ζ=e2πi/k. Let α,μ∈{0,1,…,k-1}. If R∈Cm×m, A∈Cm×n, S∈Cn×n and R and S are k-involutory, we say that A is (R,S,μ)-symmetric if RAS-1=ζμA, and A is (R,S,α,μ)-symmetric if RAS-α=ζμA.Let L be the class of m×n(R,S,μ)-symmetric matrices or the class of m×n(R,S,α,μ)-symmetric matrices. Given X∈Cn×t and B∈Cm×t, we characterize the matrices A in L that minimize ‖AX-B‖ (Frobenius norm), and, given an arbitrary W∈Cm×n, we find the unique matrix A∈L that minimizes both ‖AX-B‖ and ‖A-W‖. We also obtain necessary and sufficient conditions for existence of A∈L such that AX=B, and, assuming that the conditions are satisfied, characterize the set of all such A. 相似文献