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.     

Singular integrals along Lipschitz curves with holomorphic kernels

If γ(x)=x+iA(x),tan ^?1‖A′‖_∞<ω<π/2,S _ω ⁰ ={z∈C}| |argz|<ω, or, |arg(-z)|<ω} We have proved that if φ is a holomorphic function in S _ω ⁰ and \(\left| {\varphi (z)} \right| \leqslant \frac{C}{{\left| z \right|}}\) , denotingT f (z)= ∫?(z-ζ)f(ζ)dζ, ?f∈C ₀(γ), ?z∈suppf, where C_c(γ) denotes the class of continuous functions with compact supports, then the following two conditions are equivalent:

1. T can be extended to be a bounded operator on L²(γ);
2. there exists a function ?₁ ∈H ^∞(S _ω ⁰ ) such that ?′₁(z)=?(z)+?(-z), ?z∈S _ω ⁰ ?z∈S _w ⁰ .

     

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.     

ParNes: a rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals

In this article, we propose an algorithm, nesta-lasso, for the lasso problem, i.e., an underdetermined linear least-squares problem with a 1-norm constraint on the solution. We prove under the assumption of the restricted isometry property (rip) and a sparsity condition on the solution, that nesta-lasso is guaranteed to be almost always locally linearly convergent. As in the case of the algorithm nesta, proposed by Becker, Bobin, and Candès, we rely on Nesterov’s accelerated proximal gradient method, which takes $O(\sqrt {1/\varepsilon })$ iterations to come within $\varepsilon > 0$ of the optimal value. We introduce a modification to Nesterov’s method that regularly updates the prox-center in a provably optimal manner. The aforementioned linear convergence is in part due to this modification. In the second part of this article, we attempt to solve the basis pursuit denoising (bpdn) problem (i.e., approximating the minimum 1-norm solution to an underdetermined least squares problem) by using nesta-lasso in conjunction with the Pareto root-finding method employed by van den Berg and Friedlander in their spgl1 solver. The resulting algorithm is called parnes. We provide numerical evidence to show that it is comparable to currently available solvers.     

Globally-biased Disimpl algorithm for expensive global optimization

Direct-type global optimization algorithms often spend an excessive number of function evaluations on problems with many local optima exploring suboptimal local minima, thereby delaying discovery of the global minimum. In this paper, a globally-biased simplicial partition Disimpl algorithm for global optimization of expensive Lipschitz continuous functions with an unknown Lipschitz constant is proposed. A scheme for an adaptive balancing of local and global information during the search is introduced, implemented, experimentally investigated, and compared with the well-known Direct and Direct l methods. Extensive numerical experiments executed on 800 multidimensional multiextremal test functions show a promising performance of the new acceleration technique with respect to competitors.     

On spectra ofp-hyponormal operators

The purpose of this paper is to show the following: Let 0<p<1/2. IfT=U|T| is a p-hyponormal operator with a unitaryU on a Hilbert space, then $$\sigma (T) = \mathop \cup \limits_{0 \leqslant k \leqslant 1} \sigma (T_{\left[ k \right]} ),$$ where $$T_{\left[ k \right]} = U[(1 - k)S_U^ - (\left| T \right|^{2p} ) + kS_U^ + (\left| T \right|^{2p} ]^{\tfrac{1}{{2p}}} $$ andS _U ^± (T) denote the polar symbols ofT.     

Resonance-free region in scattering by a strictly convex obstacle

We prove the existence of a resonance-free region in scattering by a strictly convex obstacle \(\mathcal{O}\) with the Robin boundary condition \(\partial_{\nu}u+\gamma u|_{\partial\mathcal{O}}=0\) . More precisely, we show that the scattering resonances lie below a cubic curve ?ζ=?S|ζ|^1/3+C. The constant S is the same as in the case of the Neumann boundary condition γ=0. This generalizes earlier results on cubic pole-free regions obtained for the Dirichlet boundary condition.     

The weighted Grammar constraint

We introduce the WeightedGrammar constraint and propose propagation algorithms based on the CYK parser and the Earley parser. We show that the traces of these algorithms can be encoded as a weighted negation normal form (WNNF), a generalization of NNF that allows nodes to carry weights. Based on this connection, we prove the correctness and complexity of these algorithms. Specifically, these algorithms enforce domain consistency on the WeightedGrammar constraint in time O(n ³). Further, we propose that the WNNF constraint can be decomposed into a set of primitive arithmetic constraint without hindering propagation.     

A mean field model for a class of garbage collection algorithms in flash-based solid state drives

Garbage collection (GC) algorithms play a key role in reducing the write amplification in flash-based solid state drives, where the write amplification affects the lifespan and speed of the drive. This paper introduces a mean field model to assess the write amplification and the distribution of the number of valid pages per block for a class $\mathcal {C}$ of GC algorithms. Apart from the Random GC algorithm, class $\mathcal {C}$ includes two novel GC algorithms: the $d$ -Choices GC algorithm, that selects $d$ blocks uniformly at random and erases the block containing the least number of valid pages among the $d$ selected blocks, and the Random++ GC algorithm, that repeatedly selects another block uniformly at random until it finds a block with a lower than average number of valid blocks. Using simulation experiments, we show that the proposed mean field model is highly accurate in predicting the write amplification (for drives with $N=50{,}000$ blocks). We further show that the $d$ -Choices GC algorithm has a write amplification close to that of the Greedy GC algorithm even for small $d$ values, e.g., $d = 10$ , and offers a more attractive trade-off between its simplicity and its performance than the Windowed GC algorithm introduced and analyzed in earlier studies. The Random++ algorithm is shown to be less effective as it is even inferior to the FIFO algorithm when the number of pages $b$ per block is large (e.g., for $b \ge 64$ ).     

Approximating minimum-cost edge-covers of crossing biset-families

Part of this paper appeared in the preliminary version [16]. An ordered pair ? = (S, S ₊) of subsets of a groundset V is called a biset if S ? S+; (V S ⁺;V S) is the co-biset of ?. Two bisets \(\hat X,\hat Y\) intersect if ^X X ∩ Y ≠ \(\not 0\) and cross if both X ∩ Y \(\not 0\) and X ⁺ ∪ Y ⁺ ≠= V. The intersection and the union of two bisets \(\hat X,\hat Y\) are defined by \(\hat X \cap \hat Y = (X \cap Y,X^ + \cap Y^ + )\) and \(\hat X \cup \hat Y = (X \cup Y,X^ + \cup Y^ + )\) . A biset-family \(\mathcal{F}\) is crossing (intersecting) if \(\hat X \cap \hat Y,\hat X \cup \hat Y \in \mathcal{F}\) for any \(\hat X,\hat Y \in \mathcal{F}\) that cross (intersect). A directed edge covers a biset ? if it goes from S to V S ⁺. We consider the problem of covering a crossing biset-family \(\mathcal{F}\) by a minimum-cost set of directed edges. While for intersecting \(\mathcal{F}\) , a standard primal-dual algorithm computes an optimal solution, the approximability of the case of crossing \(\mathcal{F}\) is not yet understood, as it includes several NP-hard problems, for which a poly-logarithmic approximation was discovered only recently or is not known. Let us say that a biset-family \(\mathcal{F}\) is k-regular if \(\hat X \cap \hat Y,\hat X \cup \hat Y \in \mathcal{F}\) for any \(\hat X,\hat Y \in \mathcal{F}\) with |V (X∪Y)≥k+1 that intersect. In this paper we obtain an O(log |V|)-approximation algorithm for arbitrary crossing \(\mathcal{F}\) if in addition both \(\mathcal{F}\) and the family of co-bisets of \(\mathcal{F}\) are k-regular, our ratios are: \(O\left( {\log \frac{{|V|}} {{|V| - k}}} \right) \) if |S ⁺ \ S| = k for all \(\hat S \in \mathcal{F}\) , and \(O\left( {\frac{{|V|}} {{|V| - k}}\log \frac{{|V|}} {{|V| - k}}} \right) \) if |S ⁺ \ S| = k for all \(\hat S \in \mathcal{F}\) . Using these generic algorithms, we derive for some network design problems the following approximation ratios: \(O\left( {\log k \cdot \log \tfrac{n} {{n - k}}} \right) \) for k-Connected Subgraph, and O(logk) \(\min \{ \tfrac{n} {{n - k}}\log \tfrac{n} {{n - k}},\log k\} \) for Subset k-Connected Subgraph when all edges with positive cost have their endnodes in the subset.     

A variance-based method to rank input variables of the Mesh Adaptive Direct Search algorithm

The Mesh Adaptive Direct Search algorithm (Mads) algorithm is designed for nonsmooth blackbox optimization problems in which the evaluation of the functions defining the problems are expensive to compute. The Mads algorithm is not designed for problems with a large number of variables. The present paper uses a statistical tool based on variance decomposition to rank the relative importance of the variables. This statistical method is then coupled with the Mads algorithm so that the optimization is performed either in the entire space of variables or in subspaces associated with statistically important variables. The resulting algorithm is called Stats-Mads and is tested on bound constrained test problems having up to 500 variables. The numerical results show a significant improvement in the objective function value after a fixed budget of function evaluations.     

A Spanning Tree with High Degree Vertices

Let G be a connected graph, let ${X \subset V(G)}$ and let f be a mapping from X to {2, 3, . . .}. Kaneko and Yoshimoto (Inf Process Lett 73:163–165, 2000) conjectured that if |N _G (S) ? X| ≥ f (S) ? 2|S| + ω _G (S) + 1 for any subset ${S \subset X}$ , then there exists a spanning tree T such that d _T (x) ≥ f (x) for all ${x \in X}$ . In this paper, we show a result with a stronger assumption than this conjecture; if |N _G (S) ? X| ≥ f (S) ? 2|S| + α(S) + 1 for any subset ${S \subset X}$ , then there exists a spanning tree T such that d _T (x) ≥ f (x) for all ${x \in X}$ .     

Directed graphs over topological spaces: Some set theoretical aspects

In this paper we shall consider problems of the following type. SupposeG is some set,U is some family of subsests ofG (e.g.G could be the Euclidean plane andU might be the family of all sets of Lebesgue measure zero), andG is any directed graph overG (i.e. any collection of ordered pairs of members ofG) such that for eachg∈G the set {h:<g,h>∈G} belongs to the familyU. How large a setSυG must there exist with the property that (S×S) ∩G=, i.e. such that it is totally disconnected? In many of the cases we shall consider (including the particular example above), the answer will turn out to be independent of the axioms of set theory and will remain so even after adjoining the negation of the continuum hypothesis.     

An estimate for the sum of Legendre symbols

For the sum S of the Legendre symbols of a polynomial of odd degree n ≥ 3 modulo primes p ≥ 3, Weil’s estimate |S| ≤ (n ? 1) $ \sqrt p $ and Korobov’s estimate $$ \left| S \right| \leqslant (n - 1)\sqrt {p - \frac{{(n - 3)(n - 4)}} {4}} forp \geqslant \frac{{n^2 + 9}} {2} $$ are well known. In this paper, we prove a stronger estimate, namely, $$ \left| S \right| < (n - 1)\sqrt {p - \frac{{(n - 3)(n + 1)}} {4}} $$ .     

Factorization of Lipschitz functions and absolute convergence of Vilenkin-Fourier series

LetG be a Vilenkin group (i.e., an infinite, compact, metrizable, zero-dimensional Abelian group). Our main result is a factorization theorem for functions in the Lipschitz spaces \(\mathfrak{L}\mathfrak{i}\mathfrak{p}\) (α,p; G). As colloraries of this theorem, we obtain (i) an extension of a factorization theorem ofY. Uno; (ii) a convolution formula which says that \(\mathfrak{L}\mathfrak{i}\mathfrak{p} (\alpha , r; G) = \mathfrak{L}\mathfrak{i}\mathfrak{p} (\beta , l; G)*\mathfrak{L}\mathfrak{i}\mathfrak{p} (\alpha - \beta , r; G)\) for 0<β<α<∞ and 1≤r≤∞; and (iii) an analogue, valid for allG, of a classical theorem ofHardy andLittlewood. We also present several results on absolute convergence of Fourier series defined onG, extending a theorem ofC. W. Onneweer and four results ofN. Ja. Vilenkin andA. I. Rubinshtein. The fourVilenkin-Rubinshtein results are analogues of classical theorems due, respectively, toO. Szász, S. B. Bernshtein, A. Zygmund, andG. G. Lorentz.     

Parallel stochastic gradient algorithms for large-scale matrix completion

This paper develops Jellyfish, an algorithm for solving data-processing problems with matrix-valued decision variables regularized to have low rank. Particular examples of problems solvable by Jellyfish include matrix completion problems and least-squares problems regularized by the nuclear norm or $\gamma _2$ -norm. Jellyfish implements a projected incremental gradient method with a biased, random ordering of the increments. This biased ordering allows for a parallel implementation that admits a speed-up nearly proportional to the number of processors. On large-scale matrix completion tasks, Jellyfish is orders of magnitude more efficient than existing codes. For example, on the Netflix Prize data set, prior art computes rating predictions in approximately 4 h, while Jellyfish solves the same problem in under 3 min on a 12 core workstation.     

On oscillatory integral Hilbert transformation with trigonometric polynomial phase

Let $ \mathcal{P}_n $ denote the set of algebraic polynomials of degree n with the real coefficients. Stein and Wpainger [1] proved that $$ \mathop {\sup }\limits_{p( \cdot ) \in \mathcal{P}_n } \left| {p.v.\int_\mathbb{R} {\frac{{e^{ip(x)} }} {x}dx} } \right| \leqslant C_n , $$ where C _n depends only on n. Later A. Carbery, S. Wainger and J. Wright (according to a communication obtained from I. R. Parissis), and Parissis [3] obtained the following sharp order estimate $$ \mathop {\sup }\limits_{p( \cdot ) \in \mathcal{P}_n } \left| {p.v.\int_\mathbb{R} {\frac{{e^{ip(x)} }} {x}dx} } \right| \sim \ln n. $$ . Now let $ \mathcal{T}_n $ denote the set of trigonometric polynomials $$ t(x) = \frac{{a_0 }} {2} + \sum\limits_{k = 1}^n {(a_k coskx + b_k sinkx)} $$ with real coefficients a _k , b _k . The main result of the paper is that $$ \mathop {\sup }\limits_{t( \cdot ) \in \mathcal{T}_n } \left| {p.v.\int_\mathbb{R} {\frac{{e^{it(x)} }} {x}dx} } \right| \leqslant C_n , $$ with an effective bound on C _n . Besides, an analog of a lemma, due to I. M. Vinogradov, is established, concerning the estimate of the measure of the set, where a polynomial is small, via the coefficients of the polynomial.     

On p dependent boundedness of singular integral operators

We study the classical Calderón Zygmund singular integral operator with homogeneous kernel. Suppose that Ω is an integrable function with mean value 0 on S ¹. We study the singular integral operator $$T_\Omega f= {\rm p.v.} \, f * \frac {\Omega (x/|x|)}{|x|^2}.$$ We show that for α > 0 the condition $$\Bigg| \int \limits _{I} \Omega (\theta) \, d\theta \Bigg| \leq C |\log|I||^{-1-\alpha} \quad\quad\quad\quad (0.1)$$ for all intervals |I| < 1 in S ¹ gives L ^p boundedness of T _Ω in the range ${|1/2-1/p| < \frac \alpha {2(\alpha+1)}}$ . This condition is weaker than the conditions from Grafakos and Stefanov (Indiana Univ Math J 47:455–469, 1998) and Fan et al. (Math Inequal Appl 2:73–81, 1999). We also construct an example of an integrable Ω which satisfies (0.1) such that T _Ω is not L ^p bounded for ${|1/2-1/p| > \frac {3\alpha +1}{6(\alpha +1)}}$ .     

Lower bounds on the number of maximal subgroups in a finite group

For a finite group G, let m(G) denote the set of maximal subgroups of G and π(G) denote the set of primes which divide |G|. When G is a cyclic group, an elementary calculation proves that |m(G)| = |π(G)|. In this paper, we prove lower bounds on |m(G)| when G is not cyclic. In general, ${|m(G)| \geq |\pi(G)|+p}$ | m ( G ) | ≥ | π ( G ) | + p , where ${p \in \pi(G)}$ p ∈ π ( G ) is the smallest prime that divides |G|. If G has a noncyclic Sylow subgroup and ${q \in \pi(G)}$ q ∈ π ( G ) is the smallest prime such that ${Q \in {\rm syl}_q(G)}$ Q ∈ syl q ( G ) is noncyclic, then ${|m(G)| \geq |\pi(G)|+q}$ | m ( G ) | ≥ | π ( G ) | + q . Both lower bounds are best possible.