On the Number of Sum-Free Sets

Cameron and Erds have considered the question: how many sum-freesets are contained in the first n integers;they have shown (personalcommunication) that the number of sum-free sets contained withinthe integers {n, n + 1, ..., n} is c.2^n/2. We prove that thenumber of sets contained within {l, 2, ...,n} is o(2ⁿ⁽⁺⁾) forevery > 0.     

Sum-Free Sets and Related Sets

A   of integers is sum-free if . Cameron conjectured that the number of sum-free sets is . As a step towards this conjecture, we prove that the number of sets satisfying

Bounds on Maximal Families of Sets Not Containing Three Sets with A ∩ B ⊂ C, A ⊄ B

Lower and upper estimates are given on the size of a family of subsets of an n-element set containing no three distinct sets satisfying A ∩ B ⊂ C, A ⊄ B. This is a sharpening of an earlier result where the same question was solved under the condition that there are no three distinct sets such that A ∩ B ⊂ C. The second author was supported by the Hungarian National Foundation for Scientific Research grant numbers NK062321, AT048826, the Bulgarian National Science Fund under Grant IO-03/2005 and the projects of the European Community: INTAS 04-77-7171, FIST–MTKD-CT-2004-003006.     

On Trees of Bounded Degree with Maximal Number of Greatest Independent Sets

Given n and d, we describe the structure of trees with the maximal possible number of greatest independent sets in the class of n-vertex trees of vertex degree at most d.We show that the extremal tree is unique for all even n but uniqueness may fail for odd n; moreover, for d = 3 and every odd n ≥ 7, there are exactly ?(n ? 3)/4? + 1 extremal trees. In the paper, the problem of searching for extremal (n, d)-trees is also considered for the 2-caterpillars; i.e., the trees in which every vertex lies at distance at most 2 from some simple path. Given n and d ∈ {3, 4}, we completely reveal all extremal 2-caterpillars on n vertices each of which has degree at most d.     

Spherical Designs and Generalized Sum-Free Sets in Abelian Groups

We extend the concepts of sum-freesets and Sidon-sets of combinatorial number theory with the aimto provide explicit constructions for spherical designs. We calla subset S of the (additive) abelian group G t-free if for all non-negative integers kand l with k+l t, the sum of k(not necessarily distinct) elements of S does notequal the sum of l (not necessarily distinct) elementsof S unless k=l and the two sums containthe same terms. Here we shall give asymptotic bounds for thesize of a largest t-free set in Z _n,and for t 3 discuss how t-freesets in Z _n can be used to constructspherical t-designs.     

Some Bounds for the Number of Components of Real Zero Sets of Sparse Polynomials

We prove that the zero set of a 4-nomial in n variables in the positive orthant has at most three connected components. This bound, which does not depend on the degree of the polynomial, not only improves the best previously known bound (which was 10) but is optimal as well. In the general case we prove that the number of connected components of the zero set of an m-nomial in n variables in the positive orthant is lower than or equal to (n+1)^m-12^{1 + (m - 1)(m - 2)/2}, improving slightly the known bounds. Finally, we show that for generic exponents, the number of non-compact connected components of the zero set of a 5-nomial in three variables in the positive octant is at most 12. This strongly improves the best previously known bound, which was 10,384. All the bounds obtained in this paper continue to hold for real exponents.     

Maximal Equilateral Sets

A subset of a normed space $X$ X is called equilateral if the distance between any two points is the same. Let $m(X)$ m ( X ) be the smallest possible size of an equilateral subset of $X$ X maximal with respect to inclusion. We first observe that Petty’s construction of a $d$ d - $X$ X of any finite dimension $d\ge 4$ d ≥ 4 with $m(X)=4$ m ( X ) = 4 can be generalised to give $m(X\oplus _1\mathbb R )=4$ m ( X ⊕ 1 R ) = 4 for any $X$ X of dimension at least $2$ 2 which has a smooth point on its unit sphere. By a construction involving Hadamard matrices we then show that for any set $\Gamma $ Γ , $m(\ell _p(\Gamma ))$ m ( ? p ( Γ ) ) is finite and bounded above by a function of $p$ p , for all $1\le p<2$ 1 ≤ p < 2 . Also, for all $p\in [1,\infty )$ p ∈ [ 1 , ∞ ) and $d\in \mathbb N $ d ∈ N there exists $c=c(p,d)>1$ c = c ( p , d ) > 1 such that $m(X)\le d+1$ m ( X ) ≤ d + 1 for all $d$ d - $X$ X with Banach–Mazur distance less than $c$ c from $\ell _p^d$ ? p d . Using Brouwer’s fixed-point theorem we show that $m(X)\le d+1$ m ( X ) ≤ d + 1 for all $d$ d - $X$ X with Banach–Mazur distance less than $3/2$ 3 / 2 from $\ell _\infty ^d$ ? ∞ d . A graph-theoretical argument furthermore shows that $m(\ell _\infty ^d)=d+1$ m ( ? ∞ d ) = d + 1 . The above results lead us to conjecture that $m(X)\le 1+\dim X$ m ( X ) ≤ 1 + dim X for all finite-normed spaces $X$ X .     

N-graphs,Modular Sidon and Sum-Free Sets,and Partition Identities

Using a new graphical representation for partitions, the author obtains a family of partition identities associated with partitions into distinct parts of an arithmetic progression, or, more generally, with partitions into distinct parts of a set that is a finite union of arithmetic progressions associated with a modular sum-free Sidon set. Partition identities are also constructed for sets associated with modular sum-free sets.     

Matrix Bounds on the Spectral Condition Number

The purpose of this paper is to obtain some new lower and upper bounds on κ(A)+κ^-1(A), where κ(A) is the spectral condition number of an n×n nonsingular matrix A, and compare these with previously known bounds.     

Maximal and Minimal Semilattices on Ordered Sets

The map which takes an element of an ordered set to its principal ideal is a natural embedding of that ordered set into its powerset, a semilattice. If attention is restricted to all finite intersections of the principal ideals of the original ordered set, then an embedding into a much smaller semilattice is obtained. In this paper the question is answered of when this construction is, in a certain arrow-theoretic sense, minimal. Specifically, a characterisation is given, in terms of ideals and filters, of those ordered sets which admit a so-called minimal embedding into a semilattice. Similarly, a candidate maximal semilattice on an ordered set can be constructed from the principal filters of its elements. A characterisation of those ordered sets that extend to a maximal semilattice is given. Finally, the notion of a free semilattice on an ordered set is given, and it is shown that the candidate maximal semilattice in the embedding-theoretic sense is the free object.     

Different Bounds on the Different Betti Numbers of Semi-Algebraic Sets

   Abstract. A classic result in real algebraic geometry due to Oleinik—Petrovskii, Thom and Milnor, bounds the topological complexity (the sum of the Betti numbers) of basic semi-algebraic sets. This bound is tight as one can construct examples having that many connected components. However, till now no significantly better bounds were known on the individual higher Betti numbers. We prove better bounds on the individual Betti numbers of basic semi-algebraic sets, as well as arrangements of algebraic hypersurfaces. As a corollary we obtain a polynomial bound on the highest Betti numbers of basic semi-algebraic sets defined by quadratic inequalities.     

Different Bounds on the Different Betti Numbers of Semi-Algebraic Sets

Abstract. A classic result in real algebraic geometry due to Oleinik—Petrovskii, Thom and Milnor, bounds the topological complexity (the sum of the Betti numbers) of basic semi-algebraic sets. This bound is tight as one can construct examples having that many connected components. However, till now no significantly better bounds were known on the individual higher Betti numbers. We prove better bounds on the individual Betti numbers of basic semi-algebraic sets, as well as arrangements of algebraic hypersurfaces. As a corollary we obtain a polynomial bound on the highest Betti numbers of basic semi-algebraic sets defined by quadratic inequalities.     

4一致L—超图的最小边数的上界

主要讨论了4一致L—超图的最小边数与最小上色数的关系，给出了上色数为3的4一致L—超图的最小边数的一个上界。     

Bounds on Condition Number of a Matrix

For each vector norm‖x‖, a matirx $A$ has its operator norm $‖A‖=\mathop{\rm min}\limits_{x≠0}\frac{‖Ax‖}{‖x‖}$and a condition number $P(A)=‖A‖‖A^{-1}‖$. Let $U$ be the set of the whole of norms defined on $C^n$. It is shown that for a nonsingular matrix $A\in C^{n\times n}$, there is no finite upper bound of $P(A)$ whch ‖·‖ varies on $U$ if $A\neq \alpha I$; on the other hand, it is shown that$\mathop{\rm inf}\limits_{‖·‖\in U}‖A‖‖A^{-1}‖ =ρ(A)ρ(A^{-1})$ and in which case this infimum can or cannot be attained, where $ρ(A)$ denotes the spectral radius of $A$.     

Bounds on the Distance Two-Domination Number of a Graph

 For a graph G = (V, E), a subset D⊆V(G) is said to be distance two-dominating set in G if for each vertex u∈V−D, there exists a vertex v∈D such that d(u,v)≤2. The minimum cardinality of a distance two-dominating set in G is called a distance two-domination number and is denoted by γ₂(G). In this note we obtain various upper bounds for γ₂(G) and characterize the classes of graphs attaining these bounds. Received: May 31, 1999 Final version received: July 13, 2000     

Bounds on the 2-Rainbow Domination Number of Graphs

A 2-rainbow domination function of a graph G is a function f that assigns to each vertex a set of colors chosen from the set {1, 2}, such that for any ${v\in V(G), f(v)=\emptyset}$ implies ${\bigcup_{u\in N(v)}f(u)=\{1,2\}.}$ The 2-rainbow domination number γ _r2(G) of a graph G is the minimum ${w(f)=\Sigma_{v\in V}|f(v)|}$ over all such functions f. Let G be a connected graph of order |V(G)| = n ≥ 3. We prove that γ _r2(G) ≤ 3n/4 and we characterize the graphs achieving equality. We also prove a lower bound for 2-rainbow domination number of a tree using its domination number. Some other lower and upper bounds of γ _r2(G) in terms of diameter are also given.     

Counting Maximal Antichains and Independent Sets

Answering several questions of Duffus, Frankl and Rödl, we give asymptotics for the logarithms of (i) the number of maximal antichains in the n-dimensional Boolean algebra and (ii) the numbers of maximal independent sets in the covering graph of the n-dimensional hypercube and certain natural subgraphs thereof. The results in (ii) are implied by more general upper bounds on the numbers of maximal independent sets in regular and biregular graphs. We also mention some stronger possibilities involving actual rather than logarithmic asymptotics.     

Sets of Locally Maximal Visibility and Finite Unions of Starshaped Sets

 Let , where is an open connected subset of some linear topological space, such that S contains all triangular regions whose (relative) boundaries lie in S. If some finite subset T of S has locally maximal visibility in S, then . Hence S is a finite union of starshaped sets whose kernels are determined by T. An analogous result holds for S open. Moreover, counterexamples show that neither the requirement on triangular regions nor the restriction to a finite set T can be deleted. (Received 7 September 1998; in revised form 25 October 1999)     

Characterizing Starshaped Sets by Maximal Visibility

Let S be a nonempty set in a real topological linear space L. p S is a point of maximal visibility of S if and only if it admits a neighbourhood N in L such that Sq Sp for every point q S N, where Sx = { s S : x is visible from s via S }. For S being either open and connected or the closure of its connected interior, it is shown that the kernel of S is the set of all maximal visibility points of S. Planar examples reveal that the topological assumptions on S are necessary. This substantially strengthens a recent result of Toranzos and Forte Cunto.     

Remarks on Maximal Operators Over Arbitrary Sets of Directions

Throughout this paper, we shall let be a subset of [0, 1] havingcardinality N. We shall consider to be a set of slopes, andfor any s , we shall let e_s be the unit vector of slope s inR². Then, following [7], we define the maximal operator on R²associated with the set by The history of the bounds obtained on is quite curious. The earliest study of relatedoperators was carried out by Cordoba [2]. He obtained a boundof C(1 + log N) on the L² operator norm of the Kakeya maximaloperator over rectangles of length 1 and eccentricity N. Thisoperator is analogous to with However, for arbitrary sets, the best known result seems to be C(1 + log N). This followsfrom Lemma 5.1 in [1], but a point of view which produces aproof appears already in [8]. However, in this paper, we provethe following.