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 that if G is a k-partite graph on n vertices in which all of the parts have order at most n/r and every vertex is adjacent to at least a 1−1/r+o(1) proportion of the vertices in every other part, then G contains the (r−1)-st power of a Hamiltonian cycle
A digraph is {\em d-dominating} if every set of at most d vertices has a common out-neighbor. For all integers d≥2, let f(d) be the smallest integer such that the vertices of every 2-edge-colored (finite or infinite) complete digraph (including loops) can be covered by the vertices of at most f(d) monochromatic d-dominating subgraphs. Note that the existence of f(d) is not obvious -- indeed, the question which motivated this paper was simply to determine whether f(d) is bounded, even for d=2. We answer this question affirmatively for all d≥2, proving 4≤f(2)≤8 and 2d≤f(d)≤2d(d−1dd−1) for all d≥3. We also give an example to show that there is no analogous bound for more than two colors. Our result provides a positive answer to a question regarding an infinite analogue of the Burr-Erdős conjecture on the Ramsey numbers of d-degenerate graphs. Moreover, a special case of our result is related to properties of d-paradoxical tournaments.
For all positive integers r≥3 and n such that r2−r divides n and an affine plane of order r exists, we construct an r-edge colored graph with minimum degree (1−r2−rr−2)n−2 such that the largest monochromatic component has order less than r−1n. This generalizes an example of Guggiari and Scott and, independently, Rahimi for r=3 and thus disproves a conjecture of Gyárfás and Sárközy for all integers r≥3 such that an affine plane of order r exists.
It is known that in any r-coloring of the edges of a complete r-uniform hypergraph, there exists a spanning monochromatic component. Given a Steiner triple system on n vertices, what is the largest monochromatic component one can guarantee in an arbitrary 3-coloring of the edges? Gyárfás proved that (2n+3)/3 is an absolute lower bound and that this lower bound is best possible for infinitely many n. On the other hand, we prove that for almost all Steiner triple systems the lower bound is actually (1−o(1))n. We obtain this result as a consequence of a more general theorem which shows that the lower bound depends on the size of a largest \emph{3-partite hole} (that is, sets X1,X2,X3 with ∣X1∣=∣X2∣=∣X3∣ such that no edge intersects all of X1,X2,X3) in the Steiner triple system (Gyárfás previously observed that the upper bound depends on this parameter). Furthermore, we show that this lower bound is tight unless the coloring has a particular structure. We also suggest a variety of other Ramsey problems in the setting of Steiner triple systems.
For all integers k with k≥2, if G is a balanced k-partite graph on n≥3 vertices with minimum degree at least ⌈2n⌉+⌊2⌈2k+1⌉n+2⌋−kn={⌈2n⌉+⌊k+1n+2⌋−kn2n+⌊k+2n+2⌋−kn:k odd :k even , then G has a Hamiltonian cycle unless k=2 and 4 divides n, or k=2n and 4 divides n. In the case where k=2 and 4 divides n, or k=2n and 4 divides n, we can characterize the graphs which do not have a Hamiltonian cycle and see that ⌈2n⌉+⌊2⌈2k+1⌉n+2⌋−kn+1 suffices. This result is tight for all k≥2 and n≥3 divisible by k.
Let Tk be the transitive tournament on k vertices. We show that every oriented graph on n=4m vertices with minimum total degree (11/12+o(1))n can be partitioned into vertex disjoint T4's, and this bound is asymptotically tight. We also improve the best known bound on the minimum total degree for partitioning oriented graphs into vertex disjoint Tk's.
Lehel conjectured that in every 2-coloring of the edges of Kn, there is a vertex disjoint red and blue cycle which span V(Kn). Łuczak, Rödl, and Szemerédi proved Lehel's conjecture for large n, Allen gave a different proof for large n, and finally Bessy and Thomassé gave a proof for all n. Balogh, Barát, Gerbner, Gyárfás, and Sárközy proposed a significant strengthening of Lehel's conjecture where Kn is replaced by any graph G with δ(G)>3n/4; if true, this minimum degree condition is essentially best possible. We prove that their conjecture holds when δ(G)>(3/4+o(1))n. Our proof uses Szemerédi's regularity lemma along with the absorbing method of Rödl, Ruciński, and Szemerédi by first showing that the graph can be covered with monochromatic subgraphs having certain robust expansion properties.
The Hajnal--Szemerédi theorem states that for any integer r≥1 and any multiple n of r, if G is a graph on n vertices and δ(G)≥(1−1/r)n, then G can be partitioned into n/r vertex-disjoint copies of the complete graph on r vertices. We prove a very general analogue of this result for directed graphs: for any integer r≥4 and any sufficiently large multiple n of r, if G is a directed graph on n vertices and every vertex is incident to at least 2(1−1/r)n−1 directed edges, then G can be partitioned into n/r vertex-disjoint subgraphs of size r each of which contain every tournament on r vertices. A related Turán-type result is also proven.
Let n be sufficiently large and suppose that G is a digraph on n vertices where every vertex has in- and outdegree at least n/2. We show that G contains every orientation of a Hamilton cycle except, possibly, the antidirected one. The antidirected case was settled by DeBiasio and Molla, where the threshold is n/2+1. Our result is best possible and improves on an approximate result by Häggkvist and Thomason.
A classic theorem of Dirac from 1952 states that every graph with minimum degree at least n/2 contains a Hamiltonian cycle. In 1963, Pósa conjectured that every graph with minimum degree at least 2n/3 contains the square of a Hamiltonian cycle. In 1960, Ore relaxed the degree condition in the Dirac's theorem by proving that every graph with deg(u)+deg(v)≥n for every uv∈/E(G) contains a Hamiltonian cycle. Recently, Châu proved an Ore-type version of Pósa's conjecture for graphs on n≥n0 vertices using the regularity--blow-up method; consequently the n0 is very large (involving a tower function). Here we present another proof that avoids the use of the regularity lemma. Aside from the fact that our proof holds for much smaller n0, we believe that our method of proof will be of independent interest.
In 1960, Ghouila-Houri extended Dirac's theorem to directed graphs by proving that if D is a directed graph on n vertices with minimum out-degree and in-degree at least n/2 (i.e. minimum semi-degree at least n/2), then D contains a directed Hamiltonian cycle. Of course there are other orientations of a cycle in a directed graph and it is not clear that the semi-degree threshold for the directed Hamiltonian cycle is the same as the semi-degree threshold for some other orientation. In 1980, Grant initiated the problem of determining the minimum semi-degree threshold for the anti-directed Hamiltonian cycle (an orientation in which consecutive edges alternate direction). We prove that for sufficiently large even n, if D is a directed graph on n vertices with minimum semi-degree at least n/2+1, then D contains an anti-directed Hamiltonian cycle. This result is sharp.
Hajnal and Szemeredi proved that every graph G with |G|=ks and minimum degree at least k(s-1) contains k vertex disjoint s-cliques; moreover this degree bound is optimal. We extend their theorem to directed graphs by showing that every directed graph D with |D|=ks and minimum (total) degree at least 2k(s-1)-1 contains k vertex disjoint transitive tournaments on s vertices. Our result implies the Hajnal-Szemeredi Theorem, and the degree bound is optimal. We also make some conjectures regarding even more general results for multigraphs and partitioning into other tournaments. One of these conjectures is supported by an asymptotic result.
Given a 3-graph H, let \ex_2(n, H) denote the maximum value of the minimum codegree of a 3-graph on n vertices which does not contain a copy of H. Let F denote the Fano plane, which is the 3-graph \{axx',ayy',azz',xyz',xy'z,x'yz,x'y'z'\}. Mubayi proved that \ex_2(n,F)=(1/2+o(1))n and conjectured that \ex_2(n, F)=\floor{n/2} for sufficiently large n. Using a very sophisticated quasi-randomness argument, Keevash proved Mubayi's conjecture. Here we give a simple proof of Mubayi's conjecture by using a class of 3-graphs that we call rings. We also determine the Turán density of the family of rings.
The problem of determining the optimal minimum degree condition for a balanced bipartite graph on 2ms vertices to contain m vertex disjoint copies of K_{s,s} was solved by Zhao. Later Hladký and Schacht, and Czygrinow and DeBiasio determined the optimal minimum degree condition for a balanced bipartite graph on 2m(s+t) vertices to contain m vertex disjoint copies of K_{s,t} for fixed positive integers s<t. For a balanced bipartite graph G[U,V], let δ_U be the minimum degree over all vertices in U and δ_V be the minimum degree over all vertices in V. We consider the problem of determining the optimal value of δ_U+δ_V which guarantees that G can be tiled with K_{s,s}. We show that the optimal value depends on D:=|δ_V-δ_U|. When D is small, we show that δ_U+δ_V\geq n+3s-5 is best possible. As D becomes larger, we show that δ_U+δ_V can be made smaller, but no smaller than n+2s-2s^{1/2}. However, when D=n-C for some constant C, we show that there exist graphs with δ_U+δ_V\geq n+s^{s^{1/3}} which cannot be tiled with K_{s,s}.
Let K_4^3-2e denote the hypergraph consisting of two triples on four points. For an integer n, let t(n, K_4^3-2e) denote the smallest integer d so that every 3-uniform hypergraph G of order n with minimum pair-degree δ_2(G) \geq d contains \floor{n/4} vertex-disjoint copies of K_4^3-2e. Kühn and Osthus proved that t(n, K_4^3-2e) = (1 + o(1))n/4 holds for large integers n. Here, we prove the exact counterpart, that for all sufficiently large integers n divisible by 4, t(n, K_4^3-2e) = n/4 when n/4 is odd, and t(n, K_4^3-2e) = n/4+1 when n/4 is even. A main ingredient in our proof is the recent `absorption technique' of Rödl, Ruciński and Szemerédi.
Bipartite graph tiling was studied by Zhao who gave the best possible minimum degree conditions for a balanced bipartite graph on 2ms vertices to contain m vertex disjoint copies of K_{s,s}. Let s<t be fixed positive integers. Hladký and Schacht gave minimum degree conditions for a balanced bipartite graph on 2m(s+t) vertices to contain m vertex disjoint copies of K_{s,t}. Their results were best possible, except in the case when m is odd and t> 2s+1. We give the best possible minimum degree condition in this case.
In 1962 Pósa conjectured that every graph G on n vertices with minimum degree at least 2n/3 contains the square of a hamiltonian cycle. In 1996 Fan and Kierstead proved the path version of Pósa's Conjecture. They also proved that it would suffice to show that G contains the square of a cycle of length greater than 2n/3. Still in 1996, Komlós, Sárközy, and Szemerédi proved Pósa's Conjecture, using the Regularity and Blow-up Lemmas, for graphs of order n > n_0, where n_0 is a very large constant. Here we show without using these lemmas that n_0=2\times 10^8 is sufficient. We are motivated by the recent work of Levitt, Szemerédi and Sárközy, but our methods are based on techniques that were available in the 90's.
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.