共查询到20条相似文献,搜索用时 31 毫秒
1.
Anna Lladó Jordi Moragas 《European Journal of Combinatorics》2012,33(4):427-434
A sequence m1≥m2≥?≥mk of k positive integers isn-realizable if there is a partition X1,X2,…,Xk of the integer interval [1,n] such that the sum of the elements in Xi is mi for each i=1,2,…,k. We consider the modular version of the problem and, by using the polynomial method by Alon (1999) [2], we prove that all sequences in Z/pZ of length k≤(p−1)/2 are realizable for any prime p≥3. The bound on k is best possible. An extension of this result is applied to give two results of p-realizable sequences in the integers. The first one is an extension, for n a prime, of the best known sufficient condition for n-realizability. The second one shows that, for n≥(4k)3, an n-feasible sequence of length k isn-realizable if and only if it does not contain forbidden subsequences of elements smaller than n, a natural obstruction forn-realizability. 相似文献
2.
Keqin Feng 《Discrete Applied Mathematics》2006,154(6):942-949
Let f(k1,…,km) be the minimal value of size of all possible unextendible product bases in the tensor product space . We have trivial lower bounds and upper bound k1?km. Alon and Lovász determined all cases such that f(k1,…,km)=n(k1,…,km). In this paper we determine all cases such that f(k1,…,km)=k1?km by presenting a sharper upper bound. We also determine several cases such that f(k1,…,km)=n(k1,…,km)+1 by using a result on 1-factorization of complete graphs. 相似文献
3.
Alphonse Baartmans 《Discrete Mathematics》2008,308(13):2885-2895
Let A denote a set of order m and let X be a subset of Ak+1. Then X will be called a blocker (of Ak+1) if for any element say (a1,a2,…,ak,ak+1) of Ak+1, there is some element (x1,x2,…,xk,xk+1) of X such that xi equals ai for at least two i. The smallest size of a blocker set X will be denoted by α(m,k)and the corresponding blocker set will be called a minimal blocker. Honsberger (who credits Schellenberg for the result) essentially proved that α(2n,2) equals 2n2 for all n. Using orthogonal arrays, we obtain precise numbers α(m,k) (and lower bounds in other cases) for a large number of values of both k and m. The case k=2 that is three coordinate places (and small m) corresponds to the usual combination lock. Supposing that we have a defective combination lock with k+1 coordinate places that would open if any two coordinates are correct, the numbers α(m,k) obtained here give the smallest number of attempts that will have to be made to ensure that the lock can be opened. It is quite obvious that a trivial upper bound for α(m,k) is m2 since allowing the first two coordinates to take all the possible values in A will certainly obtain a blocker set. The results in this paper essentially prove that α(m,k) is no more than about m2/k in many cases and that the upper bound cannot be improved. The paper also obtains precise values of α(m,k) whenever suitable orthogonal arrays of strength two (that is, mutually orthogonal Latin squares) exist. 相似文献
4.
Hiro Ito 《Discrete Applied Mathematics》2006,154(16):2330-2334
Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x0,x1,…,xn-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex xi and define the area AP(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size cH(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:
- •
- AP(H)?AP(H′) for all convex n-gons P.
- •
- cH(i,j,k)?cH′(i,j,k) for all convex three-cuts C(i,j,k).
5.
Mordecai J. Golin 《Discrete Mathematics》2010,310(4):792-803
Let T(G) be the number of spanning trees in graph G. In this note, we explore the asymptotics of T(G) when G is a circulant graph with given jumps.The circulant graph is the 2k-regular graph with n vertices labeled 0,1,2,…,n−1, where node i has the 2k neighbors i±s1,i±s2,…,i±sk where all the operations are . We give a closed formula for the asymptotic limit as a function of s1,s2,…,sk. We then extend this by permitting some of the jumps to be linear functions of n, i.e., letting si, di and ei be arbitrary integers, and examining
6.
Bakir Farhi 《Journal of Number Theory》2007,125(2):393-411
We present here a method which allows to derive a nontrivial lower bounds for the least common multiple of some finite sequences of integers. We obtain efficient lower bounds (which in a way are optimal) for the arithmetic progressions and lower bounds less efficient (but nontrivial) for quadratic sequences whose general term has the form un=an(n+t)+b with (a,t,b)∈Z3, a?5, t?0, gcd(a,b)=1. From this, we deduce for instance the lower bound: lcm{12+1,22+1,…,n2+1}?0,32n(1,442) (for all n?1). In the last part of this article, we study the integer lcm(n,n+1,…,n+k) (k∈N, n∈N∗). We show that it has a divisor dn,k simple in its dependence on n and k, and a multiple mn,k also simple in its dependence on n. In addition, we prove that both equalities: lcm(n,n+1,…,n+k)=dn,k and lcm(n,n+1,…,n+k)=mn,k hold for an infinitely many pairs (n,k). 相似文献
7.
Disjoint triangles and quadrilaterals in a graph 总被引:1,自引:0,他引:1
Jin Yan 《Discrete Mathematics》2008,308(17):3930-3937
Let G be a simple graph of order n and s and k be two positive integers. Brandt et al. obtained the following result: If s?k, n?3s+4(k-s) and σ2(G)?n+s, then G contains k disjoint cycles C1,…,Ck satisfying |Ci|=3 for 1?i?s and |Ci|?4 for s<i?k. In the above result, the length of Ci is not specified for s<i?k. We get a result specifying the length of Ci for each s<i?k if n?3s+4(k-s)+3. 相似文献
8.
We consider the possibility of the analytic continuation of the Dirichlet series SP;Z(s) associated with a polynomial P(x) and auxiliary series Z(s). In fact, we derive a certain criterion for the analytic continuation for some class of polynomials and give examples such that SP;Z(s) cannot be continued meromorphically to the whole plane C. We also study the asymptotic behaviors of the sum MP(x)=∑P(n1,…,nk)?xΛ(n1)?Λ(nk) considered first by M. Peter. Generalizations of this sum are also considered. 相似文献
9.
This paper deals with non-simultaneous and simultaneous blow-up for radially symmetric solution (u1,u2,…,un) to heat equations coupled via nonlinear boundary (i=1,2,…,n). It is proved that there exist suitable initial data such that ui(i∈{1,2,…,n}) blows up alone if and only if qi+1<pi. All of the classifications on the existence of only two components blowing up simultaneously are obtained. We find that different positions (different values of k, i, n) of ui−k and ui leads to quite different blow-up rates. It is interesting that different initial data lead to different blow-up phenomena even with the same requirements on exponent parameters. We also propose that ui−k,ui−k+1,…,ui blow up simultaneously while the other ones remain bounded in different exponent regions. Moreover, the blow-up rates and blow-up sets are obtained. 相似文献
10.
Ingo Wegener 《Discrete Mathematics》1979,28(2):219-222
A system A1,…,Am of subsets of X?{1,…,n} is called a separating system if for any two distinct elements of X there is a set Ai (1?i?m) that contains exactly one of the two elements. We investigate separating systems where each set Ai has at most k elements and we are looking for minimal separating systems, that means separating systems with the least number of subsets. We call this least number m(n,k). Katona has proved good bounds on m(n,k) but his proof is very complicated. We give a shorter and easier proof. In doing so we slightly improve the upper bound of Katona. 相似文献
11.
Sang-Gu Lee 《Linear algebra and its applications》2011,435(9):2097-2109
We investigate simultaneous solutions of the matrix Sylvester equations AiX-XBi=Ci,i=1,2,…,k, where {A1,…,Ak} and {B1,…,Bk} are k-tuples of commuting matrices of order m×m and p×p, respectively. We show that the matrix Sylvester equations have a unique solution X for every compatible k-tuple of m×p matrices {C1,…,Ck} if and only if the joint spectra σ(A1,…,Ak) and σ(B1,…,Bk) are disjoint. We discuss the connection between the simultaneous solutions of Sylvester equations and related questions about idempotent matrices separating disjoint subsets of the joint spectrum, spectral mapping for the differences of commuting k-tuples, and a characterization of the joint spectrum via simultaneous solutions of systems of linear equations. 相似文献
12.
《Quaestiones Mathematicae》2013,36(4):383-398
Abstract A set B of vertices of a graph G = (V,E) is a k-maximal independent set (kMIS) if B is independent but for all ?-subsets X of B, where ? ? k—1, and all (? + 1)-subsets Y of V—B, the set (B—X) u Y is dependent. A set S of vertices of C is a k-maximal clique (kMc) of G iff S is a kMIS of [Gbar]. Let βk, (G) (wk(G) respectively) denote the smallest cardinality of a kMIS (kMC) of G—obviously βk(G) = wk([Gbar]). For the sequence m1 ? m2 ?…? mn = r of positive integers, necessary and sufficient conditions are found for a graph G to exist such that wk(G) = mk for k = 1,2,…,n and w(G) = r (equivalently, βk(G) = mk for k = 1,2,…,n and β(G) = r). Define sk(?,m) to be the largest integer such that for every graph G with at most sk(?,m) vertices, βk(G) ? ? or wk(G) ? m. Exact values for sk(?,m) if k ≥ 2 and upper and lower bounds for s1(?,m) are de termined. 相似文献
13.
Jun Tarui 《Discrete Mathematics》2008,308(8):1350-1354
A family P={π1,…,πq} of permutations of [n]={1,…,n} is completely k-scrambling [Spencer, Acta Math Hungar 72; Füredi, Random Struct Algor 96] if for any distinct k points x1,…,xk∈[n], permutations πi's in P produce all k! possible orders on πi(x1),…,πi(xk). Let N*(n,k) be the minimum size of such a family. This paper focuses on the case k=3. By a simple explicit construction, we show the following upper bound, which we express together with the lower bound due to Füredi for comparison.
14.
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. 相似文献
15.
Consider the multiplicities ep1(n),ep2(n),…,epk(n) in which the primes p1,p2,…,pk appear in the factorization of n!. We show that these multiplicities are jointly uniformly distributed modulo (m1,m2,…,mk) for any fixed integers m1,m2,…,mk, thus improving a result of Luca and St?nic? [F. Luca, P. St?nic?, On the prime power factorization of n!, J. Number Theory 102 (2003) 298-305]. To prove the theorem, we obtain a result regarding the joint distribution of several completely q-additive functions, which seems to be of independent interest. 相似文献
16.
Dalibor Froncek 《Discrete Mathematics》2009,309(2):501-389
We completely solve certain case of a “two delegation negotiation” version of the Oberwolfach problem, which can be stated as follows. Let H(k,3) be a bipartite graph with bipartition X={x1,x2,…,xk},Y={y1,y2,…,yk} and edges x1y1,x1y2,xkyk−1,xkyk, and xiyi−1,xiyi,xiyi+1 for i=2,3,…,k−1. We completely characterize all complete bipartite graphs Kn,n that can be factorized into factors isomorphic to G=mH(k,3), where k is odd and mH(k,3) is the graph consisting of m disjoint copies of H(k,3). 相似文献
17.
R. Tijdeman 《Indagationes Mathematicae》2003,14(1):135-147
Let w = w1 … wn be a word of maximal length n, and with a maximal number of distinct letters for this length, such that w has periods p1, …, pn but not period gcd(p1,…,pr). We provide a fast algorithm to compute n and w. We show that w is uniquely determined apart from isomorphism and that it is a palindrome. Furthermore we give lower and upper bounds for n as explicit functions of p1, …pr. For r = 2 the exact value of n is due to Fine and Wilf. In case the number of distinct letters in the extremal word equals r a formula for n had been given by Castelli, Mignosi and Restivo in case r = 3 and by Justin if r > 3. 相似文献
18.
Hwa Kyung Kim 《Linear algebra and its applications》2011,435(9):2166-2174
For a positive integer m where 1?m?n, the m-competition index (generalized competition index) of a primitive digraph is the smallest positive integer k such that for every pair of vertices x and y, there exist m distinct vertices v1,v2,…,vm such that there are directed walks of length k from x to vi and from y to vi for 1?i?m. The m-competition index is a generalization of the scrambling index and the exponent of a primitive digraph. In this study, we determine an upper bound on the m-competition index of a primitive digraph using Boolean rank and give examples of primitive Boolean matrices that attain the bound. 相似文献
19.
Øystein J. Rødseth 《Discrete Mathematics》2006,306(16):2005-2009
Recently, Sloane suggested the following problem: We are given n boxes, labeled 1,2,…,n. For i=1,…,n, box i weighs (m-1)i grams (where m?2 is a fixed integer) and box i can support a total weight of i grams. What is the number of different ways to build a single stack of boxes in which no box will be squashed by the weight of the boxes above it? Prior to this generalized problem, Sloane and Sellers solved the case m=2. More recently, Andrews and Sellers solved the case m?3. In this note we give new and simple proofs of the results of Sloane and Sellers and of Andrews and Sellers, using a known connection with m-ary partitions. 相似文献
20.
Gustav Nordh 《Discrete Mathematics》2008,308(9):1653-1664
A Skolem sequence is a sequence s1,s2,…,s2n (where si∈A={1,…,n}), each si occurs exactly twice in the sequence and the two occurrences are exactly si positions apart. A set A that can be used to construct Skolem sequences is called a Skolem set. The problem of deciding which sets of the form A={1,…,n} are Skolem sets was solved by Thoralf Skolem in the late 1950s. We study the natural generalization where A is allowed to be any set of n positive integers. We give necessary conditions for the existence of Skolem sets of this generalized form. We conjecture these necessary conditions to be sufficient, and give computational evidence in favor of our conjecture. We investigate special cases of the conjecture and prove that the conjecture holds for some of them. We also study enumerative questions and show that this problem has strong connections with problems related to permutation displacements. 相似文献