BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let [n]=X1∪X2∪X3 be a partition with ⌊3n⌋≤∣Xi∣≤⌈3n⌉ and define G={G⊂[n]:∣G∩Xi∣≤1,1≤i≤3}. It is easy to check that the trace G∣Y:={G∩Y:G∈G} satisfies ∣G∣Y∣≤12 for all 4-sets Y⊂[n]. For n≥25 it is proven that whenever F⊂2[n] satisfies ∣F∣>∣G∣ then ∣F∣C∣≥13 for some C⊂[n], ∣C∣=4. Several further results of a similar flavor are established as well.
Two families F,G of k-subsets of {1,2,…,n} are called non-trivial cross-intersecting if F∩G=∅ for all F∈F,G∈G and ∩{F:F∈F}=∅=∩{G:G∈G}. In the present paper, we determine the maximum product of the sizes of two non-trivial cross-intersecting families of k-subsets of {1,2,…,n} for n≥4k, k≥8, which is a product version of the classical Hilton-Milner Theorem.
For a family F, let D(F) stand for the family of all sets that can be expressed as F∖G, where F,G∈F. A family F is intersecting if any two sets from the family have non-empty intersection. In this paper, we study the following question: what is the maximum of ∣D(F)∣ for an intersecting family of k-element sets? Frankl conjectured that the maximum is attained when F is the family of all sets containing a fixed element. We show that this holds if n≥50klnk and k≥50. At the same time, we provide a counterexample for n<4k.
In a recent breakthrough, Adiprasito, Avvakumov, and Karasev constructed a triangulation of the n-dimensional real projective space with a subexponential number of vertices. They reduced the problem to finding a small downward closed set-system F covering an n-element ground set which satisfies the following condition: For any two disjoint members A,B∈F, there exist a∈A and b∈B such that either B∪{a}∈F and A∪{b}∖{a}∈F, or A∪{b}∈F and B∪{a}∖{b}∈F. Denoting by f(n) the smallest cardinality of such a family F, they proved that f(n)<2O(nlogn), and they asked for a nontrivial lower bound. It turns out that the construction of Adiprasito et al. is not far from optimal; we show that 2(1.42+o(1))n≤f(n)≤2(1+o(1))2nlogn. We also study a variant of the above problem, where the condition is strengthened by also requiring that for any two disjoint members A,B∈F with ∣A∣>∣B∣, there exists a∈A such that B∪{a}∈F. In this case, we prove that the size of the smallest F satisfying this stronger condition lies between 2Ω(nlogn) and 2O(nloglogn/logn).
Let F,G,H be three graphs on the same n vertices. We consider the maximum of the sum and product of the number of their edges subject to the condition in the title.
In this paper, we show that, given two down-sets (simplicial complexes) there is a matching between them that matches disjoint sets and covers the smaller of the two down-sets. This result generalizes an unpublished result of Berge from circa 1980. The result has nice corollaries for cross-intersecting families and Chvátal's conjecture. More concretely, we show that Chvátal's conjecture is true for intersecting families with covering number 2. A family F⊂2[n] is intersection-union (IU) if for any A,B∈F we have 1≤∣A∩B∣≤n−1. Using the aforementioned result, we derive several exact product- and sum-type results for IU-families.
We introduce the following variant of the VC-dimension. Given S⊆{0,1}n and a positive integer d, we define Ud(S) to be the size of the largest subset I⊆[n] such that the projection of S on every subset of I of size d is the d-dimensional cube. We show that determining the largest cardinality of a set with a given Ud dimension is equivalent to a Turán-type problem related to the total number of cliques in a d-uniform hypergraph. This allows us to beat the Sauer--Shelah lemma for this notion of dimension. We use this to obtain several results on Σ3k-circuits, i.e., depth-3 circuits with top gate OR and bottom fan-in at most k: * Tight relationship between the number of satisfying assignments of a 2-CNF and the dimension of the largest projection accepted by it, thus improving Paturi, Saks, and Zane (Comput. Complex. '00). * Improved Σ33-circuit lower bounds for affine dispersers for sublinear dimension. Moreover, we pose a purely hypergraph-theoretic conjecture under which we get further improvement. * We make progress towards settling the Σ32 complexity of the inner product function and all degree-2 polynomials over F2 in general. The question of determining the Σ33 complexity of IP was recently posed by Golovnev, Kulikov, and Williams (ITCS'21).
Given a family of sets on the plane, we say that the family is intersecting if for any two sets from the family their interiors intersect. In this paper, we study intersecting families of triangles with vertices in a given set of points. In particular, we show that if a set P of n points is in convex position, then the largest intersecting family of triangles with vertices in P contains at most (41+o(1))(3n) triangles.
A family F⊂(k[n]) is U(s,q) of for any F1,…,Fs∈F we have ∣F1∪…∪Fs∣≤q. This notion generalizes the property of a family to be t-intersecting and to have matching number smaller than s. In this paper, we find the maximum ∣F∣ for F that are U(s,q), provided n>C(s,q)k with moderate C(s,q). In particular, we generalize the result of the first author on the Erdős Matching Conjecture and prove a generalization of the Erdős-Ko-Rado theorem, which states that for n>s2k the largest family F⊂(k[n]) with property U(s,s(k−1)+1) is the star and is in particular intersecting. (Conversely, it is easy to see that any intersecting family in (k[n]) is U(s,s(k−1)+1).) We investigate the case k=3 more thoroughly, showing that, unlike in the case of the Erdős Matching Conjecture, in general there may be 3 extremal families.
In this paper, we investigate Erd\H os--Ko--Rado type theorems for families of vectors from {0,±1}n with fixed numbers of +1's and −1's. Scalar product plays the role of intersection size. In particular, we sharpen our earlier result on the largest size of a family of such vectors that avoids the smallest possible scalar product. We also obtain an exact result for the largest size of a family with no negative scalar products.
In this paper, we study the maximum degree in non-empty induced subgraphs of the Kneser graph KG(n,k). One of the main results asserts that, for k>k0 and n>64k2, whenever a non-empty subgraph has m≥k(k−2n−2) vertices, its maximum degree is at least 21(1−nk2)m−(k−2n−2)≥0.49m. This bound is essentially best possible. One of the intermediate steps is to obtain structural results on non-empty subgraphs with small maximum degree.
Since its formulation, Turán's hypergraph problems have been among the most challenging open problems in extremal combinatorics. One of them is the following: given a 3-uniform hypergraph F on n vertices in which any five vertices span at least one edge, prove that ∣F∣≥(1/4−o(1))(3n). The construction showing that this bound would be best possible is simply (3X)∪(3Y) where X and Y evenly partition the vertex set. This construction has the following more general (2p+1,p+1)-property: any set of 2p+1 vertices spans a complete sub-hypergraph on p+1 vertices. One of our main results says that, quite surprisingly, for all p>2 the (2p+1,p+1)-property implies the conjectured lower bound.
For a k-graph F⊂(k[n]), the clique number of F is defined to be the maximum size of a subset Q of [n] with (kQ)⊂F. In the present paper, we determine the maximum number of edges in a k-graph on [n] with matching number at most s and clique number at least q for n≥8k2s and for q≥(s+1)k−l, n≤(s+1)k+s/(3k)−l. Two special cases that q=(s+1)k−2 and k=2 are solved completely.
Let X be an n-element set, where n is even. We refute a conjecture of J. Gordon and Y. Teplitskaya, according to which, for every maximal intersecting family F of 2n-element subsets of X, one can partition X into 2n disjoint pairs in such a way that no matter how we pick one element from each of the first 2n−1 pairs, the set formed by them can always be completed to a member of F by adding an element of the last pair. The above problem is related to classical questions in extremal set theory. For any t≥2, we call a family of sets F⊂2X {\em t-separable} if for any ordered pair of elements (x,y) of X, there exists F∈F such that F∩{x,y}={x}. For a fixed t,2≤t≤5 and n→∞, we establish asymptotically tight estimates for the smallest integer s=s(n,t) such that every family F with ∣F∣≥s is t-separable.
We say that a family F of k-element sets is a {\it j-junta} if there is a set J of size j such that, for any F, its presence in F depends on its intersection with J only. Approximating arbitrary families by j-juntas with small j is a recent powerful technique in extremal set theory. The weak point of all known junta approximation results is that they work in the range n>Ck, where C is an extremely fast growing function of the input parameters, such as the quality of approximation or the number of families we simultaneously approximate. We say that a family F is {\it shifted} if for any F={x1,…,xk}∈F and any G={y1,…,yk} such that yi≤xi, we have G∈F. For many extremal set theory problems, including the Erd\H os Matching Conjecture, or the Complete t-Intersection Theorem, it is sufficient to deal with shifted families only. In this paper, we present very general approximation by juntas results for shifted families with explicit (and essentially linear) dependency on the input parameters. The results are best possible up to some constant factors. Moreover, they give meaningful statements for almost all range of values of n. The proofs are shorter than the proofs of the previous approximation by juntas results and are completely self-contained. As an application of our junta approximation, we give a nearly-linear bound for the multi-family version of the Erd\H os Matching Conjecture. More precisely, we prove the following result. Let n≥12sklog(e2s) and suppose that the families F1,…,Fs⊂(k[n]) do not contain F1∈F1,…,Fs∈Fs such that Fi's are pairwise disjoint. Then mini∣Fi∣≤(kn)−(kn−s+1).
We give a short survey of problems and results on (1) diameter graphs and hypergraphs, and (2) geometric Ramsey theory. We also make some modest contributions to both areas. Extending a well known theorem of Kahn and Kalai which disproved Borsuk's conjecture, we show that for any integer r≥2, there exist ε=ε(r)>0 and d0=d0(r) with the following property. For every d≥d0, there is a finite point set P⊂Rd of diameter 1 such that no matter how we color the elements of P with fewer than (1+ε)d colors, we can always find r points of the same color, any two of which are at distance 1.
Let A⊂Nn be an r-wise s-union family, that is, a family of sequences with n components of non-negative integers such that for any r sequences in A the total sum of the maximum of each component in those sequences is at most s. We determine the maximum size of A and its unique extremal configuration provided (i) n is sufficiently large for fixed r and s, or (ii) n=r+1.
In 1965 Erd\H os conjectured that for all k≥2, s≥1 and n≥k(s+1), an n-vertex k-uniform hypergraph $\F$ with $ν(\F)=s$ cannot have more than \newline max{(ksk+k−1),(kn)−(kn−s)} edges. It took almost fifty years to prove it for triple systems. In 2012 we proved the conjecture for all s and all n≥4(s+1). Then Łuczak and Mieczkowska (2013) proved the conjecture for sufficiently large s and all n. Soon after, Frankl proved it for all s. Here we present a simpler version of that proof which yields Erd\H os's conjecture for s≥33. Our motivation is to lay down foundations for a possible proof in the much harder case k=4, at least for large s.
Let d be a fixed positive integer and let ε>0. It is shown that for every sufficiently large n≥n0(d,ε), the d-dimensional unit cube can be decomposed into exactly n smaller cubes such that the ratio of the side length of the largest cube to the side length of the smallest one is at most 1+ε. Moreover, for every n≥n0, there is a decomposition with the required properties, using cubes of at most d+2 different side lengths. If we drop the condition that the side lengths of the cubes must be roughly equal, it is sufficient to use cubes of two different sizes.
Two families A and B, of k-subsets of an n-set, are {\em cross t-intersecting} if for every choice of subsets A∈A and B∈B we have ∣A∩B∣≥t. We address the following conjectured cross t-intersecting version of the Erd\H os--Ko--Rado Theorem: For all n≥(t+1)(k−t+1) the maximum value of ∣A∣∣B∣ for two cross t-intersecting families A,B⊂(k[n]) is (k−tn−t)2. We verify this for all t≥14 except finitely many n and k for each fixed t. Further, we prove uniqueness and stability results in these cases, showing, for instance, that the families reaching this bound are unique up to isomorphism. We also consider a {\em p-weight} version of the problem, which comes from the product measure on the power set of an n-set.
In this paper we study conditions which guarantee the existence of perfect matchings and perfect fractional matchings in uniform hypergraphs. We reduce this problem to an old conjecture by Erdős on estimating the maximum number of edges in a hypergraph when the (fractional) matching number is given, which we are able to solve in some special cases using probabilistic techniques. Based on these results, we obtain some general theorems on the minimum d-degree ensuring the existence of perfect (fractional) matchings. In particular, we asymptotically determine the minimum vertex degree which guarantees a perfect matching in 4-uniform and 5-uniform hypergraphs. We also discuss an application to a problem of finding an optimal data allocation in a distributed storage system.
The aim of the present paper is to prove that the maximum number of edges in a 3-uniform hypergraph on n vertices and matching number s is max{\binom(3s+2,3), \binom(n,3) - \binom(n-s,3)} for all n,s, n >= 3s+2.
A family F is intersecting if any two members have a nonempty intersection. Erdos, Ko, and Rado showed that |F|\leq {n-1\choose k-1} holds for an intersecting family of k-subsets of [n]:={1,2,3,...,n}, n\geq 2k. For n> 2k the only extremal family consists of all k-subsets containing a fixed element. Here a new proof is presented. It is even shorter than the classical proof of Katona using cyclic permutations, or the one found by Daykin applying the Kruskal-Katona theorem.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.