共查询到20条相似文献,搜索用时 46 毫秒
1.
The shadow minimization problem for t-intersecting systems of finite sets is considered. Let
be a family of k-subsets of . The -shadow of
is the set of all (k-)-subsets
contained in the members of
. Let
be a t-intersecting family (any two members have at least t elements in common) with
. Given k,t,m the problem is to minimize
(over all choices of
). In this paper we solve this problem when m is big enough. 相似文献
2.
For an l-graph
, the Turán number
is the maximum number of edges in an n-vertex l-graph
containing no copy of
. The limit
is known to exist [8]. The Ramsey–Turán density
is defined similarly to
except that we restrict to only those
with independence number o(n). A result of Erdős and Sós [3] states that
as long as for every edge E of
there is another edge E′of
for which |E∩E′|≥2. Therefore a natural question is whether there exists
for which
.
Another variant
proposed in [3] requires the stronger condition that every set of vertices of
of size at least εn (0<ε<1) has density bounded below by some threshold. By definition,
for every
. However, even
is not known for very many l-graphs
when l>2.
We prove the existence of a phenomenon similar to supersaturation for Turán problems for hypergraphs. As a consequence, we
construct, for each l≥3, infinitely many l-graphs
for which
.
We also prove that the 3-graph
with triples 12a, 12b, 12c, 13a, 13b, 13c, 23a, 23b, 23c, abc, satisfies
. The existence of a hypergraph
satisfying
was conjectured by Erdős and Sós [3], proved by Frankl and R?dl [6], and later by Sidorenko [14]. Our short proof is based
on different ideas and is simpler than these earlier proofs.
* Research supported in part by the National Science Foundation under grants DMS-9970325 and DMS-0400812, and an Alfred P.
Sloan Research Fellowship.
† Research supported in part by the National Science Foundation under grants DMS-0071261 and DMS-0300529. 相似文献
3.
In the late 1950s, B. Segre introduced the fundamental
notion of arcs and complete arcs [48,49]. An arc in a nite
projective plane is a set of points with no three on a line and
it is complete if cannot be extended without violating this
property. Given a projective plane
, determining
, the size of its
smallest complete arc, has been a major open question in finite
geometry for several decades. Assume that
has order
q, it was shown by Lunelli
and Sce [41], more than 40 years ago, that
. Apart from this bound,
practically nothing was known about
, except for the case
is the Galois plane. For
this case, the best upper bound, prior to this paper, was
O(q
3/4)
obtained by Sznyi using the properties of the Galois field
GF(q).In this paper, we prove that
for any projective plane
of order
q, where
c is a universal constant.
Together with Lunelli-Sces lower bound, our result determines
up to a polylogarithmic
factor. Our proof uses a probabilistic method known as the
dynamic random construction or Rödls nibble. The proof also
gives a quick randomized algorithm which produces a small
complete arc with high probability.The key ingredient of our proof is a new concentration
result, which applies for non-Lipschitz functions and is of
independent interest.* Research supported in part by grant RB091G-VU from
UCSD, by NSF grant DMS-0200357 and by an A. Sloan
fellowship.Part of this work was done at AT&T Bell Labs and
Microsoft Research 相似文献
4.
In this paper we prove that if
is a set of
k positive integers and
{A
1,
..., A
m
} is a family of subsets
of an n-element set
satisfying
, for all 1
i <
j m, then
. The case
k = 1 was proven 50 years ago
by Majumdar. 相似文献
5.
Michael Capalbo 《Combinatorica》2005,25(4):379-391
Here we solve an open problem considered by various researchers by presenting the first explicit constructions of an infinite
family
of bounded-degree ‘unique-neighbor’ concentrators Γ; i.e., there are strictly positive constants α and ε, such that all Γ = (X,Y,E(Γ)) ∈
satisfy the following properties. The output-set Y has cardinality
times that of the input-set X, and for each subset S of X with no more than α|X| vertices, there are at least ε|S| vertices in Y that are adjacent in Γ to exactly one vertex in S. Also, the construction of
is simple to specify, and each
has fewer than
edges. We then modify
to obtain explicit unique-neighbor concentrators of maximum degree 3.
* Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013. 相似文献
6.
For suitable positive integers n and k let m(n, k) denote the maximum number of edges in a graph of order n which has a unique k-factor. In 1964, Hetyei and in 1984, Hendry proved
for even n and
, respectively. Recently, Johann confirmed the following conjectures of Hendry:
for
and kn even and
for n = 2kq, where q is a positive integer. In this paper we prove
for
and kn even, and we determine m(n, 3). 相似文献
7.
We show that the hereditary discrepancy of a hypergraph
on n points increases by a factor of at most O(log n) when one adds a new edge to
. 相似文献
8.
We present several partial results, variants, and
consistency results concerning the following (as yet unsolved)
conjecture. If X is a graph
on the ground set V with
then
X has an edge coloring
F with
colors such that if
V is decomposed into
parts then there is one
in which F assumes all
values.Due to some unfortunate misunderstandings, this
paper appeared much later than we expected.* Research partially supported by NSF grants
DMS-9704477 and DMS-0072560. Research partially supported by Hungarian National
Research Grant T 032455. 相似文献
9.
A triangle is a family of three sets A,B,C such that A∩B, B∩C, C∩A are each nonempty, and
. Let
be a family of r-element subsets of an n-element set, containing no triangle. Our main result implies that for r ≥ 3 and n ≥ 3r/2, we have
This settles a longstanding conjecture of Erdős [7], by improving on earlier results of Bermond, Chvátal, Frankl, and Füredi.
We also show that equality holds if and only if
consists of all r-element subsets containing a fixed element.
Analogous results are obtained for nonuniform families. 相似文献
10.
In this paper we show that if X is an s-distance set in
m
and X is on
p concentric spheres then
Moreover if
X is antipodal, then
. 相似文献
11.
12.
Let V be an
rn-dimensional linear
subspace of
. Suppose the smallest
Hamming weight of non-zero vectors in V is d. (In coding-theoretic terminology,
V is a linear code of length
n, rate
r and distance
d.) We settle two extremal
problems on such spaces.First, we prove a (weak form) of a conjecture by Kalai and
Linial and show that the fraction of vectors in
V with weight
d is exponentially small.
Specifically, in the interesting case of a small
r, this fraction does not
exceed
.We also answer a question of Ben-Or and show that if
, then for every
k, at most
vectors of
V have weight
k.Our work draws on a simple connection between extremal
properties of linear subspaces of
and the distribution of
values in short sums of
-characters.* Supported in part by grants from the Israeli
Academy of Sciences and the Binational Science Foundation
Israel-USA. This work was done while the author was a student
in the Hebrew University of Jerusalem, Israel. 相似文献
13.
Abstract
By
we denote the set of all propositional formulas. Let
be the set of all clauses. Define
. In Sec. 2 of this paper we prove that for normal modal logics
, the notions of
-expansions and
-expansions coincide. In Sec. 3, we prove that if I consists of default clauses then the notions of
-expansions for I and
-expansions for I coincide. To this end, we first show, in Sec. 3, that the notion of
-expansions for I is the same as that of
-expansions for I.
The project is supported by NSFC 相似文献
14.
Let
be the 2k-uniform hypergraph obtained by letting P1, . . .,Pr be pairwise disjoint sets of size k and taking as edges all sets Pi∪Pj with i ≠ j. This can be thought of as the ‘k-expansion’ of the complete graph Kr: each vertex has been replaced with a set of size k. An example of a hypergraph with vertex set V that does not contain
can be obtained by partitioning V = V1 ∪V2 and taking as edges all sets of size 2k that intersect each of V1 and V2 in an odd number of elements. Let
denote a hypergraph on n vertices obtained by this construction that has as many edges as possible. For n sufficiently large we prove a conjecture of Frankl, which states that any hypergraph on n vertices that contains no
has at most as many edges as
.
Sidorenko has given an upper bound of
for the Tur′an density of
for any r, and a construction establishing a matching lower bound when r is of the form 2p+1. In this paper we also show that when r=2p+1, any
-free hypergraph of density
looks approximately like Sidorenko’s construction. On the other hand, when r is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Turán density
of
to
, where c(r) is a constant depending only on r.
The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections
in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear
algebra, the Kruskal–Katona theorem and properties of Krawtchouck polynomials.
* Research supported in part by NSF grants DMS-0355497, DMS-0106589, and by an Alfred P. Sloan fellowship. 相似文献
15.
Let n and r be positive integers. Suppose that a family
satisfies F1∩···∩Fr ≠∅ for all F1, . . .,Fr ∈
and
. We prove that there exists ε=ε(r) >0 such that
holds for 1/2≤w≤1/2+ε if r≥13. 相似文献
16.
Matching Polynomials And Duality 总被引:2,自引:0,他引:2
Let G be a simple graph on n vertices. An r-matching in G is a set of r independent edges. The number of r-matchings in G will be denoted by p(G, r). We set p(G, 0) = 1 and define the matching polynomial of G by
and the signless matching polynomial of G by
.It is classical that the matching polynomials of a graph G determine the matching polynomials of its complement
. We make this statement more explicit by proving new duality theorems by the generating function method for set functions. In particular, we show that the matching functions
and
are, up to a sign, real Fourier transforms of each other.Moreover, we generalize Foatas combinatorial proof of the Mehler formula for Hermite polynomials to matching polynomials. This provides a new short proof of the classical fact that all zeros of µ(G, x) are real. The same statement is also proved for a common generalization of the matching polynomial and the rook polynomial. 相似文献
17.
We assume that in a linear space
there is a
non-empty set M of points with the property that every plane
containing a point of M is a projective plane. In
section 3 an example is given that in general
is not a
projective space. But if M can be completed by two
points to a generating set of P, then
is a projective space. 相似文献
18.
In this paper, we first introduce new objects called “translation generalized ovals” and “translation generalized ovoids”,
and make a thorough study of these objects. We then obtain numerous new characterizations of the
of Tits and the classical generalized quadrangle
in even characteristic, including the complete classification of 2-transitive generalized ovals for the even case. Next,
we prove a new strong characterization theorem for the
of Tits. As a corollary, we obtain a purely geometric proof of a theorem of Johnson on semifield flocks.
* The second author is a Postdoctoral Fellow of the Fund for Scientific Research—Flanders (Belgium). 相似文献
19.
For a Sperner family A
2[n] let A
i
denote the family of all i-element sets in A. We sharpen the LYM inequality
by adding to the LHS all possible products of fractions
, with suitable coefficients. A corresponding inequality is established also for the linear lattice and the lattice of subsets of a multiset (with all elements having the same multiplicity).* Research supported by the Sonderforschungsbereich 343 Diskrete Strukturen in der Mathematik, University of Bielefeld. 相似文献
20.
Given two disjoint subsets T
1 and
T
2 of
nodes in an undirected 3-connected graph G = (V, E) with node set
V and arc set
E, where
and
are even numbers, we
show that V can be
partitioned into two sets V
1 and
V
2
such that the graphs induced by V
1 and
V
2 are
both connected and
holds for each
j = 1,2. Such a partition can
be found in
time. Our proof relies
on geometric arguments. We define a new type of convex
embedding of k-connected
graphs into real space R
k-1 and prove that for
k = 3 such an embedding
always exists.
1 A preliminary version
of this paper with title Bisecting Two Subsets in 3-Connected
Graphs appeared in the Proceedings of the 10th Annual
International Symposium on Algorithms and Computation, ISAAC
99, (A. Aggarwal, C. P. Rangan, eds.), Springer LNCS 1741,
425–434, 1999. 相似文献