On the trace of finite sets

For a family $\text{T}$ of subsets of an n-set X we define the trace of it on a subset Y of X by T_$\text{T}$(Y) = {F∩Y:F?$\text{T}$}. We say that (m,n) → (r,s) if for every $\text{T}$ with |$\text{T| ?m}$ we can find a Y?X|Y| = s such that |T_$\text{T}$(Y)| ? r. We give a unified proof for results of Bollobàs, Bondy, and Sauer concerning this arrow function, and we prove a conjecture of Bondy and Lovász saying $\text{(?}\text{n}{}^2\text{4}\text{? + n + 2,n)→ (3,7)}$, which generalizes Turán's theorem on the maximum number of edges in a graph not containing a triangle.     

A sufficient condition for hamiltonian circuits

A theorem is proved that is (in a sense) the best possible improvement on the following theme: If G is an undirected graph on n vertices in which $\text{|Γ(S)| ≥}\text{1}\text{3}\text{(n + | S | + 3)}$ for every non-empty subset S of the vertices of G, then G is Hamiltonian.     

A better decomposition theorem for simply connected m-convex sets

A set S in R^d is said to be m-convex, m ? 2, if and only if for every m points in S, at least one of the line segments determined by these points lies in S. For S a closed m-convex set in R², various decomposition theorems have been obtained to express S as a finite union of convex sets. However, the previous bounds may be lowered further, and we have the following result:In case S is simply connected, then S is a union of σ(m) or fewer convex sets, where $\text{σ(m) = [(m ?}\text{N}\text{)(m ?}\text{3}\text{2}\text{) +}\text{3}\text{2}\text{]}$.Moreover, this result induces an improved decomposition in the general case as well.     

Algebras of subnormal operators

The paper deals with the following: (I) If S is a subnormal operator on $\text{H}$, then $\text{Ol}$(S) = $\text{W}$(S) = Alg Lat S. (II) If L ∈ ($\text{Ol}$(S), σ-wot)¹, then there exist vectors a and b in $\text{H}$ such that L(T) = 〈Ta, b〉 for every T in $\text{Ol}$. (III) In addition to I the map i(T) = T is a homeomorphism from ($\text{Ol}$, σ-wot) onto ($\text{W}$(S), wot). (IV) If S is not a reductive normal operator, then there exists a cyclic invariant subspace for S that has an open set of bounded point evaluations. (This open set can be constructed to be as large as possible.)     

Solution of the Hamiltonian problem for self-complementary graphs

A graph G is said to be highly constricted if there exists a nonempty subset S of vertices such that (i) G ? S has more than |S| components, (ii) S induces the complete graph, and (iii) for every u ∈ S and v ? S, we have d_G(u) > d_G(v), where d_G(u) denotes the degree of u in G. In this paper it is shown that a non-hamiltonian self-complementary graph G of order p is highly constricted, unless p = 4N and G is a particular graph $\text{G}{}^1\text{(4N)}$. It is also proved that if G is a self-complementary graph of order p(≥8) and π its degree sequence, then G is pancyclic if π has a realization with a hamiltonian cycle, and G has a 2-factor if π has a realization with a 2-factor, unless p = 4N and $\text{G = G}{}^1\text{(4N)}$.     

A Euler-Poincaré characteristic for the open set lattices of finite topologies

Let $\text{T}$ be a finite topology. If P and Q are open sets of $\text{T}$ (Q may be the null set) then P is a minimal cover of Q provided Q ? P and there does not exist any open set R of $\text{T}$ such that Q ? R ? P. A subcollection $\text{D}$ of the open sets of $\text{T}$ is termed an i-discrete collection of $\text{T}$ provided $\text{D}$ contains every open O ∈ $\text{T}$ with the property that ? $\text{D}$ ? O ? ? $\text{D}$, $\text{D}$ contains exactly i minimal covers of ? $\text{D}$, and provided ?$\text{D}$ = ?{O | O ∈ $\text{D}$ and O is a minimal cover of ? $\text{D}$}. A single open set is a O-discrete collection. The number of distinct i-discrete collections of $\text{T}$ is denoted by p($\text{T}$, i). If there does not exist any i-discrete collection then p($\text{T}$,i) = 0, and this happens trivially for the case when i is greater than the number of points on which $\text{T}$ is defined. The object of this article is to establish the theorem: For any finite topology $\text{T}$, the quantity E($\text{T}$) = Σ_{i = 0}^∞ (?1)ⁱp($\text{T}$, i) = 1.     

Conjecture of Li and Praeger concerning the isomorphisms of Cayley graphs of A5

LetG be a finite group, andS a subset ofG \ |1| withS =S ^?1. We useX = Cay(G,S) to denote the Cayley graph ofG with respect toS. We callS a Cl-subset ofG, if for any isomorphism Cay(G,S) ≈ Cay(G,T) there is an α∈ Aut(G) such thatS ^α =T. Assume that m is a positive integer.G is called anm-Cl-group if every subsetS ofG withS =S ^?1 and | S | ≤m is Cl. In this paper we prove that the alternating groupA ₅ is a 4-Cl-group, which was a conjecture posed by Li and Praeger.     

On the minimum number of disjoint pairs in a family of finite sets

The following conjecture of Katona is proved. Let X be a finite set of cardinality n, 1 ? m ? 2ⁿ. Then there is a family $\text{F}$, |$\text{F}$| = m, such that F ∈ $\text{F}$, G ? X, | G | > | F | implies G ∈ $\text{F}$ and $\text{F}$ minimizes the number of pairs (F₁, F₂), F₁, F₂ ∈ $\text{F}$ F₁ ∩ F₂ = ? over all families consisting of m subsets of X.     

On the automorphism group of a tree

It is shown that H = Γ(T)_v is normal in G = Γ(T_v) for any tree T and any vertex v, if and only if, for all vertices u in the neighborhood N of v, the set of images of u under G is either contained in N or has precisely the vertex u in common with N and every vertex in the set of images is fixed by H. Further, if S is the smallest normal subgroup of G containing H then $\text{G}\text{S}$ is the direct product of the wreath products of various symmetric groups around groups of order 1 or 2. The degrees of the symmetric groups involved depend on the numbers of isomorphic components of T_v and the structure of such components.     

Random sum-free subsets of abelian groups

We characterize the structure of maximum-size sum-free subsets of a random subset of an abelian group G. In particular, we determine the threshold above which, with high probability as |G| → ∞, each such subset is contained in some maximum-size sum-free subset of G, whenever q divides |G| for some (fixed) prime q with q ≡ 2 (mod 3). Moreover, in the special case G = ?_2n , we determine the sharp threshold for the above property. The proof uses recent ‘transference’ theorems of Conlon and Gowers, together with stability theorems for sum-free sets of abelian groups.     

The binding number of a graph and its Anderson number

The binding number of a graph G, bind(G), is defined; some examples of its calculation are given, and some upper bounds for it are proved. It is then proved that, if bind(G) ≥ c, then G contains at least $\text{|G|}\text{c}\text{(c + 1)}$ disjoint edges if $\text{0 ≤ c ≤}\text{1}\text{2}$, at least $\text{| G |}\text{(3c ? 2)}\text{3c}\text{?}\text{2(c ? 1)}\text{c}$ disjoint edges if $\text{1 ≤ c ≤}\text{4}\text{3}$, a Hamiltonian circuit if $\text{c ≥}\text{3}\text{2}$, and a circuit of length at least $\text{3(| G | ?1)(c ? 1)}\text{c}$ if $\text{1 < c ≤}\text{3}\text{2}$ and G is not one of two specified exceptional graphs. Each of these results is best possible.The Anderson number of a graph is defined. The Anderson numbers of a few very simple graphs are determined; and some rather weak bounds are obtained, and some conjectures made, on the Anderson numbers of graphs in general.     

On subgraph number independence in trees

For finite graphs F and G, let N_F(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If $\text{F}$ and $\text{G}$ are families of graphs, it is natural to ask then whether or not the quantities N_F(G), F∈$\text{F}$, are linearly independent when G is restricted to $\text{G}$. For example, if $\text{F}$ = {K₁, K₂} (where K_n denotes the complete graph on n vertices) and $\text{F}$ is the family of all (finite) trees, then of course N_K1(T) ? N_K2(T) = 1 for all T∈$\text{F}$. Slightly less trivially, if $\text{F}$ = {S_n: n = 1, 2, 3,…} (where S_n denotes the star on n edges) and $\text{G}$ again is the family of all trees, then Σ_n=1^∞(?1)ⁿ⁺¹N_Sn(T)=1 for all T∈$\text{G}$. It is proved that such a linear dependence can never occur if $\text{F}$ is finite, no F∈$\text{F}$ has an isolated point, and $\text{G}$ contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear).     

A fundamental region for Hecke's modular group

Hecke proved analytically that when λ ≥ 2 or when $\text{λ = 2}\text{cos}\text{(}\text{π}\text{q}\text{)}$, q ∈ Z, q ≥ 3, then $\text{B(λ) = {τ:}\text{Im}\text{τ > 0, |}\text{Re}\text{τ| <}\text{λ}\text{2}\text{, |τ| > 1}}$ is a fundamental region for the group G(λ) = 〈S_λ, T〉, where S_λ: τ → τ + λ and $\text{T: τ →}\text{?1}\text{τ}$. He also showed that B(λ) fails to be a fundamental region for all other λ > 0 by proving that G(λ) is not discontinuous. We give an elementary proof of these facts and prove a related result concerning the distribution of G(λ)-equivalent points.     

Maximum number of sum-free colorings in finite abelian groups

An r-coloring of a subset A of a finite abelian group G is called sum-free if it does not induce a monochromatic Schur triple, i.e., a triple of elements a, b, c ∈ A with a + b = c. We investigate κ_r,G, the maximum number of sum-free r-colorings admitted by subsets of G, and our results show a close relationship between κ_r,G and largest sum-free sets of G.Given a sufficiently large abelian group G of type I, i.e., |G| has a prime divisor q with q ≡ 2 (mod 3). For r = 2, 3 we show that a subset A ? G achieves κ_r,G if and only if A is a largest sum-free set of G. For even order G the result extends to r = 4, 5, where the phenomenon persists only if G has a unique largest sum-free set. On the contrary, if the largest sum-free set in G is not unique, then A attains κ_r,G if and only if it is the union of two largest sum-free sets (in case r = 4) and the union of three (“independent”) largest sum-free sets (in case r = 5).Our approach relies on the so called container method and can be extended to larger r in case G is of even order and contains sufficiently many largest sum-free sets.     

The visually distinct configurations of k sets

Two sets of sets, C₀ and C₁, are said to be visually equivalent if there is a 1-1 mapping m from C₀ onto C₁ such that for every S, T?C₀, S ∩ T=0 if and only if m(S)∩ m(T)=0 and S?T if and only if m(S)?m(T). We find estimates for V(k), the number of equivalence classes of this relation on sets of k sets, for finite and infinite k. Our main results are that for finite k, $\text{1}\text{2}\text{k}{}^2\text{-k log k <log V (k)<ak}{}^2\text{+βk+log k}$, where α and β are approximately 0.7255 and 2.5323 respectively, and there is a set N of cardinality $\text{1}\text{2}\text{(k}{}^2\text{+k)}$ such that there are V(k) visually distinct sets of k subsets of N.     

Graphical t-wise balanced designs

A pair (X, $\text{B}$) will be a t-wise balanced design (tBD) of type t?(v, K, λ) if $\text{B}\text{= (B}{}_{\mathrm{i}}\text{: i ? I)}$ is a family of subsets of X, called blocks, such that: (i) $\text{|X| = v ?}\text{N}$, where $\text{N}$ is the set of positive integers; (ii) $\text{1?t?|B}{}_{\mathrm{i}}\text{|?K?}\text{N}$, for every i ? I; and (iii) if T ? X, |T| = t, then there are λ ? $\text{N}$ indices i ? I where T ? B_i. Throughout this paper we make three restrictions on our tBD's: (1) there are no repeated blocks, i.e. $\text{B}$ will be a set of subsets of X; (2) t ? K or there are no blocks of size t; and (3) $\text{P}{}_{\mathrm{k}}\text{(X)?}\text{B}$ or $\text{B}$ does not contain all k-subsets of X for any t<k?v. Note then that X ? $\text{B}$. Also, if we give the parameters of a specific tBD, then we will choose a minimal K.We focus on the $\text{t?((}\text{p}\text{2}\text{), K, λ)}$ designs with the symmetric group S_p as automorphism group, i.e. X will be the set of $\text{v = (}\text{p}\text{2}\text{)}$ labelled edges of the undirected complete graph K_p and if B ? $\text{B}$ then all subgraphs of K_p isomorphic to B are also in $\text{B}$. Call such tBD's ‘graphical tBD's’. We determine all graphical tBD's with λ = 1 or 2 which will include one with parameters 4?(15,{5,7},1).     

An infinite class of generalized room squares

A generalized Room square $\text{G}$ of order n and degree k is an ${}^{\mathrm{n?1}}{}^{\mathrm{k?1}}\text{×}{}^{\mathrm{n?1}}{}^{\mathrm{k?1}}$ array, each cell of which is either empty or contains an unordered k-tuple of a set S, |S| = n, such that each row and each column of the array contains each element of S exactly once and $\text{G}$ contains each unordered k-tuple of S exactly once. Using a class of Steiner systems and a generalized Room square of order 18 and degree 3 constructed by ad hoc methods, an infinite class of degree 3 squares is constructed.     

Applications of the Connes spectrum to C1-dynamical systems,II

We show that for a C¹-dynamical system (A, G, α) with G discrete (abelian) the Connes spectrum Γ(α) is equal to $\text{G}\text{?}$ if and only if every nonzero closed ideal in G × _αA has a nonzero intersection with A. Denote by G_J the closed subgroup of G that leaves fixed the primitive ideal J of A. We show for a general group G that if all isotropy groups G_J are discrete, then GX_αA is simple if and only if A is G-simple and $\text{Γ(}\text{α}\text{) =}\text{G}\text{?}$. This result is applicable not only when G is discrete but also when G?$\text{R}$ or G?$\text{T}$ provided that A is not primitive. Specializing to single automorphisms (i.e., G=$\text{Z}$) we show that if (the transposed of) α acts freely on a dense set of points in $\text{A}\text{?}$, then Λ(α)=$\text{T}$. The converse is only proved when A is of type I.     

Great intersecting families of edges in hereditary hypergraphs

Chvátal stated in 1972 the following conjecture: If $\text{H}$ is a hereditary hypergraph on S and $\text{M}$ ? $\text{H}$ is a family of maximum cardinality of pairwise intersecting members of $\text{H}$, then there exists an x ∈ S such that d_$\text{H}$(x) = |{H ∈ $\text{H}$: x ∈ H}| = |$\text{M}$|. Berge and Schönheim proved that |$\text{M}$|?$\text{1}\text{2}$|$\text{H}$| for every $\text{H}$ and $\text{M}$. Now we prove that if there exists an $\text{M}$ ? $\text{H}$, |$\text{M}$| = $\text{1}\text{2}$|$\text{H}$| then Chvátal's conjecture is true for this $\text{H}$.     

A bound for the number of tournaments with specified scores

Let $\text{T}$(R) denote the set of all tournaments with score vector R = (r₁, r₂,…, r_n). R. A. Brualdi and Li Qiao (“Proceedings of the Silver Jubilee Conference in Combinatorics at Waterloo,” in press) conjectured that if R is strong with r₁ ≤ r₂ ≤ … ≤ r_n, then |$\text{T}$(R)| ≥ 2^n?2 with equality if and only if R = (1, 1, 2,…, n ? 3, n ? 2, n ? 2). In this paper their conjecture is proved, and this result is used to establish a lower bound on the cardinality of $\text{T}$(R) for every R.