Pairwise Balanced Designs with Prescribed Minimum Dimension

The dimension of a linear space is the maximum positive integer d such that any d of its points generate a proper subspace. For a set K of integers at least two, recall that a pairwise balanced design $\operatorname{PBD}(v,K)$ is a linear space on v points whose lines (or blocks) have sizes belonging to K. We show that, for any prescribed set of sizes K and lower bound d on the dimension, there exists a $\operatorname{PBD}(v,K)$ of dimension at least d for all sufficiently large and numerically admissible v.     

The Characterization for a Graphic Sequence to have a Realization Containing K 1,1,s

A graphic sequence π?=?(d ₁, d ₂, . . . , d _n ) is said to be potentially K _1,1,s -graphic if there is a realization of π containing K _1,1,s as a subgraph, where K _1,1,s is the 1?× 1?× s complete 3-partite graph. In this paper, a simple characterization of potentially K _1,1,s -graphic sequences for s?≥ 2 and n?≥ 3s?+?1 is obtained. This characterization implies Lai’s conjecture on σ(K _1,1,s , n), which was confirmed by J.H. Yin, J.S. Li and W.Y. Li, and the values of σ(K _2,s , n) for s?≥ 4 and n?≥ 3s?+?1, where K _2,s is the 2?× s complete bipartite graph.     

The degree of an integral point in Ps minus a hypersurface

Let K be a number field of degree m with ring of integers R and absolute discriminant d_K. Given a hypersurface Z_K of degree d in the projective space P_K^us over K with Zariski closure Z in P_R^s, we give an explicit function of m, d_K, s,d, a Hermitian metric on R^s+1 ⊗_z C, and a projective height of Z defined in [1], 4.1, such that there exists an integral point in P_R^s Z of degree bounded by this function.     

Approximation of convex bodies by polytopes with uniformly bounded valences

Given any convex bodyK in Euclideann-spaceR ⁿ and any number ?>0, does there always exist a polytopeP(K, ?)?R ⁿ such that the number of vertices of a facet ofP and the number of facets meeting in a common vertex are bounded by a constant depending on the dimensiond only and such that the Hausdorff-distance ? (K, P) ofK andP is less than ?? This question of Ewald posed at the Durham symposium in 1975 is answered in the affirmative.     

Disjoint cliques in claw-free graphs

A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K_1,3. Let s and k be two integers with 0 ≤ s ≤ k and let G be a claw-free graph of order n. In this paper, we investigate clique partition problems in claw-free graphs. It is proved that if n ≥ 3s+4(k?s) and d(x)+d(y) ≥ n?2s+2k+1 for any pair of non-adjacent vertices x, y of G, then G contains s disjoint K₃s and k ? s disjoint K₄s such that all of them are disjoint. Moreover, the degree condition is sharp in some cases.     

Graphic sequences and split graphs

The split graph K _rVK _s on r+s vertices is denoted by S _r,s. A graphic sequence π = (d ₁, d ₂, ···, d _n) is said to be potentially S _r,s-graphic if there is a realization of π containing S _r,s as a subgraph. In this paper, a simple sufficient condition for π to be potentially S _r,s-graphic is obtained, which extends an analogous condition for p to be potentially K _r+1-graphic due to Yin and Li (Discrete Math. 301 (2005) 218–227). As an application of this condition, we further determine the values of σ(S _r,s, n) for n ≥ 3r + 3s - 1.     

Central limit theorems for random polytopes in a smooth convex set

Let K be a smooth convex set with volume one in Rd. Choose n random points in K independently according to the uniform distribution. The convex hull of these points, denoted by Kn, is called a random polytope. We prove that several key functionals of Kn satisfy the central limit theorem as n tends to infinity.     

On defining numbers of circular complete graphs

Let d(σ) stand for the defining number of the colouring σ. In this paper we consider and for the onto χ-colourings γ of the circular complete graph K_n,d. In this regard we obtain a lower bound for d^min(K_n,d) and we also prove that this parameter is asymptotically equal to χ-1. Also, we show that when χ?4 and s≠0 then d^max(K_χd-s,d)=χ+2s-3, and, moreover, we prove an inequality relating this parameter to the circular chromatic number for any graph G.     

How many s-subspaces must miss a point set in PG(d, q)

The following result is well-known for finite projective spaces. The smallest cardinality of a set of points of PG(n, q) with the property that every s-subspace has a point in the set is (q ^n+1-s - 1)/(q - 1). We solve in finite projective spaces PG(n, q) the following problem. Given integers s and b with 0 ≤ s ≤ n - 1 and 1 ≤ b ≤ (q ^n+1-s - 1)/(q - 1), what is the smallest number of s-subspaces that must miss a set of b points. If d is the smallest integer such that b ≤ (q ^d+1 - 1)/(q - 1), then we shall see that the smallest number is obtained only when the b points generate a subspace of dimension d. We then also determine the smallest number of s-subspaces that must miss a set of b points of PG(n, q) which do not lie together in a subspace of dimension d. The results are obtained by geometrical and combinatorial arguments that rely on a strong algebraic result for projective planes by T. Szőnyi and Z. Weiner.     

Some inequalities for multidimensional (0,1)- matrices

Can there exist a (0,1)-matrix of order n and dimension d, such that the sum on any e-dimensional hyperplane of the matrix is a fixed number r? The answer to this question is of importance both for the construction of incomplete block designs and for the investigation of extremal points in the convex sets of multidimensional stochastic matrices. Some necessary conditions that must be fulfilled by the parameters n, d, e, and r are deduced in this paper.     

Close-to-normal structure and its applications

Let K be a bounded subset of a metric space (B, d). Let W(K) be the supremum of the cardinals of all subsets H of K such that the distance between any two distinct points in H is equal to the diameter of K. This function W on the family of all bounded subsets of B is used to prove the following result. Let K be a weakly compact convex subset of a Banach space B. Then K has a close-to-normal structure if B satisfies any of the following conditions: (a) B is strictly convex; (b) B is separable; (c) B has the property A: For any sequence {x_n} in B, {x_n} converges to a point x in B if it converges weakly to x and {∥x_n∥} converges to ∥x∥. Applications of this result to the fixed point theory are given.     

Time-optimal trajectories of generic control-affine systems have at worst iterated Fuller singularities

We consider in this paper the regularity problem for time-optimal trajectories of a single-input control-affine system on a n-dimensional manifold. We prove that, under generic conditions on the drift and the controlled vector field, any control u associated with an optimal trajectory is smooth out of a countable set of times. More precisely, there exists an integer K, only depending on the dimension n, such that the non-smoothness set of u is made of isolated points, accumulations of isolated points, and so on up to K-th order iterated accumulations.     

Reconstructing edge-disjoint paths

For an undirected graph G=(V,E), the edge connectivity values between every pair of nodes of G can be succinctly recorded in a flow-equivalent tree that contains the edge connectivity value for a linear number of pairs of nodes. We generalize this result to show how we can efficiently recover a maximum set of disjoint paths between any pair of nodes of G by storing such sets for a linear number of pairs of nodes. At the heart of our result is an observation that combining two flow solutions of the same value, one between nodes s and r and the second between nodes r and t, into a feasible flow solution of value f between nodes s and t, is equivalent to solving a stable matching problem on a bipartite multigraph.Our observation, combined with an observation of Chazelle, leads to a data structure, which takes O(n^3.5) time to generate, that can construct the maximum number λ(u,v) of edge-disjoint paths between any pair (u,v) of nodes in time O(α(n,n)λ(u,v)n) time.     

Tame linear extension operators for smooth Whitney functions

For a compact set K⊆Rd we present a rather easy construction of a linear extension operator E:E(K)→C^∞(Rd) for the space of Whitney jets E(K) which satisfies linear tame continuity estimates , where ‖⋅s_‖ denotes the s-th Whitney norm. The construction turns out to be possible if and only if the local Markov inequality LMI(s) introduced by Bos and Milman holds for every s>r on K. In particular, E(K) admits a tame linear extension operator if and only if the local Markov inequality LMI(s) holds on K for some s?1.     

On the homogeneous algebraic graphs of large girth and their applications

Families of finite graphs of large girth were introduced in classical extremal graph theory. One important theoretical result here is the upper bound on the maximal size of the graph with girth ?2d established in Even Circuit Theorem by P. Erdös. We consider some results on such algebraic graphs over any field. The upper bound on the dimension of variety of edges for algebraic graphs of girth ?2d is established. Getting the lower bound, we use the family of bipartite graphs D(n,K) with n?2 over a field K, whose partition sets are two copies of the vector space Kⁿ. We consider the problem of constructing homogeneous algebraic graphs with a prescribed girth and formulate some problems motivated by classical extremal graph theory. Finally, we present a very short survey on applications of finite homogeneous algebraic graphs to coding theory and cryptography.     

Representation sets for integral binary quadratic forms over the rationals

Let f be an integral binary form of discriminant d which represents n integrally. Two rational representations (r, s) and (r′, s′), with denominators prime to n, of n by f are called semiequivalent with respect to f if there is a rational automorph of f with determinant 1 and denominator m which takes (r, s) into (r′, s′) where (m, n) = 1 and m contains no factors p of d such that $\text{d}\text{p}{}^2$ is a discriminant. The number of such equivalence classes for a given f and n is sometimes finite. This number is obtained for forms with negative discriminants which have one class in each primitive genus.     

Carmichael numbers in number rings

We generalize Carmichael numbers to ideals in number rings and prove a generalization of Korselt's Criterion for these Carmichael ideals. We investigate when Carmichael numbers in the integers generate Carmichael ideals in the algebraic integers of abelian number fields. In particular, we show that given any composite integer n, there exist infinitely many quadratic number fields in which n is not Carmichael. Finally, we show that there are infinitely many abelian number fields K with discriminant relatively prime to n such that n is not Carmichael in K.     

Existence Criterion for Estimates of Derivatives of Rational Functions

Suppose that K is a compact set in the open complex plane. In this paper, we prove an existence criterion for an estimate of Markov-Bernstein type for derivatives of a rational function R(z) at any fixed point z ₀ ∈ K. We prove that, for a fixed integer s, the estimate of the form |R ^(s) (z ₀)| ≤ C(K, z ₀, s)n‖R‖ _C(K), where R is an arbitrary rational function of degree n without poles on K and C is a bounded function depending on three arguments K, z ₀, and s, holds if and only if the supremum $$\omega (K,z_0 ,s) = \sup \left\{ {\frac{{\operatorname{dist} (z,K)}}{{\left| {z - z_0 } \right|^{s + 1} }}} \right\}$$ over z in the complement of K is finite. Under this assumption, C is less than or equal to const ·s!ω(K, z ₀, s).     

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.     

On digit sums of multiples of an integer

Let g>1 be an integer and sg(m) be the sum of digits in base g of the positive integer m. In this paper, we study the positive integers n such that sg(n) and sg(kn) satisfy certain relations for a fixed, or arbitrary positive integer k. In the first part of the paper, we prove that if n is not a power of g, then there exists a nontrivial multiple of n say kn such that sg(n)=sg(kn). In the second part of the paper, we show that for any K>0 the set of the integers n satisfying sg(n)?Ksg(kn) for all k∈N is of asymptotic density 0. This gives an affirmative answer to a question of W.M. Schmidt.