共查询到20条相似文献,搜索用时 15 毫秒
1.
Paul A. Russell 《Discrete Mathematics》2009,309(9):2952-2956
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’. 相似文献
2.
LIQIAO XUJUNMING ZHANGZHONGLIANG 《高校应用数学学报(英文版)》1995,10(2):215-222
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. 相似文献
3.
David Ellis 《Journal of Combinatorial Theory, Series A》2012,119(4):825-849
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. 相似文献
4.
Zeev Nutov 《Discrete Applied Mathematics》2009,157(1):112-117
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 FI 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. 相似文献
5.
《Discrete Mathematics》2022,345(7):112886
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 Kneser graphs. Denote this number with . We give lower and upper bounds on , and we solve the problem up to a constant deviation depending only on k, and find the exact value for if N is large enough. Also we compute that is asymptotically equivalent to . 相似文献
6.
Ehud Friedgut 《Combinatorica》2008,28(5):503-528
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}
n
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. 相似文献
7.
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. 相似文献
8.
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. 相似文献
9.
Jeffrey Shallit 《Graphs and Combinatorics》1993,9(2-4):197-200
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 2k + k - 1 ≤ n < 2k+1 + k. Furthermore, we show that for eachn, this bound is actually achieved. The proof uses properties of the de Bruijn graph. 相似文献
10.
James G. Oxley 《Combinatorica》1984,4(2-3):187-195
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. 相似文献
11.
12.
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). 相似文献
13.
Klaus Metsch 《Combinatorica》1995,15(1):105-110
SupposeS is a planar space withv>4 points and letq be the positive real number such thatv=q
3+q2+q+1. Assuming a weak non-degeneracy condition, we shall show thatS has at least (q2+1)(q2+q+1) lines with equality iffq is a prime power andS=PG(3,q). 相似文献
14.
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. 相似文献
15.
Michael Krivelevich 《Combinatorica》1997,17(3):401-426
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. 相似文献
16.
Given two collections F1 and F2 of sets, each member of one intersecting each member of the other, let the collections of latent sets FiL, i = 1, 2, be the sets that are contained in members of Fi but that are not themselves members of Fi. If lower case letters indicate the size of the collections we then have 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 s1 or s2 can be no larger than the lesser of the number of elements of G containing s1 and the number containing s2. Certain extensions and a related conjecture of Chvátal are described. 相似文献
17.
18.
Rosário Fernandes 《Linear algebra and its applications》2007,422(1):1-16
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. 相似文献
19.
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. 相似文献
20.
Dániel Gerbner 《Discrete Mathematics》2009,309(9):2861-2869
The profile vector f(U)∈Rn+1 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). 相似文献