共查询到20条相似文献,搜索用时 15 毫秒
1.
Albert L Wells 《Journal of Combinatorial Theory, Series A》1977,22(3):313-321
In this paper a certain condition on partial latin squares is shown to be sufficient to guarantee that the partial square can be completed, namely, that it have fewer than n entries, and that at most of these lie off some line, where n is the order of the square. This is applied to establish that the Evans conjecture is true for n ? 8; i.e., that given a partial latin square of order n with fewer than n entries, n ? 8, the square can be completed. Finally, the results are viewed in a conjugate way to establish different conditions sufficient for the completion of a partial latin square. 相似文献
2.
H.S Witsenhausen 《Journal of Combinatorial Theory, Series A》1974,17(3):387-390
It is established that the maximum number of points required to puncture 3n sets of probability is 2n, as had been conjectured. In fact, for 1 ≤ m ≤ n, a family of m sets of probability can be punctured using no more than points. The more general statement that (k + 1)n sets of probability require at most 2n points for puncturing is shown to be false already for k = 3. 相似文献
3.
For a permutation σ of the integers from 1 to n, let ?(σ) be the smallest number of prefix reversals that will transform σ to the identity permutation, and let ?(n) be the largest such ?(σ) for all σ in (the symmetric group) Sn. We show that , and that for n a multiple of 16. If, furthermore, each integer is required to participate in an even number of reversed prefixes, the corresponding function g(n) is shown to obey . 相似文献
4.
Arnošt J.J Heidrich 《Journal of Number Theory》1977,9(4):413-419
Let p be an odd prime and n an integer relatively prime to p. In this work three criteria which give the value of the Legendre symbol () are developed. The first uses two adjacent rows of Pascal's triangle which depend only on p to express () explicitly in terms of the numerically least residues (mod p) of the numbers n, 2n, …, [ or of the numbers . The second, analogous to a theorem of Zolotareff and valid only if p ≡ 1 (mod 4), expresses () in terms of the parity of the permutation of the set {} defined by the absolute values of the numerically least residues of . The third is a result dual to Gauss' lemma which can be derived directly without Euler's criterion. The applications of the dual include a proof of Gauss' lemma free of Euler's criterion and a proof of the Quadratic Reciprocity Law. 相似文献
5.
Let M be the n-dimensional Minkowski space, n ? 3. One consequence of [1] is that the null space of the equation on differential k-forms Φ in M is conformally covariant. The same is true of a nonlinear equation obtained by adding to the above a term homogeneous of degree . This generalizes the well-known conformal covariance properties of the wave equation and the equations when k = 0, and of Maxwell's equations on a vector potential when (and n is even). We define a natural (conformally invariant) symplectic structure for the new equations, and use it to calculate the conserved quantities corresponding to the standard conformal group generators. 相似文献
6.
A weighted lattice path from (1, 1) to (n, m) is a path consisting of unit vertical, horizontal, and diagonal steps of weight w. Let f(0), f(1), f(2), … be a nondecreasing sequence of positive integers; the path connecting the points of the set will be called the roof determined by f. We determine the number of weighted lattice paths from (1, 1) to (n + 1, f(n)) which do not cross the roof determined by f. We also determine the polynomials that must be placed in each cell below the roof such that if a 1 is placed in each cell whose lower left-hand corner is a point of the roof, every k × k square subarray comprised of adjacent rows and columns and containing at least one 1 will have determinant . 相似文献
7.
Daniel A Marcus 《Journal of Combinatorial Theory, Series B》1981,30(1):21-31
It is shown that every k-edge-connected digraph with m edges and n vertices contains a spanning connected subgraph having at most edges. When k = 2 the bound is improved to , which implies that a 2-edge-connected digraph is connected by less than 70% of its edges. Examples are given which require almost two-thirds of the edges to connect all vertices. 相似文献
8.
John Konvalina 《Journal of Combinatorial Theory, Series A》1981,31(2):101-107
Let f(n, k) denote the number of ways of selecting k objects from n objects arrayed in a line with no two selected having unit separation (i.e., having exactly one object between them). Then, if (where ). If n < 2(k ? 1), then f(n, k) = 0. In addition, f(n, k) satisfies the recurrence relation f(n, k) = f(n ? 1, k) + f(n ? 3, k ? 1) + f(n ? 4, k ? 2). If the objects are arrayed in a circle, and the corresponding number is denoted by g(n, k), then for n > 3, g(n, k) = f(n ? 2, k) + 2f(n ? 5, k ? 1) + 3f(n ? 6, k ? 2). In particular, if n ? 2k + 1 then . 相似文献
9.
George B Purdy 《Journal of Combinatorial Theory, Series A》1974,17(1):131-133
There are at most 2n spheres tangent to all n + 1 faces of an n-simplex. It has been shown that the minimum number of such spheres is if n is odd and if n is even. The object of this note is to show that this result is a consequence of a theorem in graph theory. 相似文献
10.
M. Lewin and Y. Vitek conjecture [7] that every integer is an exponent of some n×n primitive matrix. In this paper, we prove three results related to Lewin and Vitek's conjecture: (1) Every integer is an exponent of some n×n primitive matrix. (2) The conjecture is true when n is sufficiently large. (3) We give a counterexample to show that the conjecture is not true in the case when n=11. 相似文献
11.
Cai Mao-cheng 《Discrete Mathematics》1982,41(3):229-234
Let G be a minimally k-connected graph of order n and size e(G).Mader [4] proved that (i) ; (ii) e(G)?k(n?k) if n?3k?2, and the complete bipartite graph Kk,n?k is the only minimally k-connected graph of order; n and size k(n?k) when k?2 and n?3k?1.The purpose of the present paper is to determine all minimally k-connected graphs of low order and maximal size. For each n such that k+1?n?3k?2 we prove and characterize all minimally k-connected graphs of order n and size . 相似文献
12.
J. Shearer 《Discrete Mathematics》1979,25(2):175-178
If the lines of the complete graph Kn are colored so that no point is on more than lines of the same color or so that each point lies on more than lines of different colors, then Kn contains a cycle of length n with adjacent lines having different colors. 相似文献
13.
Let A be a real symmetric n × n matrix of rank k, and suppose that A = BB′ for some real n × m matrix B with nonnegative entries (for some m). (Such an A is called completely positive.) It is shown that such a B exists with , where 2N is the maximal number of (off-diagonal) entries which equal zero in a nonsingular principal submatrix of A. An example is given where the least m which works is (k odd), (k even). 相似文献
14.
Frances Chevarley Edmonds 《Discrete Mathematics》1977,18(1):1-22
Enumeration of arrays whose row and column sums are specified have been studied by a number of people. It has been determined that the function that enumerates square arrays of dimension n, whose rows and columns sum to a fixed non-negative integer r, is a polynomial in r of degree (n ? 1)2.In this paper we consider rectangular arrays whose rows sum to a fixed non-negative integer r and whose columns sum to a fixed non-negative integer s, determined by ns = mr. in particular, we show that the functions which enumerate 2 × n and 3 × n arrays with fixed row sums and , where the symbol (a, b) denotes the greatest common divisor of a and b, and fixed column sums, are polynomials in r of degrees (n ? 1) and 2(n ? 1) respectively. We have found simple formulas to evaluate these polynomials for negative values, - r, and we show that for certain small negative integers our polynomials will always be zero. We also considered the generating functions of these polynomials and show that they are rational functions of degrees less than zero, whose denominators are of the forms (1 ? y)n and (1 ? y)2n?1 respectively and whose numerators are polynomials in y whose coefficients satisfy certain properties. In the last section we list the actual polynomials and generating functions in the 2 × n and 3 × n cases for small specific values of n. 相似文献
15.
D.T Todorov 《Journal of Combinatorial Theory, Series A》1985,39(1):83-101
Let n ? k ? t be positive integers, and let Ω be a set of n elements. Let C(n, k, t) denote the number of k-tuples of Ω in a minimal system of k-tuples such that every t-tuple is contained in at least one k-tuple of the system. C(n, k, t) has been determined in all cases for which [W. H. Mills, Ars Combinatoria8 (1979), 199–315]. C(n, k, t) is determined in the case . 相似文献
16.
J.-C. Panayiotopoulos 《European Journal of Operational Research》1982,9(1):77-82
This paper deals with probabilistic analysis of optimal solutions of the asymmetric traveling salesman problem. The exact distribution for the number of required next-best solutions of the assignment problem with random data in order to find an optimal tour is given. For every n-city asymmetric problem, there exists an algorithm such that (i) with probability 1 ? s, s?(0,1) the algorithm produces an optimal tour, (ii) it runs in time , and (iii) it requires less than w((w + n ? 1) computational steps, where w = log(s)/log(1 ? En); En ?(0,1) is given by a simple mathematical formula. Additionally, the polynomial of (iii) gives the exact (deterministic) execution time to find w =1 ,2…. next-best solutions of the assignment problem. 相似文献
17.
Explicit and asymptotic solutions are presented to the recurrence M(1) = g(1), M(n + 1) = g(n + 1) + min1 ? t ? n(αM(t) + βM(n + 1 ? t)) for the cases (1) α + β < 1, is rational, and g(n) = δnI. (2) α + β > 1, min(α, β) > 1, is rational, and (a) g(n) = δn1, (b) g(n) = 1. The general form of this recurrence was studied extensively by Fredman and Knuth [J. Math. Anal. Appl.48 (1974), 534–559], who showed, without actually solving the recurrence, that in the above cases , where γ is defined by α?γ + β?γ = 1, and that does not exist. Using similar techniques, the recurrence M(1) = g(1), M(n + 1) = g(n + 1) + max1 ? t ? n(αM(t) + βM(n + 1 ? t)) is also investigated for the special case α = β < 1 and g(n) = 1 if n is odd = 0 if n is even. 相似文献
18.
19.
Sagun Chanillo 《Journal of Functional Analysis》1984,55(1):18-24
It is shown that the multiplier for the ball is restricted weak type on radial functions in Lp(n) when . Interpolation then yields a theorem of Herz. 相似文献
20.
Denote by M(n) the smallest positive integer such that for every n-element monoid M there is a graph G with at most M(n) vertices such that End(G) is isomorphic to M. It is proved that . Moreover, for almost all n-element monoids M there is a graph G with at most 12 · n · log2n + n vertices such that End(G) is isomorphic to M. 相似文献