共查询到20条相似文献,搜索用时 421 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
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. 相似文献
4.
Summary A common strategy in the numerical integration over ann-dimensional hypercube or simplex, is to consider a regular subdivision of the integration domain intom
n
subdomains and to approximate the integral over each subdomain by means of a cubature formula. An asymptotic error expansion whenm is derived in case of an integrand with homogeneous boundary singularities. The error expansion also copes with the use of different cubature formulas for the boundary subdomains and for the interior subdomains. 相似文献
5.
Let Δ(1) be the uniform three direction mesh of the plane whose vertices are integer points of
.Let
(respectively
of degree d=3r (respectively d=3r+1 ) for r odd (respectively even) on the triangulation
, and of degree d=2r (respectively d=2r+1) for r odd (respectively even) on the triangulation
. Using linear combinations of translates of these splines we obtain Lagrange interpolants whose corresponding order of approximation
is optimal.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
6.
M. N. El Tarazi 《BIT Numerical Mathematics》1990,30(3):484-489
The interpolation problem at uniform mesh points of a quadratic splines(x
i)=f
i,i=0, 1,...,N ands(x
0)=f0 is considered. It is known that s–f=O(h
3) and s–f=O(h
2), whereh is the step size, and that these orders cannot be improved. Contrary to recently published results we prove that superconvergence cannot occur for any particular point independent off other than mesh points wheres=f by assumption. Best error bounds for some compound formulae approximatingf
i
andf
i
(3)
are also derived. 相似文献
7.
Let n be a positive integer, let
be complex numbers and let
be a nonsingular n × n complex Toeplitz matrix. We present a superfast algorithm for computing the determinant of T. Superfast means that the arithmetic complexity of our algorithm is
, where N denotes the smallest power of 2 that is larger than or equal to n. We show that det T can be computed from the determinant of a certain coupled Vandermonde matrix. The latter matrix is related to a linearized
rational interpolation problem at roots of unity and we show how its determinant can be calculated by multiplying the pivots
that appear in the superfast interpolation algorithm that we presented in a previous publication.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
8.
For evaluation schemes based on the Lagrangian form of a polynomial with degreen, a rigorous error analysis is performed, taking into account that data, computation and even the nodes of interpolation might be perturbed by round-off. The error norm of the scheme is betweenn
2 andn
2+(3n+7)
n
, where
n
denotes the Lebesgue constant belonging to the nodes. Hence, the error norm is of least possible orderO(n
2) if, for instance, the nodes are chosen to be the Chebyshev points or the Fekete points. 相似文献
9.
A theorem of Lovász asserts that (H)/*(H)r/2 for everyr-partite hypergraphH (where and * denote the covering number and fractional covering number respectively). Here it is shown that the same upper bound is valid for a more general class of hypergraphs: those which admit a partition (V
1, ...,V
k
) of the vertex set and a partitionp
1+...+p
k
ofr such that |eV
i
|p
i
r/2 for every edgee and every 1ik. Moreover, strict inequality holds whenr>2, and in this form the bound is tight. The investigation of the ratio /* is extended to some other classes of hypergraphs, defined by conditions of similar flavour. Upper bounds on this ratio are obtained fork-colourable, stronglyk-colourable and (what we call)k-partitionable hypergraphs.Supported by grant HL28438 at MIPG, University of Pennsylvania, and by the fund for the promotion of research at the Technion.This author's research was supported by the fund for the promotion of research at the Technion. 相似文献
10.
Let X = {1, . . . ,
n}, and let
be a family of subsets
of X. Given the size of
, at least how many pairs
of elements of
must be disjoint? In
this paper we give a lower bound for the number of disjoint
pairs in
. The bound we obtain is
essentially best possible. In particular, we give a new proof of
a result of Frankl and of Ahlswede, that if
satisfies
then
contains at least as
many disjoint pairs as X(r).The situation is rather different if we restrict our
attention to
: then we are asking for
the minimum number of edges spanned by a subset of the Kneser
graph of given size. We make a conjecture on this lower bound,
and disprove a related conjecture of Poljak and Tuza on the
largest bipartite subgraph of the Kneser graph.* Research partially supported by NSF grant
DMS-9971788 相似文献
11.
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. 相似文献
12.
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. 相似文献
13.
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. 相似文献
14.
Charles J. Colbourn 《Annals of Combinatorics》1999,3(1):43-52
Frankl and Füredi [11] established that the largest number of 3-subsets of ann-set, for which no four distinct setsA,B,D satisfyAB=CD, is at most
. Chee, Colbourn, and Ling [6] established that this upper bound is met with few exceptions whenn0, 1 (mod 3). In this paper, it is established that the upper bound is also met with few exceptions whenn2 (mod 3).The research was supported in part by the US Army Research Office under Grant DAAG55-98-1-0272. 相似文献
15.
Summary In order to compute an integralI[f], one needs at least two cubature formulaeQ
j
,j{1, 2}. |Q
1[f]–Q
2[f]| can be used as an error estimate for the less precise cubature formula. In order to reduce the amount of work, one can try to reuse some of the function evaluations needed forQ
1, inQ
2. The easiest way to construct embedded cubature formulae is: start with a high degree formulaQ
1, drop (at least) one knot and calculate the weights such that the new formulaQ
2 is exact for as much monomials as possible. We describe how such embedded formulae with positive weights can be found. The disadvantage of such embedded cubature formulae is that there is in general a large difference in the degree of exactness of the two formulae. In this paper we will explain how the high degree formula can be chosen to obtain an embedded pair of cubature formulae of degrees 2m+1/2m–1. The method works for all regions
n
,n2. We will also show the influence of structure on the cubature formulae. 相似文献
16.
Pierre Verlinden 《Numerical Algorithms》1999,22(2):183-192
Consider a weight
and a rational modification of it
is a polynomial. An algorithm is stabilized for the following problem: “Given the coefficients of the three-term recurrence
equation satisfied by the orthogonal polynomials relative to
, compute the coefficients of the recurrence equation satisfied by the orthogonal polynomials relative to
.”
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
17.
For each positive integerk, we consider the setA
k
of all ordered pairs [a, b] such that in everyk-graph withn vertices andm edges some set of at mostam+bn vertices meets all the edges. We show that eachA
k
withk2 has infinitely many extreme points and conjecture that, for every positive , it has only finitely many extreme points [a, b] witha. With the extreme points ordered by the first coordinate, we identify the last two extreme points of everyA
k
, identify the last three extreme points ofA
3, and describeA
2 completely. A by-product of our arguments is a new algorithmic proof of Turán's theorem. 相似文献
18.
We develop an approach to multivariable cubature based on positivity, extension, and completion properties of moment matrices. We obtain a matrix-based lower bound on the size of a cubature rule of degree 2n + 1; for a planar measure , the bound is based on estimating
where C:=C# [ ] is a positive matrix naturally associated with the moments of . We use this estimate to construct various minimal or near-minimal cubature rules for planar measures. In the case when C = diag(c1,...,cn) (including the case when is planar measure on the unit disk), (C) is at least as large as the number of gaps ck >ck+1. 相似文献
19.
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
. 相似文献
20.
Jeff Kahn 《Combinatorica》1992,12(4):417-423
Letn(k) be the least size of an intersecting family ofk-sets with cover numberk, and let
k
denote any projective plane of orderk–1.Theorem There is a constant A such that ifH is a random set ofm Aklogk lines from
k
then Pr(H<)0(k).Corollary
If there exists a
k
thenn(k)=O(klogk). These statements were conjectured by P. Erds and L. Lovász in 1973.Supported in part by NSF-DMS87-83558 and AFOSR grants 89-0066, 89-0512 and 90-0008 相似文献