Characteristic properties of equivalent structures in compositional models

Compositional model theory serves as an alternative approach to multidimensional probability distribution representation and processing. Every compositional model over a finite non-empty set of variables N is uniquely defined by its generating sequence - an ordered set of low-dimensional probability distributions. A generating sequence structure induces a system of conditional independence statements over N valid for every multidimensional distribution represented by a compositional model with this structure.The equivalence problem is how to characterise whether all independence statements induced by structure P are induced by a second structure P^′ and vice versa. This problem can be solved in several ways. A partial solution of the so-called direct characterisation of an equivalence problem is represented here. We deduce and describe three properties of equivalent structures necessary for equivalence of the respective structures. We call them characteristic properties of classes of equivalent structures.     

Colorful flowers

For a set A let k[A] denote the family of all k-element subsets of A. A function f:k[A]→C is a local coloring if it maps disjoint sets of A into different elements of C. A family F⊆k[A] is called a flower if there exists E∈[A]^k−1 so that |F∩F^′|=E for all F,F^′∈F, F≠F^′. A flower is said to be colorful if f(F)≠f(F^′) for any two F,F^′∈F. In the paper we find the smallest cardinal γ such that there exists a local coloring of k[A] containing no colorful flower of size γ. As a consequence we answer a question raised by Pelant, Holický and Kalenda. We also discuss a few results and conjectures concerning a generalization of this problem.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(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 c_H(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:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

Complete solving of explicit evaluation of Gauss sums in the index 2 case

Let p be a prime number,N be a positive integer such that gcd(N,p) = 1,q = pf where f is the multiplicative order of p modulo N.Let χ be a primitive multiplicative character of order N over finite field Fq.This paper studies the problem of explicit evaluation of Gauss sums G(χ) in the "index 2 case"(i.e.[(Z/NZ):p] = 2).Firstly,the classification of the Gauss sums in the index 2 case is presented.Then,the explicit evaluation of Gauss sums G(χλ)(1 λ N-1) in the index 2 case with order N being general even integer(i.e.N = 2r·N0,where r,N0 are positive integers and N0 3 is odd) is obtained.Thus,combining with the researches before,the problem of explicit evaluation of Gauss sums in the index 2 case is completely solved.     

Similarity classes of3 × 3 matrices over a discrete valuation ring

Let Q be a complete discrete valuation ring. Let Π be a prime element in Q. Write P = ΠQ. For n = 1,2,…, letQ_n be the factor ring Q | Pⁿ. Let G = G1₃(Q_n. Denote by M?_n the G-module of 3 × 3 matrices over Q_n modulo scalar matrices. Canonical forms are found for every element in M?_n, and it is shown that there exist five sets of similarity classes. Some results about the general case of NxN matrices over Q also are proved.     

On exact recovery of sparse vectors from linear measurements

Let 1 ≤ k ≤ n < N. We say that a vector x ∈ ? ^N is k-sparse if it has at most k nonzero coordinates. Let Φ be an n × N matrix. We consider the problem of recovery of a k-sparse vector x ∈ ? ^N from the vector y = Φx ∈ ? ⁿ . We obtain almost-sharp necessary conditions for k, n, N for this problem to be reduced to that of minimization of the ?₁-norm of vectors z satisfying the condition y = Φz.     

Partitions of natural numbers with the same representation functions

For a set A of nonnegative integers the representation functions R₂(A,n), R₃(A,n) are defined as the number of solutions of the equation n=a+a^′,a,a^′∈A with a<a^′, a?a^′, respectively. Let D(0)=0 and let D(a) denote the number of ones in the binary representation of a. Let A₀ be the set of all nonnegative integers a with even D(a) and A₁ be the set of all nonnegative integers a with odd D(a). In this paper we show that (a) if R₂(A,n)=R₂(N?A,n) for all n?2N−1, then R₂(A,n)=R₂(N?A,n)?1 for all n?12N²−10N−2 except for A=A₀ or A=A₁; (b) if R₃(A,n)=R₃(N?A,n) for all n?2N−1, then R₃(A,n)=R₃(N?A,n)?1 for all n?12N²+2N. Several problems are posed in this paper.     

A note on transitive permutation groups of prime degree

LetG be a nonsolvable transitive permutation group of prime degreep. LetP be a Sylow-p-subgroup ofG and letq be a generator of the subgroup ofN _G(P) fixing one point. Assume that |N _G(P)|=p(p?1) and that there exists an elementj inG such thatj ^?1qj=q^(p+1)/2. We shall prove that a group that satisfies the above condition must be the symmetric group onp points, andp is of the form 4n+1.     

On newforms for Kohnen plus spaces

In this article, we investigate the plus space of level N, where 4^?1 N is a square-free (not necessarily odd) integer. This is a generalization of Kohnen’s work. We define a Hecke isomorphism ${\wp_k}In this article, we investigate the plus space of level N, where 4⁻¹ N is a square-free (not necessarily odd) integer. This is a generalization of Kohnen’s work. We define a Hecke isomorphism ?_k{\wp_k} of M _k+1/2(4M) onto M_k+1/2⁺(8M){M_{k+1/2}^+(8M)} for any odd positive integer M. The methods of the proof of the newform theory are this isomorphism, Waldspurger’s theorem, and the dimension identity.     

The Mixed Problem for the Laplacian in Lipschitz Domains

We consider the mixed boundary value problem, or Zaremba’s problem, for the Laplacian in a bounded Lipschitz domain Ω in R ⁿ , n?≥?2. We decompose the boundary $ \partial \Omega= D\cup N$ with D and N disjoint. The boundary between D and N is assumed to be a Lipschitz surface in $\partial \Omega$ . We find an exponent q ₀?>?1 so that for p between 1 and q ₀ we may solve the mixed problem for L ^p . Thus, if we specify Dirichlet data on D in the Sobolev space W ^1,p (D) and Neumann data on N in L ^p (N), the mixed problem with data f _D and f _N has a unique solution and the non-tangential maximal function of the gradient lies in $L^p( \partial \Omega)$ . We also obtain results for p?=?1 when the data comes from Hardy spaces.     

Some applications of Montgomery's sieve

Artin has conjectured that every positive integer not a perfect square is a primitive root for some odd prime. A new estimate is obtained for the number of integers in the interval [M + 1, M + N] which are not primitive roots for any odd prime, improving on a theorem of Gallagher.Erd?s has conjectured that 7, 15, 21, 45, 75, and 105 are the only values of the positive integer n for which n ? 2^k is prime for every k with 1 ≤ k ≤ log₂n. An estimate is proved for the number of such n ≤ N.     

On the characterization of trees with signed edge domination numbers 1, 2, 3, or 4

Let G=(V,E) be a simple graph. For an edge e of G, the closed edge-neighbourhood of e is the set N[e]={e^′∈E|e^′ is adjacent to e}∪{e}. A function f:E→{1,−1} is called a signed edge domination function (SEDF) of G if ∑_e^′∈N[e]f(e^′)≥1 for every edge e of G. The signed edge domination number of G is defined as . In this paper, we characterize all trees T with signed edge domination numbers 1, 2, 3, or 4.     

The nonnegative rank factorizations of nonnegative matrices

Let A ∈ P^{m × n}_r, the set of all m × n nonnegative matrices having the same rank r. For matrices A in P^{m × n}_n, we introduce the concepts of “A has only trivial nonnegative rank factorizations” and “A can have nontrivial nonnegative rank factorizations.” Correspondingly, the set P^{m × n}_n is divided into two disjoint subsets P₍₁₎ and P₍₂₎ such that P₍₁₎∪P₍₂₎ = P^{m × n}_n. It happens that the concept of “A has only trivial nonnegative rank factorizations” is a generalization of “A is prime in P^{n × n}_n.” We characterize the sets P₍₁₎ and P₍₂₎. Some of our results generalize some theorems in the paper of Daniel J. Richman and Hans Schneider [9].     

Rank-sets of indecomposable modules over one-dimensional rings

Let R be a one-dimensional, reduced Noetherian ring with finite normalization, and suppose there exists a positive integer N_R such that, for every indecomposable finitely generated torsion-free R-module M and every minimal prime ideal P of R, the dimension of M_P, as a vector space over the localization R_P (a field), is less than or equal to N_R. For a finitely generated torsion-free R-module M, we call the set of all such vector-space dimensions the rank-set of M. What subsets of the integers arise as rank-sets of indecomposable finitely generated torsion-free R-modules? In this article, we give more information on rank-sets of indecomposable modules, to supplement previous work concerning this question. In particular we provide examples having as rank-sets those intervals of consecutive integers that are not ruled out by an earlier article of Arnavut, Luckas and Wiegand. We also show that certain non-consecutive rank-sets never arise.     

A monotone iterative technique for stationary and time dependent problems in Banach spaces

An abstract monotone iterative method is developed for operators between partially ordered Banach spaces for the nonlinear problem Lu=Nu and the nonlinear time dependent problem u^′=(L+N)u. Under appropriate assumptions on L and N we obtain maximal and minimal solutions as limits of monotone sequences of solutions of linear problems. The results are illustrated by means of concrete examples.     

Small subgraphs in random graphs and the power of multiple choices

The standard paradigm for online power of two choices problems in random graphs is the Achlioptas process. Here we consider the following natural generalization: Starting with G₀ as the empty graph on n vertices, in every step a set of r edges is drawn uniformly at random from all edges that have not been drawn in previous steps. From these, one edge has to be selected, and the remaining r−1 edges are discarded. Thus after N steps, we have seen rN edges, and selected exactly N out of these to create a graph GN.In a recent paper by Krivelevich, Loh, and Sudakov (2009) [11], the problem of avoiding a copy of some fixed graph F in GN for as long as possible is considered, and a threshold result is derived for some special cases. Moreover, the authors conjecture a general threshold formula for arbitrary graphs F. In this work we disprove this conjecture and give the complete solution of the problem by deriving explicit threshold functions N₀(F,r,n) for arbitrary graphs F and any fixed integer r. That is, we propose an edge selection strategy that a.a.s. (asymptotically almost surely, i.e. with probability 1−o(1) as n→∞) avoids creating a copy of F for as long as N=o(N₀), and prove that any online strategy will a.a.s. create such a copy once N=ω(N₀).     

Surjective partial differential operators on real analytic functions defined on open convex sets

Let P(D) be a partial differential operator with constant coefficients which is surjective on the space A(Ω) of real analytic functions on a covex open set Ω⊂ℝ ⁿ . Let L(P _m ) denote the localizations at ∞ (in the sense of H?rmander) of the principal part P _m . Then Q(x+iτN)≠ 0 for (x,τ)∈ℝ ⁿ ×(ℝ\{ 0}) for any Q∈L(P _m ) if N is a normal to δΩ which is noncharacteristic for Q. Under additional assumptions this implies that P _m must be locally hyperbolic. Received: 24 January 2000     

A modified greedy algorithm for dispersively weighted 3-set cover

The set cover problem is that of computing a minimum weight subfamily F^′, given a family F of weighted subsets of a base set U, such that every element of U is covered by some subset in F^′. The k-set cover problem is a variant in which every subset is of size at most k. It has been long known that the problem can be approximated within a factor of by the greedy heuristic, but no better bound has been shown except for the case of unweighted subsets. In this paper we consider approximation of a restricted version of the weighted 3-set cover problem, as a first step towards better approximation of general k-set cover problem, where any two distinct subset costs differ by a multiplicative factor of at least 2. It will be shown, via LP duality, that an improved approximation bound of H(3)-1/6 can be attained, when the greedy heuristic is suitably modified for this case. A key to our algorithm design and analysis is the Gallai-Edmonds structure theorem for maximum matchings.     

Singular integral operators and norm ideals satisfying a quantitative variant of Kuroda's condition

A norm ideal C is said to satisfy condition (QK) if there exist constants 0<t<1 and 0<B<∞, such that ∥X^[k]∥_C?Bk^t∥X∥_C for every finite-rank operator X and every k∈N, where X^[k] denotes the direct sum of k copies of X. Let μ be a regular Borel measure whose support is contained in a unit cube Q in Rⁿ and let K_j be the singular integral operator on L²(Rⁿ,μ) with the kernel function (x_j-y_j)/|x-y|², 1?j?n. Let {Q_w:w∈W} be the usual dyadic decomposition of Q, i.e., {Q_w:|w|=?} is the dyadic partition of Q by cubes of the size 2^-?×?×2^-?. We show that if C satisfies (QK) and if ∥∑_w∈W2^|w|μ(Q_w)ξ_w⊗ξ_w∥_C^′<∞, where C^′ is the dual of C⁽⁰⁾ and {ξ_w:w∈W} is any orthonormal set, then K₁,…,K_n∈C^′. This is a very general obstruction result for the problem of simultaneous diagonalization of commuting tuples of self-adjoint operators modulo C.     

Probability estimates for the distribution of Kolmogorov distance in the worst direction

ConsiderD _n the maximum Kolmogorov distance betweenP _n andP among all possible one-dimensional projections, whereP _n is an empirical measure based ond-dimensional i.i.d vectors with spherically symmetric probability measureP. We show in this paper that $$c_1 \lambda ^2 \exp ( - 2\lambda ^2 ) \leqslant P(\sqrt n D_n > \lambda )$$ for large λ,d≥2 and an appropriate constantc ₁. From this, when dimensiond is fixed, we give a negative answer to Huber's conjecture,P(D _n >ε)≤N exp(?2n? ²), whereN is a constant depending only on dimensiond.