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
We prove the following the generalized Turán type result. A collection T of r sets is an r-triangle if for every T1,T2,…,Tr−1∈T we have ∩i=1r−1Ti=∅, but ∩T∈TT is empty. A family F of sets is r-wise intersecting if for any F1,F2,…,Fr∈F we have ∩i=1rFi=∅ or equivalently if F does not contain any m-triangle for m=2,3,…,r. We prove that if n≥n0(r,k), then the r-wise intersecting family F⊆(k[n]) containing the most number of (r+1)-triangles is isomorphic to {F∈(k[n]):∣F∩[r+1]∣≥r}.
Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study the problem of finding a majority vertex (or show that none exists) if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by m(G). It was shown by Saks and Werman that m(Kn)=n−b(n), where b(n) is the number of 1's in the binary representation of n. In this paper, we initiate the study of the problem for general graphs. The obvious bounds for a connected graph G on n vertices are n−b(n)≤m(G)≤n−1. We show that for any tree T on an even number of vertices we have m(T)=n−1 and that for any tree T on an odd number of vertices, we have n−65≤m(T)≤n−2. Our proof uses results about the weighted version of the problem for Kn, which may be of independent interest. We also exhibit a sequence Gn of graphs with m(Gn)=n−b(n) such that Gn has O(nb(n)) edges and n vertices.
We study covering numbers and local covering numbers with respect to difference graphs and complete bipartite graphs. In particular we show that in every cover of a Young diagram with (k2k) steps with generalized rectangles there is a row or a column in the diagram that is used by at least k+1 rectangles, and prove that this is best-possible. This answers two questions by Kim, Martin, Masa{ř}{\'ı}k, Shull, Smith, Uzzell, and Wang (Europ. J. Comb. 2020), namely: - What is the local complete bipartite cover number of a difference graph? - Is there a sequence of graphs with constant local difference graph cover number and unbounded local complete bipartite cover number? We add to the study of these local covering numbers with a lower bound construction and some examples. Following Kim \emph{et al.}, we use the results on local covering numbers to provide lower and upper bounds for the local dimension of partially ordered sets of height~2. We discuss the local dimension of some posets related to Boolean lattices and show that the poset induced by the first two layers of the Boolean lattice has local dimension (1+o(1))log2log2n. We conclude with some remarks on covering numbers for digraphs and Ferrers dimension.
A widely investigated subject in combinatorial geometry, originated from Erdős, is the following. Given a point set P of cardinality n in the plane, how can we describe the distribution of the determined distances? This has been generalized in many directions. In this paper we propose the following variants. Consider planar arrangements of n lines. Determine the maximum number of triangles of unit area, maximum area or minimum area, determined by these lines. Determine the minimum size of a subset of these n lines so that all triples determine distinct area triangles. We prove that the order of magnitude for the maximum occurrence of unit areas lies between Ω(n2) and O(n9/4). This result is strongly connected to both additive combinatorial results and Szemerédi--Trotter type incidence theorems. Next we show a tight bound for the maximum number of minimum area triangles. Finally we present lower and upper bounds for the maximum area and distinct area problems by combining algebraic, geometric and combinatorial techniques.
We investigate the number of 4-edge paths in graphs with a fixed number of vertices and edges. An asymptotically sharp upper bound is given to this quantity. The extremal construction is the quasi-star or the quasi-clique graph, depending on the edge density. An easy lower bound is also proved. This answer resembles the classic theorem of Ahlswede and Katona about the maximal number of 2-edge paths, and a recent theorem of Kenyon, Radin, Ren and Sadun about k-edge stars.
Upper bounds to the size of a family of subsets of an n-element set that avoids certain configurations are proved. These forbidden configurations can be described by inclusion patterns and some sets having the same size. Our results are closely related to the forbidden subposet problems, where the avoided configurations are described solely by inclusions.
Three intersection theorems are proved. First, we determine the size of the largest set system, where the system of the pairwise unions is l-intersecting. Then we investigate set systems where the union of any s sets intersect the union of any t sets. The maximal size of such a set system is determined exactly if s+t<5, and asymptotically if s+t>4. Finally, we exactly determine the maximal size of a k-uniform set system that has the above described (s,t)-union-intersecting property, for large enough n.
Let Bn be the poset generated by the subsets of [n] with the inclusion as relation and let P be a finite poset. We want to embed P into Bn as many times as possible such that the subsets in different copies are incomparable. The maximum number of such embeddings is asymptotically determined for all finite posets P as M(P)(⌊n/2⌋n), where M(P) denotes the minimal size of the convex hull of a copy of P. We discuss both weak and strong (induced) embeddings.
For a given finite poset P, La(n,P) denotes the largest size of a family F of subsets of [n] not containing P as a weak subposet. We exactly determine La(n,P) for infinitely many P posets. These posets are built from seven base posets using two operations. For arbitrary posets, an upper bound is given for La(n,P) depending on ∣P∣ and the size of the longest chain in P. To prove these theorems we introduce a new method, counting the intersections of F with double chains, rather than chains.
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.