Deterministic extractors for affine sources over large fields

An (n,k)-affine source over a finite field is a random variable X = (X ₁,..., X _n ) ∈ , which is uniformly distributed over an (unknown) k-dimensional affine subspace of . We show how to (deterministically) extract practically all the randomness from affine sources, for any field of size larger than n ^c (where c is a large enough constant). Our main results are as follows:

Perfect difference sets constructed from Sidon sets

A set of positive integers is a perfect difference set if every nonzero integer has a unique representation as the difference of two elements of . We construct dense perfect difference sets from dense Sidon sets. As a consequence of this new approach we prove that there exists a perfect difference set such that

On A Hypergraph Turán Problem Of Frankl

Let be the 2k-uniform hypergraph obtained by letting P₁, . . .,P_r be pairwise disjoint sets of size k and taking as edges all sets P_i∪P_j with i ≠ j. This can be thought of as the ‘k-expansion’ of the complete graph K_r: each vertex has been replaced with a set of size k. An example of a hypergraph with vertex set V that does not contain can be obtained by partitioning V = V1 ∪V₂ and taking as edges all sets of size 2k that intersect each of V₁ and V₂ in an odd number of elements. Let denote a hypergraph on n vertices obtained by this construction that has as many edges as possible. For n sufficiently large we prove a conjecture of Frankl, which states that any hypergraph on n vertices that contains no has at most as many edges as . Sidorenko has given an upper bound of for the Tur′an density of for any r, and a construction establishing a matching lower bound when r is of the form 2^p+1. In this paper we also show that when r=2^p+1, any -free hypergraph of density looks approximately like Sidorenko’s construction. On the other hand, when r is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Turán density of to , where c(r) is a constant depending only on r. The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear algebra, the Kruskal–Katona theorem and properties of Krawtchouck polynomials. * Research supported in part by NSF grants DMS-0355497, DMS-0106589, and by an Alfred P. Sloan fellowship.     

Three-dimensional sets with small sumset

We describe the structure of three dimensional sets of lattice points, having a small doubling property. Let be a finite subset of ℤ³ such that dim = 3. If and , then lies on three parallel lines. Moreover, for every three dimensional finite set that lies on three parallel lines, if , then is contained in three arithmetic progressions with the same common difference, having together no more than terms. These best possible results confirm a recent conjecture of Freiman and cannot be sharpened by reducing the quantity υ or by increasing the upper bounds for .     

Addendum To Schrijver's Work On Minimum Permanents

Let denote the set of n×n binary matrices which have each row and column sum equal to k. For 2≤k≤n→∞ we show that is asymptotically equal to (k−1)^k−1k^2−k. This confirms Conjecture 23 in Minc's catalogue of open problems. * Written while the author was employed by the Department of Computer Science at the Australian National University.     

The \bar \partial -Neumann operator and commutators of the Bergman projection and multiplication operators

We prove that compactness of the canonical solution operator to restricted to (0, 1)-forms with holomorphic coefficients is equivalent to compactness of the commutator defined on the whole L _(0,1)²(Ω), where is the multiplication by and is the orthogonal projection of L _(0,1)²(Ω) to the subspace of (0, 1) forms with holomorphic coefficients. Further we derive a formula for the -Neumann operator restricted to (0, 1) forms with holomorphic coefficients expressed by commutators of the Bergman projection and the multiplications operators by z and . Partially supported by the FWF grant P19147-N13.     

Remarks on Thurston’s Construction of Pseudo-Anosov Maps of Riemann Surfaces

It is well known that certain isotopy classes of oseudo-Anosov maos on a Riemann surface S of non-excluded type can be defined through Dehn twists tα and tβ along simple closed geodesics α and β on S,respectively. Let G be the corresponding Fuchsian group acting on the hyperbolic plane H so that H/G≌S.For any point α∈S,define S = S／{α}.In this article, the author gives explicit parabolic elements of G from which he constructs pseudo-Anosov classes on S that can be projected to a given pseudo-Anosov class on S obtained from Thurston＇s construction.     

On $$ \mathcal{C} $$*-sets and decompositions of continuous and ηζ-continuous functions

The main purpose of this paper is to introduce the concepts of *-sets, *-continuous functions and to obtain new decompositions of continuous and ηζ-continuous functions. Moreover, properties of *-sets and some properties of -sets are discussed.      

Derivations of the even part of the odd hamiltonian superalgebra in modular case

In this paper we mainly study the derivations for even part of the finite-dimensional odd Hamiltonian superalgebra HO over a field of prime characteristic. We first give the generating set of the even part g of HO. Then we compute the derivations from g into the even part m of the generalized Witt superalgebra. Finally, we determine the derivation algebra and outer derivation algebra of and the dimension formulas. In particular, the first cohomology groups H^1（g;m） and H^1（g;g） are determined.     

Explicit Bounded-Degree Unique-Neighbor Concentrators

Here we solve an open problem considered by various researchers by presenting the first explicit constructions of an infinite family of bounded-degree ‘unique-neighbor’ concentrators Γ; i.e., there are strictly positive constants α and ε, such that all Γ = (X,Y,E(Γ)) ∈ satisfy the following properties. The output-set Y has cardinality times that of the input-set X, and for each subset S of X with no more than α|X| vertices, there are at least ε|S| vertices in Y that are adjacent in Γ to exactly one vertex in S. Also, the construction of is simple to specify, and each has fewer than edges. We then modify to obtain explicit unique-neighbor concentrators of maximum degree 3. * Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013.     

<Emphasis Type="Italic">K</Emphasis><Subscript>0</Subscript>-group and approximate similarity invariants of strongly irreducible operators

Let H olenote a complex separable Hilbert space and L(H) denote the collection of bounded linear operators on H. An operator T ∈ L(H) is said to be strongly irreducible if T does not commute with any nontrivial idempotent. Herrero and Jiang showed that the norm-closure of the class of all strongly irreducible operators is the class of all operators with connected spectrum. This result can be considered as an approximate inverse of the Riesz decomposition theorem. In the paper, we give a more precise charact...     

Periodic subgroups of projective linear groups in positive characteristic

We classify the maximal irreducible periodic subgroups of PGL(q, ), where is a field of positive characteristic p transcendental over its prime subfield, q = p is prime, and ^× has an element of order q. That is, we construct a list of irreducible subgroups G of GL(q, ) containing the centre ^×1 _q of GL(q, ), such that G/ ^×1 _q is a maximal periodic subgroup of PGL(q, ), and if H is another group of this kind then H is GL(q, )-conjugate to a group in the list. We give criteria for determining when two listed groups are conjugate, and show that a maximal irreducible periodic subgroup of PGL(q, ) is self-normalising.      

Lifts, Discrepancy and Nearly Optimal Spectral Gap*

We present a new explicit construction for expander graphs with nearly optimal spectral gap. The construction is based on a series of 2-lift operations. Let G be a graph on n vertices. A 2-lift of G is a graph H on 2n vertices, with a covering map π :H →G. It is not hard to see that all eigenvalues of G are also eigenvalues of H. In addition, H has n “new” eigenvalues. We conjecture that every d-regular graph has a 2-lift such that all new eigenvalues are in the range (if true, this is tight, e.g. by the Alon–Boppana bound). Here we show that every graph of maximal degree d has a 2-lift such that all “new” eigenvalues are in the range for some constant c. This leads to a deterministic polynomial time algorithm for constructing arbitrarily large d-regular graphs, with second eigenvalue . The proof uses the following lemma (Lemma 3.3): Let A be a real symmetric matrix with zeros on the diagonal. Let d be such that the l₁ norm of each row in A is at most d. Suppose that for every x,y ∈{0,1}ⁿ with ‹x,y›=0. Then the spectral radius of A is O(α(log(d/α)+1)). An interesting consequence of this lemma is a converse to the Expander Mixing Lemma. * This research is supported by the Israeli Ministry of Science and the Israel Science Foundation.     

Darboux points and integrability of homogeneous Hamiltonian systems with three and more degrees of freedom

We consider natural complex Hamiltonian systems with n degrees of freedom given by a Hamiltonian function which is a sum of the standard kinetic energy and a homogeneous polynomial potential V of degree k > 2. The well known Morales-Ramis theorem gives the strongest known necessary conditions for the Liouville integrability of such systems. It states that for each k there exists an explicitly known infinite set ⊂ ℚ such that if the system is integrable, then all eigenvalues of the Hessian matrix V″(d) calculated at a non-zero d ∈ ℂ ⁿ satisfying V′(d) = d, belong to . The aim of this paper is, among others, to sharpen this result. Under certain genericity assumption concerning V we prove the following fact. For each k and n there exists a finite set such that if the system is integrable, then all eigenvalues of the Hessian matrix V″(d) belong to . We give an algorithm which allows to find sets . We applied this results for the case n = k = 3 and we found all integrable potentials satisfying the genericity assumption. Among them several are new and they are integrable in a highly non-trivial way. We found three potentials for which the additional first integrals are of degree 4 and 6 with respect to the momenta.      

Quantization of orbit bundles in \mathfrakg\mathfrakln* (\mathbbC) \mathfrak{g}\mathfrak{l}_n^* (\mathbb{C})

Let G be the complex general linear group and its Lie algebra equipped with a factorizable Lie bialgebra structure; let U_ħ() be the corresponding quantum group. We construct explicit U_ħ()-equivariant quantization of Poisson orbit bundles O _λ → O _μ in *.     

Proof Of A Conjecture Of Erdős On Triangles In Set-Systems

A triangle is a family of three sets A,B,C such that A∩B, B∩C, C∩A are each nonempty, and . Let be a family of r-element subsets of an n-element set, containing no triangle. Our main result implies that for r ≥ 3 and n ≥ 3r/2, we have This settles a longstanding conjecture of Erdős [7], by improving on earlier results of Bermond, Chvátal, Frankl, and Füredi. We also show that equality holds if and only if consists of all r-element subsets containing a fixed element. Analogous results are obtained for nonuniform families.     

Supersaturation For Ramsey-Turán Problems

For an l-graph , the Turán number is the maximum number of edges in an n-vertex l-graph containing no copy of . The limit is known to exist [8]. The Ramsey–Turán density is defined similarly to except that we restrict to only those with independence number o(n). A result of Erdős and Sós [3] states that as long as for every edge E of there is another edge E′of for which |E∩E′|≥2. Therefore a natural question is whether there exists for which . Another variant proposed in [3] requires the stronger condition that every set of vertices of of size at least εn (0<ε<1) has density bounded below by some threshold. By definition, for every . However, even is not known for very many l-graphs when l>2. We prove the existence of a phenomenon similar to supersaturation for Turán problems for hypergraphs. As a consequence, we construct, for each l≥3, infinitely many l-graphs for which . We also prove that the 3-graph with triples 12a, 12b, 12c, 13a, 13b, 13c, 23a, 23b, 23c, abc, satisfies . The existence of a hypergraph satisfying was conjectured by Erdős and Sós [3], proved by Frankl and R?dl [6], and later by Sidorenko [14]. Our short proof is based on different ideas and is simpler than these earlier proofs. * Research supported in part by the National Science Foundation under grants DMS-9970325 and DMS-0400812, and an Alfred P. Sloan Research Fellowship. † Research supported in part by the National Science Foundation under grants DMS-0071261 and DMS-0300529.     

Oscillation theorems for second-order nonlinear neutral delay dynamic equations on time scales

By employing the generalized Riccati transformation technique, we will establish some new oscillation criteria and study the asymptotic behavior of the nonoscillatory solutions of the second-order nonlinear neutral delay dynamic equation

The hardy and bellman operators in spaces connected with H( \mathbb{T} ) and BMO( \mathbb{T} )

Assume that 1 ≤ p < ∞ and a function f ∈ L ^p [0, π] has the Fourier series $ \sum\limits_{n = 1}^\infty {a_n } Assume that 1 ≤ p < ∞ and a function f ∈ L ^p [0, π] has the Fourier series cos nx. According to one result of G.H. Hardy, the series cos nx is the Fourier series for a certain function (f) ∈ L ^p [0, π]. But if 1 < p ≤ ∞ and f ∈ L ^p [0, π], then the series cos nx is the Fourier series for a certain function (f) ∈ L ^p [0, π]. Similar assertions are true for sine series. This allows one to define the Hardy operator on L ^p (), 1 ≤ p < ∞, and to define the Bellman operator on L ^p (), 1 < p ≤ ∞. In this paper we prove that the Bellman operator boundedly acts in VMO(), and the Hardy operator also maps a certain subspace C() onto VMO(). We also prove the invariance of certain classes of functions with given majorants of modules of continuity or best approximations in the spaces H(), L(), VMO() with respect to the Hardy and Bellman operators. Original Russian Text ? S.S. Volosivets and B.I. Golubov, 2008, published in Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2008, No. 5, pp. 4–13.     

The Maximum Size Of Graphs With A Unique<Emphasis Type="Italic">k</Emphasis>- Factor

For suitable positive integers n and k let m(n, k) denote the maximum number of edges in a graph of order n which has a unique k-factor. In 1964, Hetyei and in 1984, Hendry proved for even n and , respectively. Recently, Johann confirmed the following conjectures of Hendry: for and kn even and for n = 2kq, where q is a positive integer. In this paper we prove for and kn even, and we determine m(n, 3).