Splitting Operation and Connectedness in Binary Matroids

In [3], the authors have extended the splitting operation of graphs to binary matroids. In this paper we explore the relationship between the splitting operation and connectedness in binary matroids. We prove that repeated applications of splitting operation on a bridgeless disconnected binary matroid leads to a connected binary matroid. We extend splitting lemma of graphs [1] to binary matroids.     

Noncanonical number systems in the integers

The well-known binary and decimal representations of the integers, and other similar number systems, admit many generalisations. Here, we investigate whether still every integer could have a finite expansion on a given integer base b, when we choose a digit set that does not contain 0. We prove that such digit sets exist and we provide infinitely many examples for every base b with |b|?4, and for b=−2. For the special case b=−2, we give a full characterisation of all valid digit sets.     

Anmerkungen zu einem lemma von hoàng tuy

In [1], [2] HOÀNG TUY gave an approach to the main theorems of the convex analysis and the convex optimization being based on a lemma; he has proved it by means o induction. In [1] the equivalence of the main theorems of convex optimization given in [1], [2] does not use a separation theorem or equivalent statements. In this note the author has proved that the lemma of HOÀNG TUY can be characterized as a special separation theorem and be obtained from a separation theorem of Eidelheit. That means that the lemma is equivalent to the theorem of Hahn-Banach.     

Fractional set systems with few disjoint pairs

Ahlswede (1980) [1] and Frankl (1977) [5] independently found a result about the structure of set systems with few disjoint pairs. Bollobás and Leader (2003) [3] gave an alternate proof by generalizing to fractional set systems and noting that the optimal fractional set systems are {0,1}-valued. In this paper we show that this technique does not extend to t-intersecting families. We find optimal fractional set systems for some infinite classes of parameters, and we point out that they are strictly better than the corresponding {0,1}-valued fractional set systems. We prove some results about the structure of an optimal fractional set system, which we use to produce an algorithm for finding such systems. The run time of the algorithm is polynomial in the size of the ground set.     

Terme constant de fonctions sur un espace symétrique réductif p-adique

We generalize Casselman's pairing to p-adic reductive symmetric spaces and study the asymptotic behaviour of certain generalized coefficients. We also prove an analogue of a lemma due to Langlands which allows us to prove a disjunction result for the Cartan decomposition of the p-adic reductive symmetric spaces.     

New Bounds for Perfect Hashing via Information Theory

A set of sequences of length t from a b-element alphabet is called k-separated if for every k-tuple of the sequences there exists a coordinate in which they all differ. The problem of finding, for fixed t, b, and k, the largest size N(t, b, k) of a k-separated set of sequences is equivalent to finding the minimum size of a (b, k)-family of perfect hash functions for a set of a given size. We shall improve the bounds for N(t, b, k) obtained by Fredman and Komlós [1].Körner [2] has shown that the proof in [1] can be reduced to an application of the sub-additivity of graph entropy [3]. He also pointed out that this sub-additivity yields a method to prove non-existence bounds for graph covering problems. Our new non-existence bound is based on an extension of graph entropy to hypergraphs.     

Representation and duality for Hilbert algebras

In this paper we introduce a special kind of ordered topological spaces, called Hilbert spaces. We prove that the category of Hilbert algebras with semi-homomorphisms is dually equivalent to the category of Hilbert spaces with certain relations. We restrict this result to give a duality for the category of Hilbert algebras with homomorphisms. We apply these results to prove that the lattice of the deductive systems of a Hilbert algebra and the lattice of open subsets of its dual Hilbert space, are isomorphic. We explore how this duality is related to the duality given in [6] for finite Hilbert algebras, and with the topological duality developed in [7] for Tarski algebras.      

A variant of the hypergraph removal lemma

Recent work of Gowers [T. Gowers, A new proof of Szemerédi's theorem, Geom. Funct. Anal. 11 (2001) 465-588] and Nagle, Rödl, Schacht, and Skokan [B. Nagle, V. Rödl, M. Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Regularity lemma for k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Applications of the regularity lemma for uniform hypergraphs, preprint] has established a hypergraph removal lemma, which in turn implies some results of Szemerédi [E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975) 299-345], and Furstenberg and Katznelson [H. Furstenberg, Y. Katznelson, An ergodic Szemerédi theorem for commuting transformations, J. Anal. Math. 34 (1978) 275-291] concerning one-dimensional and multidimensional arithmetic progressions, respectively. In this paper we shall give a self-contained proof of this hypergraph removal lemma. In fact we prove a slight strengthening of the result, which we will use in a subsequent paper [T. Tao, The Gaussian primes contain arbitrarily shaped constellations, preprint] to establish (among other things) infinitely many constellations of a prescribed shape in the Gaussian primes.     

Quantitative relation between noise sensitivity and influences

A Boolean function f: {0,1} ⁿ → {0,1} is said to be noise sensitive if inserting a small random error in its argument makes the value of the function almost unpredictable. Benjamini, Kalai and Schramm [3] showed that if the sum of squares of inuences of f is close to zero then f must be noise sensitive. We show a quantitative version of this result which does not depend on n, and prove that it is tight for certain parameters. Our results hold also for a general product measure µ _p on the discrete cube, as long as log1/p?logn. We note that in [3], a quantitative relation between the sum of squares of the inuences and the noise sensitivity was also shown, but only when the sum of squares is bounded by n ^?c for a constant c. Our results require a generalization of a lemma of Talagrand on the Fourier coefficients of monotone Boolean functions. In order to achieve it, we present a considerably shorter proof of Talagrand’s lemma, which easily generalizes in various directions, including non-monotone functions.     

The edge-diametric theorem in Hamming spaces

The maximum number of edges spanned by a subset of given diameter in a Hamming space with alphabet size at least three is determined. The binary case was solved earlier by Ahlswede and Khachatrian [A diametric theorem for edges, J. Combin. Theory Ser. A 92(1) (2000) 1–16].     

The shadowing chain lemma for singular Hamiltonian systems involving strong forces

We consider a planar autonomous Hamiltonian system :q+?V(q) = 0, where the potential V: ?² \{??}?? ? has a single well of infinite depth at some point ?? and a strict global maximum 0at two distinct points a and b. Under a strong force condition around the singularity ?? we will prove a lemma on the existence and multiplicity of heteroclinic and homoclinic orbits ?? the shadowing chain lemma ?? via minimization of action integrals and using simple geometrical arguments.     

Alth?fer-Sillke不等式的改进（英）

在本文中给出二元向量空间的子集的平均Hamming距离的一个新的下界和上界，这些界对于二元向量空间的线性子空间是紧的，且改进了[2]文的Alth?fer- Sillke不等式，从而部分解决了Ahlswede和Katona在[1]中提出的一个问题.     

Exceptional functions wandering on the sphere and normal families

We extend Carathéodory’s generalization of Montel’s fundamental normality test to “wandering” exceptional functions (i.e., depending on the respective function in the family under consideration), and we give a corresponding result on shared functions. Furthermore, we prove that if we have a family of pairs (a, b) of functions meromorphic in a domain such that a and b uniformly “stay away from each other,” then the families of the functions a resp. b are normal. The proofs are based on a “simultaneous rescaling” version of Zalcman’s lemma.     

Non-homogeneous T1 theorem for bi-parameter singular integrals

We prove a non-homogeneous T1 theorem for certain bi-parameter singular integral operators. Moreover, we discuss the related non-homogeneous Journé's lemma and product BMO theory.     

A new short proof of a theorem of Ahlswede and Khachatrian

Ahlswede and Khachatrian [R. Ahlswede, L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Theory Ser. A 76 (1996) 121-138] proved the following theorem, which answered a question of Frankl and Füredi [P. Frankl, Z. Füredi, Nontrivial intersecting families, J. Combin. Theory Ser. A 41 (1986) 150-153]. Let 2?t+1?k?2t+1 and n?(t+1)(k−t+1). Suppose that F is a family of k-subsets of an n-set, every two of which have at least t common elements. If |_?F∈FF|<t, then , and this is best possible. We give a new, short proof of this result. The proof in [R. Ahlswede, L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Theory Ser. A 76 (1996) 121-138] requires the entire machinery of the proof of the complete intersection theorem, while our proof uses only ordinary compression and an earlier result of Wilson [R.M. Wilson, The exact bound in the Erd?s-Ko-Rado theorem, Combinatorica 4 (1984) 247-257].     

Landauʼs necessary density conditions for the Hankel transform

We will prove an analogue of Landau?s necessary conditions [H.J. Landau, Necessary density conditions for sampling and interpolation of certain entire functions, Acta Math. 117 (1967) 37–52] for spaces of functions whose Hankel transform is supported in a measurable subset S of the positive semi-axis. As a special case, necessary density conditions for the existence of Fourier–Bessel frames are obtained.     

Almost all triangle-free triple systems are tripartite

A triangle in a triple system is a collection of three edges isomorphic to {123,124,345}. A triple system is triangle-free if it contains no three edges forming a triangle. It is tripartite if it has a vertex partition into three parts such that every edge has exactly one point in each part. It is easy to see that every tripartite triple system is triangle-free. We prove that almost all triangle-free triple systems with vertex set [n] are tripartite. Our proof uses the hypergraph regularity lemma of Frankl and R?dl [13], and a stability theorem for triangle-free triple systems due to Keevash and the second author [15].     

The Gaussian primes contain arbitrarily shaped constellations

We show that the Gaussian primesP[i] ? ?[i] contain infinitely constellations of any prescribed shape and orientation. More precisely, we show that given any distinct Gaussian integersv ₀,…,v _k?1, there are infinitely many sets {a+rv ₀,…,rv _k?1}, witha ∈?[i] andr ∈?{0}, all of whose elements are Gaussian primes. The proof is modeled on that in [9] and requires three ingredients. The first is a hypergraph removal lemma of Gowers and Rödl-Skokan or, more precisely, a slight strenghthening of this lemma which can be found in [22]; this hypergraph removal lemma can be thought of as a generalization of the Szemerédi-Furstenberg-Katznelson theorem concerning multidimensional arithmetic progressions. The second ingredient is the transference argument from [9], which allows one to extend this hypergraph removal lemma to a relative version, weighted by a pseudorandom measure. The third ingredient is a Goldston-Yildirim type analysis for the Gaussian integers, similar to that in [9], which yields a pseudorandom measure. which is concentrated on Gaussian “almost primes”.     

The three squares lemma revisited

A recent paper Fan et al. (2006) [10] showed that the occurrence of two squares at the same position in a string, together with the occurrence of a third near by, is possible only in very special circumstances, represented by 14 well-defined cases. Similar results were published in Simpson (2007) [19]. In this paper we begin the process of extending this research in two ways: first, by proving a “two squares” lemma for a case not considered in Fan et al. (2006) [10]; second, by showing that in other cases, when three squares occur, more precise results — a breakdown into highly periodic substrings easily recognized in a left-to-right scan of the string — can be obtained with weaker assumptions. The motivation for this research is, first, to show that the maximum number of runs (maximal periodicities) in a string is at most n; second, and more important, to provide a combinatorial basis for a new generation of algorithms that directly compute repetitions in strings without elaborate preprocessing. Based on extensive computation, we present conjectures that describe the combinatorial behavior in all 14 of the subcases that arise. We then prove the correctness of seven of these conjectures. Along the way we establish a new combinatorial lemma characterizing strings of which two rotations have the same period.