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 F and H be k-uniform hypergraphs. We say H is F-saturated if H does not contain a subgraph isomorphic to F, but H+e does for any hyperedge e∈E(H). The saturation number of F, denoted satk(n,F), is the minimum number of edges in a F-saturated k-uniform hypergraph H on n vertices. Let C3(3) denote the 3-uniform loose cycle on 3 edges. In this work, we prove that (34+o(1))n≤sat3(n,C3(3))≤23n+O(1). This is the first non-trivial result on the saturation number for a fixed short hypergraph cycle.
We consider two extremal problems for set systems without long Berge cycles. First we give Dirac-type minimum degree conditions that force long Berge cycles. Next we give an upper bound for the number of hyperedges in a hypergraph with bounded circumference. Both results are best possible in infinitely many cases.
A hypergraph H is super-pancyclic if for each A⊆V(H) with ∣A∣≥3, H contains a Berge cycle with base vertex set A. We present two natural necessary conditions for a hypergraph to be super-pancyclic, and show that in several classes of hypergraphs these necessary conditions are also sufficient for this. In particular, they are sufficient for every hypergraph H with δ(H)≥max{∣V(H)∣,4∣E(H)∣+10}. We also consider super-cyclic bipartite graphs: those are (X,Y)-bigraphs G such that for each A⊆X with ∣A∣≥3, G has a cycle CA such that V(CA)∩X=A. Such graphs are incidence graphs of super-pancyclic hypergraphs, and our proofs use the language of such graphs.
DP-coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvořák and Postle. We introduce and study (i,j)-defective DP-colorings of simple graphs. Let gDP(i,j,n) be the minimum number of edges in an n-vertex DP-(i,j)-critical graph. In this paper we determine sharp bound on gDP(i,j,n) for each i≥3 and j≥2i+1 for infinitely many n.
Classical problems in hypergraph coloring theory are to estimate the minimum number of edges, m2(r) (respectively, m2∗(r)), in a non-2-colorable r-uniform (respectively, r-uniform and simple) hypergraph. The best currently known bounds are c⋅r/logr⋅2r⩽m2(r)⩽C⋅r2⋅2randc′⋅r−ε⋅4r⩽m2∗(r)⩽C′⋅r4⋅4r, for any fixed ε>0 and some c, c′, C, C′>0 (where c′ may depend on ε). In this paper we consider the same problems in the context of DP-coloring (also known as correspondence coloring), which is a generalization of list coloring introduced by Dvořák and Postle and related to local conflict coloring studied independently by Fraigniaud, Heinrich, and Kosowski. Let m~2(r) (respectively, m~2∗(r)) denote the minimum number of edges in a non-2-DP-colorable r-uniform (respectively, r-uniform and simple) hypergraph. By definition, m~2(r)⩽m2(r) and m~2∗(r)⩽m2∗(r). While the proof of the bound m2∗(r)=Ω(r−34r) due to Erdős and Lovász also works for m~2∗(r), we show that the trivial lower bound m~2(r)⩾2r−1 is asymptotically tight, i.e., m~2(r)⩽(1+o(1))2r−1. On the other hand, when r⩾2 is even, we prove that the lower bound m~2(r)⩾2r−1 is not sharp, i.e., m~2(r)⩾2r−1+1. Whether this result holds for any odd values of r remains an open problem. Nevertheless, we conjecture that the difference m~2(r)−2r−1 can be arbitrarily large.
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.
In the language of hypergraphs, our main result is a Dirac-type bound: we prove that every 3-connected hypergraph H with δ(H)≥max{∣V(H)∣,4∣E(H)∣+10} has a hamiltonian Berge cycle. This is sharp and refines a conjecture by Jackson from 1981 (in the language of bipartite graphs). Our proofs are in the language of bipartite graphs, since the incidence graph of each hypergraph is bipartite.
An {\em ordered r-graph} is an r-uniform hypergraph whose vertex set is linearly ordered. Given 2≤k≤r, an ordered r-graph H is {\em interval} k-{\em partite} if there exist at least k disjoint intervals in the ordering such that every edge of H has nonempty intersection with each of the intervals and is contained in their union. Our main result implies that for each α>k−1 and d>0, every n-vertex ordered r-graph with dnα edges has for some m≤n an m-vertex interval k-partite subgraph with Ω(dmα) edges. This is an extension to ordered r-graphs of the observation by Erd\H os and Kleitman that every r-graph contains an r-partite subgraph with a constant proportion of the edges. The restriction α>k−1 is sharp. We also present applications of the main result to several extremal problems for ordered hypergraphs.
In this paper, we prove a theorem on tight paths in convex geometric hypergraphs, which is asymptotically sharp in infinitely many cases. Our geometric theorem is a common generalization of early results of Hopf and Pannwitz [12], Sutherland [19], Kupitz and Perles [16] for convex geometric graphs, as well as the classical Erdős-Gallai Theorem [6] for graphs. As a consequence, we obtain the first substantial improvement on the Turán problem for tight paths in uniform hypergraphs.
Let D=(V,A) be a digraph. A vertex set K⊆V is a quasi-kernel of D if K is an independent set in D and for every vertex v∈V∖K, v is at most distance 2 from K. In 1974, Chvátal and Lovász proved that every digraph has a quasi-kernel. P. L. Erdős and L. A. Székely in 1976 conjectured that if every vertex of D has a positive indegree, then D has a quasi-kernel of size at most ∣V∣/2. This conjecture is only confirmed for narrow classes of digraphs, such as semicomplete multipartite, quasi-transitive, or locally demicomplete digraphs. In this note, we state a similar conjecture for all digraphs, show that the two conjectures are equivalent, and prove that both conjectures hold for a class of digraphs containing all orientations of 4-colorable graphs (in particular, of all planar graphs).
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).
A collection of sets is {\em intersecting} if every two members have nonempty intersection. We describe the structure of intersecting families of r-sets of an n-set whose size is quite a bit smaller than the maximum (r−1n−1) given by the Erd\H os-Ko-Rado Theorem. In particular, this extends the Hilton-Milner theorem on nontrivial intersecting families and answers a recent question of Han and Kohayakawa for large n. In the case r=3 we describe the structure of all intersecting families with more than 10 edges. We also prove a stability result for the Erdos matching problem. Our short proofs are simple applications of the Delta-system method introduced and extensively used by Frankl since 1977.
We consider the following generalization of graph packing. Let G1=(V1,E1) and G2=(V2,E2) be graphs of order n and G3=(V1∪V2,E3) a bipartite graph. A bijection f from V1 onto V2 is a list packing of the triple (G1,G2,G3) if uv∈E2 implies f(u)f(v)∈/E2 and vf(v)∈/E3 for all v∈V1. We extend the classical results of Sauer and Spencer and Bollobás and Eldridge on packing of graphs with small sizes or maximum degrees to the setting of list packing. In particular, we extend the well-known Bollobás--Eldridge Theorem, proving that if Δ(G1)≤n−2,Δ(G2)≤n−2,Δ(G3)≤n−1, and ∣E1∣+∣E2∣+∣E3∣≤2n−3, then either (G1,G2,G3) packs or is one of 7 possible exceptions. Hopefully, the concept of list packing will help to solve some problems on ordinary graph packing, as the concept of list coloring did for ordinary coloring.
An r-augmented tree is a rooted tree plus r edges added from each leaf to ancestors. For d,g,r∈N, we construct a bipartite r-augmented complete d-ary tree having girth at least g. The height of such trees must grow extremely rapidly in terms of the girth. Using the resulting graphs, we construct sparse non-k-choosable bipartite graphs, showing that maximum average degree at most 2(k−1) is a sharp sufficient condition for k-choosability in bipartite graphs, even when requiring large girth. We also give a new simple construction of non-k-colorable graphs and hypergraphs with any girth g.
Two graphs G1=(V1,E1) and G2=(V2,E2), each of order n, pack if there exists a bijection f from V1 onto V2 such that uv∈E1 implies f(u)f(v)∈/E2. In 2014, Żak proved that if Δ(G1),Δ(G2)≤n−2 and ∣E1∣+∣E2∣+max{Δ(G1),Δ(G2)}≤3n−96n3/4−65, then G1 and G2 pack. In the same paper, he conjectured that if Δ(G1),Δ(G2)≤n−2, then ∣E1∣+∣E2∣+max{Δ(G1),Δ(G2)}≤3n−7 is sufficient for G1 and G2 to pack. We prove that, up to an additive constant, Żak's conjecture is correct. Namely, there is a constant C such that if Δ(G1),Δ(G2)≤n−2 and ∣E1∣+∣E2∣+max{Δ(G1),Δ(G2)}≤3n−C, then G1 and G2 pack. In order to facilitate induction, we prove a stronger result on list packing.
More than twenty years ago Erdős conjectured~\cite{E1} that a triangle-free graph G of chromatic number k≥k0(ε) contains cycles of at least k2−ε different lengths as k→∞. In this paper, we prove the stronger fact that every triangle-free graph G of chromatic number k≥k0(ε) contains cycles of (641−ε)k2logk consecutive lengths, and a cycle of length at least (41−ε)k2logk. As there exist triangle-free graphs of chromatic number k with at most roughly 4k2logk vertices for large k, theses results are tight up to a constant factor. We also give new lower bounds on the circumference and the number of different cycle lengths for k-chromatic graphs in other monotone classes, in particular, for Kr-free graphs and graphs without odd cycles C2s+1.
The expansion G+ of a graph G is the 3-uniform hypergraph obtained from G by enlarging each edge of G with a vertex disjoint from V(G) such that distinct edges are enlarged by distinct vertices. Let exr(n,F) denote the maximum number of edges in an r-uniform hypergraph with n vertices not containing any copy of F. The authors \cite{KMV} recently determined ex3(n,G+) more generally, namely when G is a path or cycle, thus settling conjectures of Füredi-Jiang \cite{FJ} (for cycles) and Füredi-Jiang-Seiver \cite{FJS} (for paths). Here we continue this project by determining the asymptotics for ex3(n,G+) when G is any fixed forest. This settles a conjecture of Füredi \cite{Furedi}. Using our methods, we also show that for any graph G, either ex3(n,G+)≤(21+o(1))n2 or ex3(n,G+)≥(1+o(1))n2, thereby exhibiting a jump for the Turán number of expansions.
The expansion G+ of a graph G is the 3-uniform hypergraph obtained from G by enlarging each edge of G with a new vertex disjoint from V(G) such that distinct edges are enlarged by distinct vertices. Let ex3(n,F) denote the maximum number of edges in a 3-uniform hypergraph with n vertices not containing any copy of a 3-uniform hypergraph F. The study of ex3(n,G+) includes some well-researched problems, including the case that F consists of k disjoint edges, G is a triangle, G is a path or cycle, and G is a tree. In this paper we initiate a broader study of the behavior of ex3(n,G+). Specifically, we show ex3(n,Ks,t+)=Θ(n3−3/s) whenever t>(s−1)! and s≥3. One of the main open problems is to determine for which graphs G the quantity ex3(n,G+) is quadratic in n. We show that this occurs when G is any bipartite graph with Turán number o(nφ) where φ=21+5, and in particular, this shows ex3(n,Q+)=Θ(n2) where Q is the three-dimensional cube graph.
A k-path is a hypergraph P_k = e_1,e_2,...,e_k such that |e_i \cap e_j| = 1 if |j - i| = 1 and e_i \cap e_j is empty otherwise. A k-cycle is a hypergraph C_k = e_1,e_2,.. ,e_k obtained from a (k-1)-path e_1,e_2,...,e_{k-1} by adding an edge e_k that shares one vertex with e_1, another vertex with e_{k-1} and is disjoint from the other edges. Let ex_r(n,G) be the maximum number of edges in an r-graph with n vertices not containing a given r-graph G. We determine ex_r(n, P_k) and ex_r(n, C_k) exactly for all k \ge 4 and r \ge 3 and n sufficiently large and also characterize the extremal examples. The case k = 3 was settled by Frankl and Füredi. This work is the next step in a long line of research beginning with conjectures of Erd\H os and Sós from the early 1970's. In particular, we extend the work (and settle a recent conjecture) of Füredi, Jiang and Seiver who solved this problem for P_k when r \ge 4 and of Füredi and Jiang who solved it for C_k when r \ge 5. They used the delta system method, while we use a novel approach which involves random sampling from the shadow of an r-graph.
A harmonious coloring of G is a proper vertex coloring of G such that every pair of colors appears on at most one pair of adjacent vertices. The harmonious chromatic number of G, h(G), is the minimum number of colors needed for a harmonious coloring of G. We show that if T is a forest of order n with maximum degree Δ(T)≥3n+2, then $$h(T)= Δ(T)+2, & if $T$ has non-adjacent vertices of degree $Δ(T)$; Δ(T)+1, & otherwise. $$ Moreover, the proof yields a polynomial-time algorithm for an optimal harmonious coloring of such a forest.
A \textit{rainbow subgraph} of an edge-colored graph is a subgraph whose edges have distinct colors. The \textit{color degree} of a vertex v is the number of different colors on edges incident to v. We show that if n is large enough (namely, n≥4.25k2), then each n-vertex graph G with minimum color degree at least k contains a rainbow matching of size at least k.
A graph G is k-{\em critical} if it has chromatic number k, but every proper subgraph of G is (k−1)--colorable. Let fk(n) denote the minimum number of edges in an n-vertex k-critical graph. In a very recent paper, we gave a lower bound, fk(n)≥F(k,n), that is sharp for every n=1(modk−1). It is also sharp for k=4 and every n≥6. In this note, we present a simple proof of the bound for k=4. It implies the case k=4 of the conjecture by Ore from 1967 that for every k≥4 and n≥k+2, fk(n+k−1)=f(n)+2k−1(k−k−12). We also show that our result implies a simple short proof of the Gr\" otzsch Theorem that every triangle-free planar graph is 3-colorable.
A graph G is k-critical if it has chromatic number k, but every proper subgraph of G is (k−1)--colorable. Let fk(n) denote the minimum number of edges in an n-vertex k-critical graph. We give a lower bound, fk(n)≥F(k,n), that is sharp for every n=1(modk−1). It is also sharp for k=4 and every n≥6. The result improves the classical bounds by Gallai and Dirac and subsequent bounds by Krivelevich and Kostochka and Stiebitz. It establishes the asymptotics of fk(n) for every fixed k. It also proves that the conjecture by Ore from 1967 that for every k≥4 and n≥k+2, fk(n+k−1)=f(n)+2k−1(k−k−12) holds for each k≥4 for all but at most k3/12 values of n. We give a polynomial-time algorithm for (k−1)-coloring a graph G that satisfies ∣E(G[W])∣<Fk(∣W∣) for all W⊆V(G), ∣W∣≥k. We also present some applications of the result.
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.
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.