Partitions of large multipartites with congruence conditions. II

For 1 ≦ l ≦ j, let $\text{a}$_l = ?_h=1^q(l){a_lh + Mv: v = 0, 1, 2,…}, where j, M, q(l) and the a_lh are positive integers such that j > 1, a_l1 < … < a_lq(2) ≦ M, and let $\text{a}$_l^′ = $\text{a}$_l ∪ {0}. Let p(n : $\text{B}$) be the number of partitions of n = (n₁,…,n_j) where, for 1 ≦ l ≦ j, the lth component of each part belongs to $\text{B}$_l and let p¹(n : $\text{B}$) be the number of partitions of n into different parts where again the lth component of each part belongs to $\text{B}$_l. Asymptotic formulas are obtained for p(n : $\text{a}$), p¹(n : $\text{a}$) where all but one n_l tend to infinity much more rapidly than that n_l, and asymptotic formulas are also obtained for p(n : $\text{a}$′), p¹(n ; $\text{a}$′), where one n_l tends to infinity much more rapidly than every other n_l. These formulas contrast with those of a recent paper (Robertson and Spencer, Trans. Amer. Math. Soc., to appear) in which all the n_l tend to infinity at approximately the same rate.     

The Independence Number for De Bruijn networks and Kautz networks

Let D be a directed graph; the (l,ω)-Independence Number of graph D, denoted by α_l,ω(D), is an important performance parameter for interconnection networks. De Bruijn networks and Kautz networks, denoted by B(d,n) and K(d,n) respectively, are versatile and efficient topological structures of interconnection networks. For l=1,2,…,n, this paper shows that α_l,d−1(B(d,n))=dⁿ,α_l,d−1(K(d,n))=α_l,d(K(d,n))=dⁿ+dⁿ⁻¹ if d≥3 and n≤d−2. In particular, the paper shows the exact value of the Independence Number for B(d,1) and B(d,2) for any d. For the generalized situation, the paper obtains a lower bound α_l,d−1(B(d,n))≥d² if n≥3 and d≥5.     

A note on short cycles in a hypercube

How many edges can a quadrilateral-free subgraph of a hypercube have? This question was raised by Paul Erd?s about 27 years ago. His conjecture that such a subgraph asymptotically has at most half the edges of a hypercube is still unresolved. Let f(n,C_l) be the largest number of edges in a subgraph of a hypercube Q_n containing no cycle of length l. It is known that f(n,C_l)=o(|E(Q_n)|), when l=4k, k?2 and that . It is an open question to determine f(n,C_l) for l=4k+2, k?2. Here, we give a general upper bound for f(n,C_l) when l=4k+2 and provide a coloring of E(Q_n) by four colors containing no induced monochromatic C₁₀.     

THE EXTREME POINTS OF SEVERAL CLASSES OF ANALYTIC FUNCTIONS

1Intr0ducti0nLetAden0tethesetofallfunctionsanalyticinA={z:Izl<1}.LetB={W:WEAandIW(z)l51}.Aisalocallyconvexlineaztop0l0gicalspacewithrespecttothetopologyofuniformconvergenceon`c0mpact8ubsetsofA-LetTh(c1,'tc.-1)={p(z):p(z)EA,Rop(z)>0,p(z)=1 clz czzz ' c.-lz"-l 4z" ',wherecl,',cn-1areforedcomplexconstants}.LetTh,.(b,,-..,b,-,)={p(z):P(z)'EAwithReP(z)>Oandp(z)=1 blz ' b.-lz"-l 4z" '-,wherebl,-'-jbu-1areffeedrealconstantsanddkarerealnumbersf0rk=n,n 1,'--}-LetTu(l1,'i'tI.-1)={…     

On a class of sine-type functions

We study an infinite product F _Λ(z) with zeros λ _n = n + l(|n|), n ? ?, where l(t) is a concave function and l(t) = o(t). We obtain a test for F _Λ(z) to belong to the class of sine-type functions. For the particular case in which l(t) is a regularly varying function, we obtain sharp asymptotic estimates for F _Λ(z).     

On Subsets with Cardinalities of Intersections Divisible by a Fixed Integer

If m(n, l) denotes the maximum number of subsets of an n-element set such that the intersection of any two of them has cardinality divisible by l, then a trivial construction shows that

$m(n,l)\ge 2^{[n/l]}$

For l= 2, this was known to be essentially best possible. For l ? 3, we show by construction that m(n, l)2^?[n/l] grows exponentially in n, and we provide upper bounds.     

Covering the alternating groups by products of cycle classes

Given integers k,l?2, where either l is odd or k is even, we denote by n=n(k,l) the largest integer such that each element of An is a product of k cycles of length l. For an odd l, k is the diameter of the undirected Cayley graph Cay(An,Cl), where Cl is the set of all l-cycles in An. We prove that if k?2 and l?9 is odd and divisible by 3, then . This extends earlier results by Bertram [E. Bertram, Even permutations as a product of two conjugate cycles, J. Combin. Theory 12 (1972) 368-380] and Bertram and Herzog [E. Bertram, M. Herzog, Powers of cycle-classes in symmetric groups, J. Combin. Theory Ser. A 94 (2001) 87-99].     

Binary Segmentation for Multivariate Polynomials

This paper develops a fast method of binary segmentation for multivariate integer polynomials and applies it to polynomial multiplication, pseudodivision, resultant and gcd calculations. In the univariate case, binary segmentation yields the fastest known method for multiplication of integer polynomials, even slightly faster than fast Fourier transform methods (however, the underlying fast integer multiplication method is based on fast Fourier transforms). Fischer and Paterson ("SIAM-AMS Proceedings, 1974," pp. 113-125) seem to be the first authors who suggest binary segmentation for polynomials with coefficients in {0, 1}. Schönhage (J. Complexity1 (1985), 118-137), as well as Bini and Pan (J. Complexity2 (1986), 179-203) have applied the binary segmentation to univariate polynomial division and gcd calculation. In the multivariate case, well- known methods are the iterated application of univariate binary segmentation and Kronecker′s map. Our method of binary segmentation to the contrary is based on a one-step algebra homomorphism mapping multivariate polynomials directly into integers. More precisely, the variables x₁, . . . , x_n of a multivariate polynomial are substituted by integers 2^ν₁, . . . , 2^ν_n, where ν₁ < · · · < ν_n are chosen as small as possible. If n is the number of variables, d bounds the total degrees, and l bounds the bit lengths of the input, we achieve the bit complexities O(ψ((2d)ⁿ (n log d + l))) for multivariate multiplication, O(d ψ(d²ⁿ(n log d + l))) for multivariate pseudo-division (provided n = O(d log d)), and O(d ψ((2d²)ⁿ (n log d + l))) for multivariate subresultant chain calculation. Here ψ(l) = l log l log log l denotes the complexity of integer multiplication.     

Typical tensorial rank

Upper bounds on the typical rank $\text{R}$(n, m, l) of tensors ( = maximal border rank = rank of almost all tensors) of a given shape (n, m, l) are presented. These improve previous results by A tkinson and Lloyd. For cubic shape tensors the typical rank is determined exactly: $\text{R}$(n, n, n) = ? _n³/(3n ? 2) ? (n ≠ 3)     

Probabilistic computation of integer polynomial GCDs

We describe a probabilistic algorithm for the computation of the gcd of two univariate integer polynomials of degrees ≤ n with their l¹-norms being bounded by 2^h and estimate its expected running time by a worst-case bound of O(n(n + h)^{1 + o(1)}) bit operations.     

Sequences of Hopf-Swan subgroups

Let l be an odd prime which satisfies Vandiver's conjecture, let n?1 be an integer, and let K=Q(ζn) where ζn is a primitive lnth root of unity. Let Cl denote the cyclic group of order l. For each j, j=1,…,ln−1, there exists an inclusion of Larson orders in KCl: Λj−1⊆Λj and a corresponding surjection of Hopf-Swan subgroups T(Λj−1)→T(Λj). For the cases n=1,2 we investigate the structure of various terms in the sequence of Hopf-Swan subgroups including the Swan subgroup T(Λ₀).     

The weight distribution of irreducible cyclic codes with block lengths n1((q1−1)N)

We study the weight distribution of irreducible cyclic (n, k) codeswith block lengths n = n₁((q¹ ? 1)/N), where N|q ? 1, gcd(n₁,N) = 1, and gcd(l,N) = 1. We present the weight enumerator polynomial, A(z), when k = n₁l, k = (n₁ ? 1)l, and k = 2l. We also show how to find A(z) in general by studying the generator matrix of an (n₁, m) linear code, $\text{V}{}^1{}_{\mathrm{d}}$ over GF(q^d) where d = gcd (ord_n1(q), l). Specifically we study A(z) when $\text{V}{}^1{}_{\mathrm{d}}$ is a maximum distance separable code, a maximal shiftregister code, and a semiprimitive code. We tabulate some numbers A_μ which completely determine the weight distributionof any irreducible cyclic (n₁(2¹ ? 1), k) code over GF(2) for all n₁ ? 17.     

A note on the probabilistic approach to Turán's problem

The Turán number T(n, l, k) is the smallest possible number of edges in a k-graph on n vertices such that every l-set of vertices contains an edge. Given a k-graph H = (V(H), E(H)), we let X_s(S) equal the number of edges contained in S, for any s-set S?V(H). Turán's problem is equivalent to estimating the expectation E(X_l), given that min(X_l) ≥ 1. The following lower bound on the variance of X_s is proved:

$\text{Var(X}{}_{\mathrm{s}}\text{)?mm}\text{n?2k}\text{s?k}\text{n}\text{s}{}^{\mathrm{?1}}\text{n}\text{k}{}^1$

, where m = |E(H)| and $\text{m}\text{= (}{}_{\mathrm{k}}{}^{\mathrm{n}}\text{) ? m}$. This implies the following: putting t(k, l) = lim_n→∞T(n, l, k)(_kⁿ)^?1 then t(k, l) ≥ T(s, l, k)((_k^s) ? 1)^?1, whenever s ≥ l > k ≥ 2. A connection of these results with the existence of certain t-designs is mentioned.     

More on the generalized Macaulay theorem

Let k₁ ? k₂ ? … ? k_n be given positive integers and let F denote the set of vectors (l₁, …, l_n) with integer components satisfying 0 ? l_i ? k_i, i = 1, 2, …, n. If H is a subset of F, let (l)H denote the subset of H consisting of those vectors with component sum l, and let C((l)H) denote the smallest [(l)H] elements of (l)F. The generalized Macaulay theorem due to the author and B. Lindström [3] shows that |Gamma;((C)(l)(H)|, ? |Γ(C((l)H))|, where Γ((l)H) is the setof vectors in F obtainable by subtracting l from a single component of a vector in (l)H. A method is given for computing [Γ(C((l)H)] in this paper. It is analogous to the method for computing |Γ(C(l)H))| in the k₁ = … = k_n = 1 case which has been given independently by Katona [4] and Kruskal [5].     

Sufficient conditions that the minimum and maximum of partial differential operators should coincide and that their spectra should be discrete

An expression of the form $$l(u) = ( - 1)^m \sum\nolimits_{j = 1}^m {D_j^{2m} } u + [q(x)] + ir(x)]u$$ is considered. Sufficient conditions are found such that the minimum operator, formally conjugate tol(u), generated by the expression and the maximum operator generated by the expressionl(u) in ?₂ (E_n) should coincide. It is proved that if q(x)→∞ or q(x)+ r(x)→∞, ¦x¦→∞, then the operator generated byl(u) in ?₂ (E_n) has a discrete spectrum.     

On the length of optimal TSP circuits in sets of bounded diameter

Let V be a set of n points in R^k. Let d(V) denote the diameter of V, and l(V) denote the length of the shortest circuit which passes through all the points of V. (Such a circuit is an “optimal TSP circuit”.) l^k(n) are the extremal values of l(V) defined by l^k(n)=max{l(V)|V∈V_n^k}, where V_n^k={V|V?R^k,|V|=n, d(V)=1}. A set V∈V_n^k is “longest” if l(V)=l^k(n). In this paper, first some geometrical properties of longest sets in R² are studied which are used to obtain l²(n) for small n′s, and then asymptotic bounds on l^k(n) are derived. Let δ(V) denote the minimal distance between a pair of points in V, and let: δ^k(n)=max{δ(V)|V∈V_n^k}. It is easily observed that $\text{δ}{}^{\mathrm{k}}\text{(n)=O(n}{}^{\mathrm{<mtext>?1</mtext><mtext>k</mtext>}}\text{)}$. Hence, $\text{c}{}_{\mathrm{k}}\text{=}\text{lim sup}{}_{\mathrm{n\to \infty }}\text{δ}{}^{\mathrm{k}}\text{(n)n}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}$ exists. It is shown that for all $\text{n, c}{}_{\mathrm{k}}\text{n}{}^{\mathrm{<mtext>?1</mtext><mtext>k</mtext>}}\text{≤δ}{}^{\mathrm{k}}\text{(n)}$, and hence, for all $\text{n, l}{}^{\mathrm{k}}\text{(n)≥ c}{}_{\mathrm{k}}\text{n}{}^{\mathrm{<mtext>1?1</mtext><mtext>k</mtext>}}$. For k=2, this implies that $\text{l}{}^2\text{(n)≥(}\text{π}{}^2\text{12}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>4</mtext>}}\text{n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$, which generalizes an observation of Fejes-Toth that $\text{lim}{}_{\mathrm{n\to \infty }}\text{l}{}^2\text{(n)n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{≥(}\text{π}{}^2\text{12}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>4</mtext>}}$. It is also shown that $\text{l}{}^{\mathrm{k}}\text{(n) ≤ [}\text{(3?√3)k}\text{(k?1)}\text{]nδ}{}^{\mathrm{k}}\text{(n) + o(n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{) ≤ [}\text{(3?√3)k}\text{(k?1)}\text{]n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{+ o(n}{}^{\mathrm{<mtext>1?</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{)}$. The above upper bound is used to improve related results on longest sets in k-dimensional unit cubes obtained by Few (Mathematika2 (1955), 141–144) for almost all k′s. For k=2, Few's technique is used to show that $\text{l}{}^2\text{(n)≤(}\text{πn}\text{2}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{+ O(1)}$.     

Intersection problems and integral equivalence

Let A and B be matrices over a principal ideal domain, Π. Necessary conditions, involving the invariant factors of A and B, are given for B to be a submatrix of A or a principal submatrix of A.If a given nonnegative integral matrix, B, is the intersection matrix of a pair of families of subsets of an n-set, and n is the smallest integer for which this is true, we say that the content of B is n. In that event, B is a submatrix of K(n), the intersection matrix of all subsets of an n-set. More refined results are obtained in certain cases by considering S(n, k, l), the intersection matrix of the k-subsets of an n-set versus its l-subsets. The invariant factors of K(n) and S(n, k, l) are calculated and it is shown how this information may be used to get lower bounds for the content of B. In the more widely studied symmetric version of the content problem, B must be a principal submatrix of K(n) or, possibly, S(n, k) = S(n, k, k). In this case, the invariant factors of K(n) ? xI or S(n, k) ? xI also provide relevant information.     

Dense edge-magic graphs and thin additive bases

A graph G of order n and size m is edge-magic if there is a bijection l:V(G)∪E(G)→[n+m] such that all sums l(a)+l(b)+l(ab), ab∈E(G), are the same. We present new lower and upper bounds on M(n), the maximum size of an edge-magic graph of order n, being the first to show an upper bound of the form . Concrete estimates for ε can be obtained by knowing s(k,n), the maximum number of distinct pairwise sums that a k-subset of [n] can have.So, we also study s(k,n), motivated by the above connections to edge-magic graphs and by the fact that a few known functions from additive number theory can be expressed via s(k,n). For example, our estimate

     

Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

An exclusive-OR sum of pseudoproducts (ESPP) is a modufo-2 sum of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this sum; the length of a Boolean function in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L ^ESPP(n) on the set of Boolean functions in the class of ESPPs is considered; it is defined as the maximum length of a Boolean function of n variables in the class of ESPPs. It is proved that L ^ESPP(n) = ? (2 ⁿ /n ²). The quantity L ^ESPP(n) also equals the least number l such that any Boolean function of n variables can be represented as a modulo-2 sum of at most l multiaffine functions.