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 a minimum degree version of the Kruskal--Katona theorem: given d≥1/4 and a triple system F on n vertices with minimum degree at least d(2n), we obtain asymptotically tight lower bounds for the size of its shadow. Equivalently, for t≥n/2−1, we asymptotically determine the minimum size of a graph on n vertices, in which every vertex is contained in at least (2t) triangles. This can be viewed as a variant of the Rademacher--Turán problem.
In this paper we present a novel approach in extremal set theory which may be viewed as an asymmetric version of Katona's permutation method. We use it to find more Turán numbers of hypergraphs in the Erdős--Ko--Rado range. An (a,b)-path P of length 2k−1 consists of 2k−1 sets of size r=a+b as follows. Take k pairwise disjoint a-element sets A0,A2,…,A2k−2 and other k pairwise disjoint b-element sets B1,B3,…,B2k−1 and order them linearly as A0,B1,A2,B3,A4…. Define the (hyper)edges of P2k−1(a,b) as the sets of the form Ai∪Bi+1 and Bj∪Aj+1. The members of P can be represented as r-element intervals of the ak+bk element underlying set. Our main result is about hypergraphs that are blowups of trees, and implies that for fixed k,a,b, as n→∞ exr(n,P2k−1(a,b))=(k−1)(r−1n)+o(nr−1). This generalizes the Erdős--Gallai theorem for graphs which is the case of a=b=1. We also determine the asymptotics when a+b is even; the remaining cases are still open.
The Erdős-Gallai Theorem states that for k≥2, every graph of average degree more than k−2 contains a k-vertex path. This result is a consequence of a stronger result of Kopylov: if k is odd, k=2t+1≥5, n≥(5t−3)/2, and G is an n-vertex 2-connected graph with at least h(n,k,t):=(2k−t)+t(n−k+t) edges, then G contains a cycle of length at least k unless G=Hn,k,t:=Kn−E(Kn−t). In this paper we prove a stability version of the Erdős-Gallai Theorem: we show that for all n≥3t>3, and k∈{2t+1,2t+2}, every n-vertex 2-connected graph G with e(G)>h(n,k,t−1) either contains a cycle of length at least k or contains a set of t vertices whose removal gives a star forest. In particular, if k=2t+1=7, we show G⊆Hn,k,t. The lower bound e(G)>h(n,k,t−1) in these results is tight and is smaller than Kopylov's bound h(n,k,t) by a term of n−t−O(1).
We give an asymptotic formula for the minimum number of edges contained in triangles in a graph having n vertices and e edges. Our main tool is a generalization of Zykov's symmetrization method that can be applied for several graphs simultaneously.
The following sharpening of Turán's theorem is proved. Let Tn,p denote the complete p--partite graph of order n having the maximum number of edges. If G is an n-vertex Kp+1-free graph with e(Tn,p)−t edges then there exists an (at most) p-chromatic subgraph H0 such that e(H0)≥e(G)−t. Using this result we present a concise, contemporary proof (i.e., one applying Szemerédi's regularity lemma) for the classical stability result of Simonovits.
We consider the following question. Suppose that d≥2 and n are fixed, and that θ1,θ2,…,θn are n specified angles. How many points do we need to place in Rd to realise all of these angles? A simple degrees of freedom argument shows that m points in R2 cannot realise more than 2m−4 general angles. We give a construction to show that this bound is sharp when m≥5. In d dimensions the degrees of freedom argument gives an upper bound of dm−(2d+1)−1 general angles. However, the above result does not generalise to this case; surprisingly, the bound of 2m−4 from two dimensions cannot be improved at all. Indeed, our main result is that there are sets of 2m−3 of angles that cannot be realised by m points in any dimension.
An r-graph is an r-uniform hypergraph tree (or r-tree) if its edges can be ordered as E1,…,Em such that ∀i>1∃α(i)<i such that Ei∩(⋃j=1i−1Ej)⊆Eα(i). The Turán number ex(n,H) of an r-graph H is the largest size of an n-vertex r-graph that does not contain H. A cross-cut of H is a set of vertices in H that contains exactly one vertex of each edge of H. The cross-cut number σ(H) of H is the minimum size of a cross-cut of H. We show that for a large family of r-graphs (largest within a certain scope) that are embeddable in r-trees, ex(n,H)=(σ−1)(r−1n)+o(nr−1) holds, and we establish structural stability of near extremal graphs. From stability, we establish exact results for some subfamilies.
There are many generalizations of the Erdős-Ko-Rado theorem. We give new results (and problems) concerning families of t-intersecting k-element multisets of an n-set and point out connections to coding theory and classical geometry. We establish the conjecture that for n≥t(k−t)+2 such a family can have at most (k−tn+k−t−1) members.
We study the maximum number of hyperedges in a 3-uniform hypergraph on n vertices that does not contain a Berge cycle of a given length ℓ. In particular we prove that the upper bound for C2k+1-free hypergraphs is of the order O(k2n1+1/k), improving the upper bound of Györi and Lemons by a factor of Θ(k2). Similar bounds are shown for linear hypergraphs.
Let q be an odd prime power and let f(r) be the minimum size of the symmetric difference of r lines in the Desarguesian projective plane PG(2,q). We prove some results about the function f(r), in particular showing that there exists a constant C>0 such that f(r)=O(q) for Cq^{3/2}<r<q^2 - Cq^{3/2}.
The cube Q is the usual 8-vertex graph with 12 edges. Here we give a new proof for a theorem of Erdős and Simonovits concerning the Turán number of the cube. Namely, it is shown that e(G) < n^{8/5}+(2n)^{3/2} holds for any n-vertex cube-free graph G. Our aim is to give a self-contained exposition. We also point out the best known results and supply bipartite versions.
This paper is a survey on Extremal Graph Theory, primarily focusing on the case when one of the excluded graphs is bipartite. On one hand we give an introduction to this field and also describe many important results, methods, problems, and constructions.
Let Q(n,c) denote the minimum clique size an n-vertex graph can have if its chromatic number is c. Using Ramsey graphs we give an exact, albeit implicit, formula for the case c is at least (n+3)/2.
A family of sets F (and the corresponding family of 0-1 vectors) is called t-cancellative if for all distict t+2 members A_1,... A_t and B,C from F the union of A_1,..., A_t and B differs from the union of A_1, ..., A_t and C. Let c(n,t) be the size of the largest t-cancellative family on n elements, and let c_k(n,t) denote the largest k-uniform family. We significantly improve the previous upper bounds, e.g., we show c(n,2)< 2^0.322n (for n> n_0). Using an algebraic construction we show that the order of magnitude of c_{2k}(n,2) is n^k for each k (when n goes to infinity).
For a hypergraph G and a positive integer s, let χ_{\ell} (G,s) be the minimum value of l such that G is L-colorable from every list L with |L(v)|=l for each v\in V(G) and |L(u)\cap L(v)|\leq s for all u, v\in e\in E(G). This parameter was studied by Kratochvíl, Tuza and Voigt for various kinds of graphs. Using randomized constructions we find the asymptotics of χ_{\ell} (G,s) for balanced complete multipartite graphs and for complete k-partite k-uniform hypergraphs.
Let f:V→N be a function on the vertex set of the graph G=(V,E). The graph G is {\em f-choosable} if for every collection of lists with list sizes specified by f there is a proper coloring using colors from the lists. The sum choice number, χsc(G), is the minimum of ∑f(v), over all functions f such that G is f-choosable. It is known (Alon 1993, 2000) that if G has average degree d, then the usual choice number χℓ(G) is at least Ω(logd), so they grow simultaneously. In this paper we show that χsc(G)/∣V(G)∣ can be bounded while the minimum degree δmin(G)→∞. Our main tool is to give tight estimates for the sum choice number of the unbalanced complete bipartite graph Ka,q.
We have found the most general extension of the celebrated Sauer, Perles and Shelah, Vapnik and Chervonenkis result from 0-1 sequences to k-ary codes still giving a polynomial bound. Let $\mathcal{C}\subseteq \{0,1,..., k-1}^n$ be a k-ary code of length n. For a subset of coordinates S⊂1,2,...,n the projection of C to S is denoted by C∣S. We say that C (i,j)-{\em shatters} S if C∣S contains all the 2∣S∣ distinct vectors (codewords) with coordinates i and j. Suppose that C does not (i,j)-shatter any coordinate set of size si,j≥1 for every 1≤i<j≤q and let p=∑(si,j−1). Using a natural induction we prove that ∣C∣≤O(np) for any given p as n→∞ and give a construction showing that this exponent is the best possible. Several open problems are mentioned.
A hypergraph is called an r by r grid if it is isomorphic to a pattern of r horizontal and r vertical lines. Three sets form a triangle if they pairwise intersect in three distinct singletons. A hypergraph is linear if every pair of edges meet in at most one vertex. In this paper we construct large linear r-hypergraphs which contain no grids. Moreover, a similar construction gives large linear r-hypergraphs which contain neither grids nor triangles. For r at least 4 our constructions are almost optimal. These investigations are also motivated by coding theory: we get new bounds for optimal superimposed codes and designs.
Given a bipartite graph H and an integer n, let f(n;H) be the smallest integer such that, any set of edge disjoint copies of H on n vertices, can be extended to an H-design on at most n+f(n;H) vertices. We establish tight bounds for the growth of f(n;H) as n→∞. In particular, we prove the conjecture of Füredi and Lehel \cite{FuLe} that f(n;H)=o(n). This settles a long-standing open problem.
For a property Γ and a family of sets $\cF$, let $f(\cF,Γ)$ be the size of the largest subfamily of $\cF$ having property Γ. For a positive integer m, let f(m,Γ) be the minimum of $f(\cF,Γ)$ over all families of size m. A family $\cF$ is said to be Bd-free if it has no subfamily $\cF'=\{F_I: I \subseteq [d]\}$ of 2d distinct sets such that for every I,J⊆[d], both FI∪FJ=FI∪J and FI∩FJ=FI∩J hold. A family $\cF$ is a-union free if F1∪...Fa=Fa+1 whenever F1,..,Fa+1 are distinct sets in $\FF$. We verify a conjecture of Erd\H os and Shelah that f(m,B2-free)=Θ(m2/3). We also obtain lower and upper bounds for f(m,Bd-free) and f(m,a-union free).
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.