A generalization of the katona theorem for crosst-intersecting families

LetX be ann-element set and letA and? be families of subsets ofX. We say thatA and? are crosst-intersecting if |A ∩ B| ≥ t holds for all A ∈A and for allB ∈ ?. Suppose thatA and ? are crosst-intersecting. This paper first proves a crosst-intersecting version of Harper's Theorem:

1. There are two crosst-intersecting Hamming spheresA ₀,? ₀ with centerX such that |A| ≤ |A ₀| and|?| ≤ |? ₀| hold.
2. Suppose thatt ≥ 2 and that the pair of integers (|A) is maximal with respect to direct product ordering among pairs of crosst-intersecting families. Then,A and? are Hamming spheres with centerX.

Using these claims, the following conjecture of Frankl is proven:

1. Ifn + t = 2k ? 1 then |A| |?| ≤ max \(\left\{ {\left( {K_k^n + \left( {_{k - 1}^{n - 1} } \right)} \right)^2 ,K_k^n K_{k - 1}^n } \right\}\) holds, whereK _l ⁿ is defined as \(\left( {_n^n } \right)\left( {_{n - 1}^n } \right) + \cdots + \left( {_l^n } \right).\)
2. Ifn + t = 2k then |A| |? ≤ (K _k ⁿ )² holds.

The extremal configurations are also determined.     

Straight line arrangements in the real projective plane

Let A be an arrangement of n pseudolines in the real projective plane and let p ₃(A) be the number of triangles of A. Grünbaum has proposed the following question. Are there infinitely many simple arrangements of straight lines with p ₃(A)=1/3n(n?1)? In this paper we answer this question affirmatively.     

Minimal decompositions of graphs into mutually isomorphic subgraphs

SupposeG _n={G ₁, ...,G _k } is a collection of graphs, all havingn vertices ande edges. By aU-decomposition ofG _n we mean a set of partitions of the edge setsE(G _t ) of theG _i , sayE(G _t )== \(\sum\limits_{j = 1}^r {E_{ij} } \) E _ij , such that for eachj, all theE _ij , 1≦i≦k, are isomorphic as graphs. Define the functionU(G _n) to be the least possible value ofr aU-decomposition ofG _n can have. Finally, letU _k (n) denote the largest possible valueU(G) can assume whereG ranges over all sets ofk graphs havingn vertices and the same (unspecified) number of edges. In an earlier paper, the authors showed that $$U_2 (n) = \frac{2}{3}n + o(n).$$ In this paper, the value ofU _k (n) is investigated fork>2. It turns out rather unexpectedly that the leading term ofU _k (n) does not depend onk. In particular we show $$U_k (n) = \frac{3}{4}n + o_k (n),k \geqq 3.$$      

Two results for monocompact measures

For every finite measure space (Ω,A, P) whereA is K₁-generated we prove the equivalence of compactness and monocompactness for P . Moreover, we prove the existence of a perfect, not monocompaot probability, thus answering an open question in [6]. Let P be a charge on the algebraA andK ?A be a monocompact class. We show that P is o-additive ifK ^S P-approximatesK ^S, the family of finite unions inK , needs not to be monocompact.     

Criteria for the injectivity of analytic sheaves

It is shown that a moduleL over the sheafO of germs of holomorphic functions on a domain G of Cⁿ is injective if and only if the following conditions are satisfied; a)L is flabby; b) for every closed set S ?G and every point z λ G, the stalk se _z of the sheafS ^L;U1→Γ S ^(U:L) is an injectiveO _z -module. It follows in particular that the sheaf of germs of hyperfunctions is injective over the sheaf of germs of analytic functions.     

Simple algebras of Weyl type

Over a fieldF of arbitrary characteristic, we define the associative and the Lie algebras of Weyl type on the same vector spaceA[D] =A?F[D] from any pair of a commutative associative algebra,A with an identity element and the polynomial algebraF[D] of a commutative derivation subalgebraD ofA We prove thatA[D], as a Lie algebra (modulo its center) or as an associative algebra, is simple if and only ifA isD-simple andA[D] acts faithfully onA. Thus we obtain a lot of simple algebras.     

Quasi-factors in ergodic theory

Motivated by the notion of quasi-factor in topological dynamics, we introduce an analogous notion in the context of ergodic theory. For two processes,X andY , we haveX?Y if and only ifY has a factor which is isomorphic to a quasi-factor ofX. On the other hand, weakly mixing processes can have nontrivial quasifactors which are not w.m. We characterize those ergodic processes which admit only trivial continuous ergodic quasi-factors, and use this characterization to conclude that a process with minimal selfjoinings is of this type. From this we derive the fact that for every suchX and any ergodicY eitherX ⊥Y orY extends some symmetric product ofX.     

A computational study and survey of methods for the single-row facility layout problem

The single-row facility layout problem (SRFLP) is an NP-hard combinatorial optimization problem that is concerned with the arrangement of n departments of given lengths on a line so as to minimize the weighted sum of the distances between department pairs. (SRFLP) is the one-dimensional version of the facility layout problem that seeks to arrange rectangular departments so as to minimize the overall interaction cost. This paper compares the different modelling approaches for (SRFLP) and applies a recent SDP approach for general quadratic ordering problems from Hungerländer and Rendl to (SRFLP). In particular, we report optimal solutions for several (SRFLP) instances from the literature with up to 42 departments that remained unsolved so far. Secondly we significantly reduce the best known gaps and running times for large instances with up to 110 departments.     

Nilpotent and solvable radicals in locally finite congruence modular varieties

The Loewy rank of a modular latticeL of finite height is defined as the leastn for which there exista ₀=0t, < ... r=1 inL such that each interval I[a_i, a_i+1] is a complemented lattice. In this paper, a generalized notion of Loewy rank is applied to obtain new results in the commutator theory of locally finite congruence modular varieties. LetV be a finitely generated congruence modular variety. We prove that every algebra inV has a largest nilpotent congruence and a largest solvable congruence. Moreover, there exist first order formulas which define these special congruences in every algebra ofV.     

Using RngStreams for parallel random number generation in C++ and R

The RngStreams software package provides one viable solution to the problem of creating independent random number streams for simulations in parallel processing environments. Techniques are presented for effectively using RngStreams with C++ programs that are parallelized via OpenMP or MPI. Ways to access the backbone generator from RngStreams in R through the parallel and rstream packages are also described. The ideas in the paper are illustrated with both a simple running example and a Monte Carlo integration application.     

Narrowness implies uniformity

This paper is about varietiesV of universal algebras which satisfy the following numerical condition on the spectrum: there are only finitely many prime integersp such thatp is a divisor of the cardinality of some finite algebra inV. Such varieties are callednarrow. The variety (or equational class) generated by a classK of similar algebras is denoted by V(K)=HSPK. We define Pr (K) as the set of prime integers which divide the cardinality of a (some) finite member ofK. We callK narrow if Pr (K) is finite. The key result proved here states that for any finite setK of finite algebras of the same type, the following are equivalent: (1) SPK is a narrow class. (2) V(K) has uniform congruence relations. (3) SK has uniform congruences and (3) SK has permuting congruences. (4) Pr (V(K))= Pr(SK). A varietyV is calleddirectly representable if there is a finite setK of finite algebras such thatV= V(K) and such that all finite algebras inV belong to PK. An equivalent definition states thatV is finitely generated and, up to isomorphism,V has only finitely many finite directly indecomposable algebras. Directly representable varieties are narrow and hence congruence modular. The machinery of modular commutators is applied in this paper to derive the following results for any directly representable varietyV. Each finite, directly indecomposable algebra inV is either simple or abelian.V satisfies the commutator identity [x,y]=x·y·[1,1] holding for congruencesx andy over any member ofV. The problem of characterizing finite algebras which generate directly representable varieties is reduced to a problem of ring theory on which there exists an extensive literature: to characterize those finite ringsR with identity element for which the variety of all unitary leftR-modules is directly representable. (In the terminology of [7], the condition is thatR has finite representation type.) We show that the directly representable varieties of groups are precisely the finitely generated abelian varieties, and that a finite, subdirectly irreducible, ring generates a directly representable variety iff the ring is a field or a zero ring.     

Restricted greedy clique decompositions and greedy clique decompositions ofK 4-free graphs

A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. It has recently been shown that any greedy clique decomposition of a graph of ordern has at mostn ²/4 cliques. In this paper, we extend this result by showing that for any positive integerp, 3≤p any clique decomposisitioof a graph of ordern obtained by removing maximal cliques of order at leastp one by one until none remain, in which case the remaining edges are removed one by one, has at mostt _p-1( ⁿ ) cliques. Heret _p-1( ⁿ ) is the number of edges in the Turán graph of ordern, which has no complete subgraphs of orderp. In connection with greedy clique decompositions, P. Winkler conjectured that for any greedy clique decompositionC of a graphG of ordern the sum over the number of vertices in each clique ofC is at mostn ²/2. We prove this conjecture forK ₄-free graphs and show that in the case of equality forC andG there are only two possibilities:

1. G?K _n/2,n/2
2. G is complete 3-partite, where each part hasn/3 vertices.

We show that in either caseC is completely determined.     

When is the radical associated with a module a torsion?

For an arbitrary R-module M we consider the radical (in the sense of Maranda)G _M, namely, the largest radical among all radicalsG, such thatG(M). We determine necessary and sufficient on M in order for the radicalG(M) to be a torsion. In particular,G(M) is a torsion if and only if M is a pseudo-injective module.     

Finite union theorem with restrictions

The aim of this paper is to prove the following extension of the Folkman-Rado-Sanders Finite Union Theorem: For every positive integersr andk there exists a familyL of sets having the following properties:

1. ifS ₁,S ₂, ...,S _{k + 1} are distinct pariwise disjoint elements ofL then there exists nonemptyI ? {1, 2, ...,k + 1} with ∪ _i∈I S _i ?L
2. ifL =L ₁ ?...?L _r is an arbitrary partition then there existsj ≤ r and pairwise disjoint setsS ₁,S ₂, ...,S _k ∈L _j , such thatL _i∈I S _i ∈L _j for every nonemptyI ? {1, 2, ...,k}.

     

Regularity property of Donsker's delta function

LetL be the space of rapidly decreasing smooth functions on ? andL ^* its dual space. Let (L ²)⁺ and (L ²)^? be the spaces of test Brownian functionals and generalized Brownian functionals, respectively, on the white noise spaceL ^* with standard Gaussian measure. The Donsker delta functionδ(B(t)?x) is in (L ²)^? and admits the series representation $$\delta (B(t) - x) = (2\pi t)^{ - 1/2} \exp ( - x^2 /2t)\sum\limits_{n = 0}^\infty {(n!2^n )^{ - 1} H_n (x/\sqrt {2t} )} \times H_n (B(t)/\sqrt {2t} )$$ , whereH _n is the Hermite polynomial of degreen. It is shown that forφ in (L ²)⁺,g _t,φ(x)≡〈δ(B(t)?x), φ〉 is inL and the linear map takingφ intog _t,φ is continuous from (L ²)⁺ intoL. This implies that forf inL ^* is a generalized Brownian functional and admits the series representation $$f(B(t)) = (2\pi t)^{ - 1/2} \sum\limits_{n = 0}^\infty {(n!2^n )^{ - 1} \langle f,\xi _{n, t} \rangle } H_n (B(t)/\sqrt {2t} )$$ , whereξ _n,t is the Hermite function of degreen with parametert. This series representation is used to prove the Ito lemma forf inL ^*, $$f(B(t)) = f(B(u)) + \int_u^t {\partial _s^ * } f'(B(s)) ds + (1/2)\int_u^t {f''} (B(s)) ds$$ , where? _s ^* is the adjoint of \(\dot B(s)\) -differentiation operator? _s .     

An efficient compact quadratic convex reformulation for general integer quadratic programs

We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in Billionnet et al. (Math. Program., 2010) a general solution method based on quadratic convex reformulation, that we called MIQCR. This reformulation consists in designing an equivalent quadratic program with a convex objective function. The problem reformulated by MIQCR has a relatively important size that penalizes its solution time. In this paper, we propose a convex reformulation less general than MIQCR because it is limited to the general integer case, but that has a significantly smaller size. We call this approach Compact Quadratic Convex Reformulation (CQCR). We evaluate CQCR from the computational point of view. We perform our experiments on instances of general integer quadratic programs with one equality constraint. We show that CQCR is much faster than MIQCR and than the general non-linear solver BARON (Sahinidis and Tawarmalani, User??s manual, 2010) to solve these instances. Then, we consider the particular class of binary quadratic programs. We compare MIQCR and CQCR on instances of the Constrained Task Assignment Problem. These experiments show that CQCR can solve instances that MIQCR and other existing methods fail to solve.     

A convergence on Boolean algebras generalizing the convergence on the Aleksandrov cube

We compare the forcing-related properties of a complete Boolean algebra B with the properties of the convergences λ_s (the algebraic convergence) and λ_ls on B generalizing the convergence on the Cantor and Aleksandrov cube, respectively. In particular, we show that λ_ls is a topological convergence iff forcing by B does not produce new reals and that λ_ls is weakly topological if B satisfies condition (?) (implied by the t-cc). On the other hand, if λ_ls is a weakly topological convergence, then B is a 2^h-cc algebra or in some generic extension the distributivity number of the ground model is greater than or equal to the tower number of the extension. So, the statement “The convergence λ_ls on the collapsing algebra \(B = {\text{ro}}{(^{ < \omega }}{\omega _2})\) is weakly topological” is independent of ZFC.