A discrete version of Koldobsky’s slicing inequality

Let #K be a number of integer lattice points contained in a set K. In this paper we prove that for each d ∈ N there exists a constant C(d) depending on d only, such that for any origin-symmetric convex body K ? R ^d containing d linearly independent lattice points

$$\# K \leqslant C\left( d \right)\max \left( {\# \left( {K \cap H} \right)} \right)vo{l_d}{\left( K \right)^{\frac{{d - m}}{d}}},$$

where the maximum is taken over all m-dimensional subspaces of R ^d . We also prove that C(d) can be chosen asymptotically of order O(1) ^d d ^d?m . In particular, we have order O(1) ^d for hyperplane slices. Additionally, we show that if K is an unconditional convex body then C(d) can be chosen asymptotically of order O(d) ^d?m .

     

On the sum of the L1 influences of bounded functions

Let f: {-1, 1}ⁿ → [-1, 1] have degree d as a multilinear polynomial. It is well-known that the total influence of f is at most d. Aaronson and Ambainis asked whether the total L₁ influence of f can also be bounded as a function of d. Ba?kurs and Bavarian answered this question in the affirmative, providing a bound of O(d³) for general functions and O(d²) for homogeneous functions. We improve on their results by providing a bound of d² for general functions and O(d log d) for homogeneous functions. In addition, we prove a bound of d/(2p) + o(d) for monotone functions, and provide a matching example.     

Dynamic bivariate normal copula

Normal copula with a correlation coefficient between-1 and 1 is tail independent and so it severely underestimates extreme probabilities. By letting the correlation coefficient in a normal copula depend on the sample size, H¨usler and Reiss(1989) showed that the tail can become asymptotically dependent. We extend this result by deriving the limit of the normalized maximum of n independent observations, where the i-th observation follows from a normal copula with its correlation coefficient being either a parametric or a nonparametric function of i/n. Furthermore, both parametric and nonparametric inference for this unknown function are studied, which can be employed to test the condition by H¨usler and Reiss(1989). A simulation study and real data analysis are presented too.     

On an Extremal Problem for Poset Dimension

Let f(n) be the largest integer such that every poset on n elements has a 2-dimensional subposet on f(n) elements. What is the asymptotics of f(n)? It is easy to see that f(n) = n ^1/2. We improve the best known upper bound and show f(n) = O (n ^2/3). For higher dimensions, we show \(f_{d}(n)=\O \left (n^{\frac {d}{d + 1}}\right )\), where f _d (n) is the largest integer such that every poset on n elements has a d-dimensional subposet on f _d (n) elements.     

An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d?1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.     

Convergence analysis of the rectangular Morley element scheme for second order problem in arbitrary dimensions

We present the convergence analysis of the rectangular Morley element scheme utilised on the second order problem in arbitrary dimensions. Specifically, we prove that the convergence of the scheme is of O(h) order in energy norm and of O(h²) order in L² norm on general d-rectangular triangulations. Moreover, when the triangulation is uniform, the convergence rate can be of O(h²) order in energy norm, and the convergence rate in L² norm is still of O(h²) order, which cannot be improved. Numerical examples are presented to demonstrate our theoretical results.     

Nonsingularity,positive definiteness,and positive invertibility under fixed-point data rounding

For a real square matrix A and an integer d ? 0, let A _(d) denote the matrix formed from A by rounding off all its coefficients to d decimal places. The main problem handled in this paper is the following: assuming that A _(d) has some property, under what additional condition(s) can we be sure that the original matrix A possesses the same property? Three properties are investigated: nonsingularity, positive definiteness, and positive invertibility. In all three cases it is shown that there exists a real number α(d), computed solely from A _(d) (not from A), such that the following alternative holdsif d > α(d), then nonsingularity (positive definiteness, positive invertibility) of A _(d) implies the same property for A if d < α(d) and A _(d) is nonsingular (positive definite, positive invertible), then there exists a matrix A′ with A′_(d) = A _(d) which does not have the respective property.For nonsingularity and positive definiteness the formula for α(d) is the same and involves computation of the NP-hard norm ‖ · ‖_∞,1; for positive invertibility α(d) is given by an easily computable formula.     

On Generalized Derivations and Centralizers of Operator Algebras with Involution

Let B(H) be the algebra of all bounded linear operators on a complex Hilbert space H and A(H) ? B(H) be a standard operator algebra which is closed under the adjoint operation. Let F: A(H)→ B(H) be a linear mapping satisfying F(AA*A) = F(A)A*A + Ad(A*)A + AA*d(A) for all A ∈ A(H), where the associated linear mapping d: A(H) → B(H) satisfies the relation d(AA*A) = d(A)A*A + Ad(A*)A + AA*d(A) for all A ∈ A(H). Then F is of the form F(A) = SA ? AT for all A ∈ A(H) and some S, T ∈ B(H), that is, F is a generalized derivation. We also prove some results concerning centralizers on A(H) and semisimple H^*-algebras.     

An approximation scheme for a problem of search for a vector subset

We consider the following clustering problem: Given a vector set, find a subset of cardinality k and minimum square deviation from its mean. The distance between the vectors is defined by the Euclideanmetric. We present an approximation scheme (PTAS) that allows us to solve this problem with an arbitrary relative error ? in time O(n ^2/?+1(9/?)^3/? d), where n is the number of vectors of the input set and d denotes the dimension of the space.     

The Four-in-a-Tree Problem in Triangle-Free Graphs

The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time O(n ⁴) whether three given vertices of a graph belong to an induced tree. Here, we study four-in- a-tree for triangle-free graphs. We give a structural answer to the following question: what does a triangle-free graph look like if no induced tree covers four given vertices? Our main result says that any such graph must have the “same structure”, in a sense to be defined precisely, as a square or a cube. We provide an O(nm)-time algorithm that given a triangle-free graph G together with four vertices outputs either an induced tree that contains them or a partition of V(G) certifying that no such tree exists. We prove that the problem of deciding whether there exists a tree T covering the four vertices such that at most one vertex of T has degree at least 3 is NP-complete.     

The pos/neg-weighted 2-medians in balanced trees with subtree-shaped customers

This paper deals with the pos/neg-weighted p-median problem on tree graphs where all customers are modeled as subtrees. We present a polynomial algorithm for the 2-median problem on an arbitrary tree. Then we improve the time complexity to O(n log n) for the problem on a balanced tree, where n is the number of the vertices in the tree.     

On the asymptotic optimality of a solution of the euclidean problem of covering a graph by <Emphasis Type="Italic">m</Emphasis> nonadjacent cycles of maximum total weight

In the problem of covering an n-vertex graph by m cycles of maximum total weight, it is required to find a family of m vertex-nonadjacent cycles such that it covers all vertices of the graph and the total weight of edges in the cover is maximum. The paper presents an algorithm for approximately solving the problem of covering a graph in Euclidean d-space R^d by m nonadjacent cycles of maximum total weight. The algorithm has time complexity O(n³). An estimate of the accuracy of the algorithm depending on the parameters d, m, and n is substantiated; it is shown that if the dimension d of the space is fixed and the number of covering cycles is m = o(n), then the algorithm is asymptotically exact.     

Some variations on Tverberg’s theorem

Define T(d, r) = (d + 1)(r - 1) + 1. A well known theorem of Tverberg states that if n ≥ T(d, r), then one can partition any set of n points in R^d into r pairwise disjoint subsets whose convex hulls have a common point. The numbers T(d, r) are known as Tverberg numbers. Reay added another parameter k (2 ≤ k ≤ r) and asked: what is the smallest number n, such that every set of n points in R^d admits an r-partition, in such a way that each k of the convex hulls of the r parts meet. Call this number T(d, r, k). Reay conjectured that T(d, r, k) = T(d, r) for all d, r and k. In this paper we prove Reay’s conjecture in the following cases: when k ≥ [d+3/2], and also when d < rk/r-k - 1. The conjecture also holds for the specific values d = 3, r = 4, k = 2 and d = 5, r = 3, k = 2.     

Nonparametric spatial models for extremes: application to extreme temperature data

Estimating the probability of extreme temperature events is difficult because of limited records across time and the need to extrapolate the distributions of these events, as opposed to just the mean, to locations where observations are not available. Another related issue is the need to characterize the uncertainty in the estimated probability of extreme events at different locations. Although the tools for statistical modeling of univariate extremes are well-developed, extending these tools to model spatial extreme data is an active area of research. In this paper, in order to make inference about spatial extreme events, we introduce a new nonparametric model for extremes. We present a Dirichlet-based copula model that is a flexible alternative to parametric copula models such as the normal and t-copula. The proposed modelling approach is fitted using a Bayesian framework that allow us to take into account different sources of uncertainty in the data and models. We apply our methods to annual maximum temperature values in the east-south-central United States.     

Distance domination of generalized de Bruijn and Kautz digraphs

Let G = (V,A) be a digraph and k ≥ 1 an integer. For u, v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G _B (n, d) and generalized Kautz digraphs G _K (n, d) are good candidates for interconnection networks. Denote Δ _k := (∑ _j=0 ^k d ^j )^?1. F. Tian and J. Xu showed that ?nΔ _k ? γ _k (G _B (n, d)) ≤?n/d ^k? and ?nΔ _k ? ≤ γ _k (G _K (n, d)) ≤ ?n/d ^k ?. In this paper, we prove that every generalized de Bruijn digraph G _B (n, d) has the distance k-domination number ?nΔ _k ? or ?nΔ _k ?+1, and the distance k-domination number of every generalized Kautz digraph G _K (n, d) bounded above by ?n/(d ^k?1+d ^k )?. Additionally, we present various sufficient conditions for γ _k (G _B (n, d)) = ?nΔ _k ? and γ _k (G _K (n, d)) = ?nΔ _k ?.     

Super (<Emphasis Type="Italic">a</Emphasis>, <Emphasis Type="Italic">d</Emphasis>)-edge-antimagic total labelings of complete bipartite graphs

An (a, d)-edge-antimagic total labeling of a graph G is a bijection f from V(G) ∪ E(G) onto {1, 2,…,|V(G)| + |E(G)|} with the property that the edge-weight set {f(x) + f(xy) + f(y) | xy ∈ E(G)} is equal to {a, a + d, a + 2d,...,a + (|E(G)| ? 1)d} for two integers a > 0 and d ? 0. An (a, d)-edge-antimagic total labeling is called super if the smallest possible labels appear on the vertices. In this paper, we completely settle the problem of the super (a, d)-edge-antimagic total labeling of the complete bipartite graph K_m,n and obtain the following results: the graph K_m,n has a super (a, d)-edge-antimagic total labeling if and only if either (i) m = 1, n = 1, and d ? 0, or (ii) m = 1, n ? 2 (or n = 1 and m ? 2), and d ∈ {0, 1, 2}, or (iii) m = 1, n = 2 (or n = 1 and m = 2), and d = 3, or (iv) m, n ? 2, and d = 1.     

On Ranks of Polynomials

Let V be a vector space over a field k, P : V → k, d ≥?3. We show the existence of a function C(r, d) such that rank(P) ≤ C(r, d) for any field k, char(k) > d, a finite-dimensional k-vector space V and a polynomial P : V → k of degree d such that rank(?P/?t) ≤ r for all t ∈ V ??0. Our proof of this theorem is based on the application of results on Gowers norms for finite fields k. We don’t know a direct proof even in the case when k = ?.     

A remark on the ring of algebraic integers in $$\mathbb{Q}(\sqrt { - d} )$$

It is well-known that the rings O_d of algebraic integers in \(\mathbb{Q}(\sqrt { - d} )\) for d = 19, 43, 67, and 163 are principal ideal domains but not Euclidean. In this article we shall provide a method, based on a result of P. M. Cohn, to construct explicitly pairs (b, a) of integers in O_d for d = 19, 43, 67, and 163 such that, in O_d, there exists no terminating division chain of finite length starting from the pairs (b, a). That is, a greatest common divisor of the pairs (b, a) exists in O_d but it can not be obtained by applying a terminating division chain of finite length starting from (b, a). Furthermore, for squarefree positive integer d ? {1, 2, 3, 7, 11, 19, 43, 67, 163}, we shall also construct pairs (b, a) of integers in O_d which generate O_d but have no terminating division chain of finite length. It is of interest to note that our construction provides a short alternative proof of a theorem of Cohn which is related to the concept of GE₂-rings.     

Chromatic number and subtrees of graphs

Let G and H be two graphs. We say that G induces H if G has an induced subgraph isomorphic to H: A. Gyárfás and D. Sumner, independently, conjectured that, for every tree T. there exists a function f _T ; called binding function, depending only on T with the property that every graph G with chromatic number f _T (ω(G)) induces T. A. Gyárfás, E. Szemerédi and Z. Tuza confirmed the conjecture for all trees of radius two on triangle-free graphs, and H. Kierstead and S. Penrice generalized the approach and the conclusion of A. Gyárfás et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer k and every tree T of radius r, every graph G with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(14 ^r-1(r - 1)!) times. We extend the approach of A. Gyárfás and present a binding function for trees obtained by identifying one end of a path and the center of a star. We also improve A. Scott's upper bound by modifying his subtree structure and partition technique, and show that for every integer k and every tree T of radius r, every graph with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(6 ^r?2) times.     

Constructing permutation arrays from groups

Let M(n, d) be the maximum size of a permutation array on n symbols with pairwise Hamming distance at least d. We use various combinatorial, algebraic, and computational methods to improve lower bounds for M(n, d). We compute the Hamming distances of affine semilinear groups and projective semilinear groups, and unions of cosets of AGL(1, q) and PGL(2, q) with Frobenius maps to obtain new, improved lower bounds for M(n, d). We give new randomized algorithms. We give better lower bounds for M(n, d) also using new theorems concerning the contraction operation. For example, we prove a quadratic lower bound for \(M(n,n-2)\) for all \(n\equiv 2 \pmod 3\) such that \(n+1\) is a prime power.