Families intersecting on an interval

We shall be interested in the following Erd?s-Ko-Rado-type question. Fix some set B⊂[n]={1,2,…,n}. How large a subfamily A of the power set P[n] can we find such that the intersection of any two sets in A contains a cyclic translate (modulo n) of B? Chung, Graham, Frankl and Shearer have proved that, in the case where B=[t] is a block of length t, we can do no better than taking A to consist of all supersets of B. We give an alternative proof of this result, which is in a certain sense more ‘direct’.     

THE MAXIMUM NUMBER OF INTERSECTIONS BETWEEN TWO PLANE RECTANGULAR PATHS

We show that the maximum number of intersections between two plane rectangular paths with lengths m and n: 2 ≤ m ≤ n, is 4n 2, if m=4 and n≡1(mod 3); and it is mn 1 otherwise.     

Setwise intersecting families of permutations

A family of permutations A⊂Sn is said to be t-set-intersecting if for any two permutations σ,π∈A, there exists a t-set x whose image is the same under both permutations, i.e. σ(x)=π(x). We prove that if n is sufficiently large depending on t, the maximum-sized t-set-intersecting families of permutations in Sn are cosets of stabilizers of t-sets. The t=2 case of this was conjectured by János Körner. It can be seen as a variant of the Deza-Frankl conjecture, proved in Ellis, Friedgut and Pilpel (2011) [3]. Our proof uses similar techniques to those of Ellis, Friedgut and Pilpel (2011) [3], namely, eigenvalue methods, together with the representation theory of the symmetric group, but the combinatorial part of the proof is harder.     

Listing minimal edge-covers of intersecting families with applications to connectivity problems

Let G=(V,E) be a directed/undirected graph, let s,t∈V, and let F be an intersecting family on V (that is, X∩Y,X∪Y∈F for any intersecting X,Y∈F) so that s∈X and t∉X for every X∈F. An edge set I⊆E is an edge-cover of F if for every X∈F there is an edge in I from X to V−X. We show that minimal edge-covers of F can be listed with polynomial delay, provided that, for any I⊆E the minimal member of the residual family F_I of the sets in F not covered by I can be computed in polynomial time. As an application, we show that minimal undirected Steiner networks, and minimal k-connected and k-outconnected spanning subgraphs of a given directed/undirected graph, can be listed in incremental polynomial time.     

Clique number of Xor products of Kneser graphs

In this article we investigate a problem in graph theory, which has an equivalent reformulation in extremal set theory similar to the problems researched in “A general 2-part Erd?s-Ko-Rado theorem” by Gyula O.H. Katona, who proposed our problem as well. In the graph theoretic form we examine the clique number of the Xor product of two isomorphic $KG(N,k)$ Kneser graphs. Denote this number with $f(k,N)$. We give lower and upper bounds on $f(k,N)$, and we solve the problem up to a constant deviation depending only on k, and find the exact value for $f(2,N)$ if N is large enough. Also we compute that $f(k,k^2)$ is asymptotically equivalent to $k^2$.     

On the measure of intersecting families,uniqueness and stability

Let t≥1 be an integer and let A be a family of subsets of {1,2,…,n} every two of which intersect in at least t elements. Identifying the sets with their characteristic vectors in {0,1} ⁿ we study the maximal measure of such a family under a non uniform product measure. We prove, for a certain range of parameters, that the t-intersecting families of maximal measure are the families of all sets containing t fixed elements, and that the extremal examples are not only unique, but also stable: any t-intersecting family that is close to attaining the maximal measure must in fact be close in structure to a genuine maximum family. This is stated precisely in Theorem 1.6. We deduce some similar results for the more classical case of Erdős-Ko-Rado type theorems where all the sets in the family are restricted to be of a fixed size. See Corollary 1.7. The main technique that we apply is spectral analysis of intersection matrices that encode the relevant combinatorial information concerning intersecting families. An interesting twist is that part of the linear algebra involved is done over certain polynomial rings and not in the traditional setting over the reals. A crucial tool that we use is a recent result of Kindler and Safra [22] concerning Boolean functions whose Fourier transforms are concentrated on small sets. Research supported in part by the Israel Science Foundation, grant no. 0329745.     

The maximum number of Hamiltonian paths in tournaments

Solving an old conjecture of Szele we show that the maximum number of directed Hamiltonian paths in a tournament onn vertices is at mostc · n ^3/2 · n!/2 ^n–1, wherec is a positive constant independent ofn.Research supported in part by a U.S.A.-Israel BSF grant and by a Bergmann Memorial Grant.     

On acyclic edge coloring of planar graphs without intersecting triangles

Let Δ denote the maximum degree of a graph. Fiam?ík first and then Alon et al. again conjectured that every graph is acyclically edge (Δ+2)-colorable. Even for planar graphs, this conjecture remains open. It is known that every triangle-free planar graph is acyclically edge (Δ+5)-colorable. This paper proves that every planar graph without intersecting triangles is acyclically edge (Δ+4)-colorable.     

On the maximum number of distinct factors of a binary string

In this note we prove that a binary string of lengthn can have no more than \(2^{k + 1} - 1 + \left( {\mathop {n - k + 1}\limits_2 } \right)\) distinct factors, wherek is the unique integer such that 2^k + k - 1 ≤ n < 2^k+1 + k. Furthermore, we show that for eachn, this bound is actually achieved. The proof uses properties of the de Bruijn graph.     

On the intersections of circuits and cocircuits in matroids

Seymour has shown that a matroid has a triad, that is, a 3-element set which is the intersection of a circuit and a cocircuit, if and only if it is non-binary. In this paper we determine precisely when a matroidM has a quad, a 4-element set which is the intersection of a circuit and a cocircuit. We also show that this will occur ifM has a circuit and a cocircuit meeting in more than four elements. In addition, we prove that if a 3-connected matroid has a quad, then every pair of elements is in a quad. The corresponding result for triads was proved by Seymour.     

On the maximum number of fixed points in automorphisms of prime order of 2-(v,k,1) designs

In this paper, we study 2-(v, k, 1) designs with automorphisms of prime orderp, having the maximum possible number of fixed points. We prove an upper bound on the number of fixed points, and we study the structure of designs in which this bound is met with equality (such a design is called ap-MFP(v, k)). Several characterizations and asymptotic existence results forp-MFP(v, k) are obtained. For (p, k)=(3,3), (5,5), (2,3) and (3,4), necessary and sufficient conditions onv are obtained for the existence of ap-MFP(v, k). Further, for 3≤k≤5 and for any primep≡1 modk(k−1), we establish necessary and sufficient conditions onv for the existence of ap-MFP(v, k).     

On the number of lines in planar spaces

SupposeS is a planar space withv>4 points and letq be the positive real number such thatv=q ³+q²+q+1. Assuming a weak non-degeneracy condition, we shall show thatS has at least (q²+1)(q²+q+1) lines with equality iffq is a prime power andS=PG(3,q).     

On the number of distinct prime factors of an odd perfect number

It is not known whether or not there exists an odd perfect number. We describe an algorithmic approach for showing that if there is an odd perfect number then it has t distinct prime factors, and we discuss its application towards showing that t9.     

On the minimal number of edges in color-critical graphs

A graphG isk-critical if it has chromatic numberk, but every proper subgraph of it is (k?1)-colorable. This paper is devoted to investigating the following question: for givenk andn, what is the minimal number of edges in ak-critical graph onn vertices, with possibly some additional restrictions imposed? Our main result is that for everyk≥4 andn>k this number is at least $\left( {\frac{{k - 1}}{2} + \frac{{k - 3}}{{2(k^2 - 2k - 1)}}} \right)n$ , thus improving a result of Gallai from 1963. We discuss also the upper bounds on the minimal number of edges ink-critical graphs and provide some constructions of sparsek-critical graphs. A few applications of the results to Ramsey-type problems and problems about random graphs are described.     

On the number of latent subsets of intersecting collections

Given two collections F₁ and F₂ of sets, each member of one intersecting each member of the other, let the collections of latent sets F_i^L, i = 1, 2, be the sets that are contained in members of F_i but that are not themselves members of F_i. If lower case letters indicate the size of the collections we then have

$\text{?}{}_1{}^{\mathrm{L}}\text{?}{}_2{}^{\mathrm{L}}\text{? ?}{}_1\text{?}{}_2$

This result is used to prove that a self-intersecting subfamily F of a simplical complex G having the property that any element of F contains s₁ or s₂ can be no larger than the lesser of the number of elements of G containing s₁ and the number containing s₂. Certain extensions and a related conjecture of Chvátal are described.     

On the maximum multiplicity of an eigenvalue in a matrix whose graph contains exactly one cycle

We consider the general problem of determining the maximum possible multiplicity of an eigenvalue in a Hermitian matrix whose graph contains exactly one cycle. For some cases we express that maximum multiplicity in terms of certain parameters associated with the graph.     

On the geodetic number of median graphs

A set of vertices S in a graph is called geodetic if every vertex of this graph lies on some shortest path between two vertices from S. In this paper, minimum geodetic sets in median graphs are studied with respect to the operation of peripheral expansion. Along the way geodetic sets of median prisms are considered and median graphs that possess a geodetic set of size two are characterized.     

Profile vectors in the lattice of subspaces

The profile vector f(U)∈Rⁿ⁺¹ of a family U of subspaces of an n-dimensional vector space V over GF(q) is a vector of which the ith coordinate is the number of subspaces of dimension i in the family U(i=0,1,…,n). In this paper, we determine the profile polytope of intersecting families (the convex hull of the profile vectors of all intersecting families of subspaces).