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
Katona's intersection theorem states that every intersecting family F⊆[n](k) satisfies ∣∂F∣≥∣F∣, where ∂F={F∖x:x∈F∈F} is the shadow of F. Frankl conjectured that for n>2k and every intersecting family F⊆[n](k), there is some i∈[n] such that ∣∂F(i)∣≥∣F(i)∣, where F(i)={F∖i:i∈F∈F} is the link of F at i. Here, we prove this conjecture in a very strong form for n>(2k+1). In particular, our result implies that for any j∈[k], there is a j-set {a1,…,aj}∈[n](j) such that ∣∂F(a1,…,aj)∣≥∣F(a1,…,aj)∣. A similar statement is also obtained for cross-intersecting families.
We prove a new sufficient pair degree condition for tight Hamiltonian cycles in 3-uniform hypergraphs that (asymptotically) improves the best known pair degree condition due to Rödl, Ruciński, and Szemerédi. For graphs, Chvátal characterised all those sequences of integers for which every pointwise larger (or equal) degree sequence guarantees the existence of a Hamiltonian cycle. A step towards Chvátal's theorem was taken by Pósa, who improved on Dirac's tight minimum degree condition for Hamiltonian cycles by showing that a certain weaker condition on the degree sequence of a graph already yields a Hamiltonian cycle. In this work, we take a similar step towards a full characterisation of all pair degree matrices that ensure the existence of tight Hamiltonian cycles in 3-uniform hypergraphs by proving a 3-uniform analogue of Pósa's result. In particular, our result strengthens the asymptotic version of the result by Rödl, Ruciński, and Szemerédi.
Sidorenko's conjecture states that the number of copies of a bipartite graph H in a graph G is asymptotically minimised when G is a quasirandom graph. A notorious example where this conjecture remains open is when H=K5,5∖C10. It was even unknown whether this graph possesses the strictly stronger, weakly norming property. We take a step towards understanding the graph K5,5∖C10 by proving that it is not weakly norming. More generally, we show that 'twisted' blow-ups of cycles, which include K5,5∖C10 and C6□K2, are not weakly norming. This answers two questions of Hatami. The method relies on the analysis of Hessian matrices defined by graph homomorphisms, by using the equivalence between the (weakly) norming property and convexity of graph homomorphism densities. We also prove that Kt,t minus a perfect matching, proven to be weakly norming by Lovász, is not norming for every t>3.
We investigate the problem of determining how many monochromatic trees are necessary to cover the vertices of an edge-coloured random graph. More precisely, we show that for p≫n−1/6(lnn)1/6, in any 3-edge-colouring of the random graph G(n,p) we can find three monochromatic trees such that their union covers all vertices. This improves, for three colours, a result of Bucić, Korándi and Sudakov.
Given two non-negative integers n and s, define m(n,s) to be the maximal number such that in every hypergraph H on n vertices and with at most m(n,s) edges there is a vertex x such that ∣Hx∣≥∣E(H)∣−s, where Hx={H∖{x}:H∈E(H)}. This problem has been posed by Füredi and Pach and by Frankl and Tokushige. While the first results were only for specific small values of s, Frankl determined m(n,2d−1−1) for all d∈N with d∣n. Subsequently, the goal became to determine m(n,2d−1−c) for larger c. Frankl and Watanabe determined m(n,2d−1−c) for c∈{0,2}. Other general results were not known so far. Our main result sheds light on what happens further away from powers of two: We prove that m(n,2d−1−c)=dn(2d−c) for d≥4c and d∣n and give an example showing that this equality does not hold for c=d. The other line of research on this problem is to determine m(n,s) for small values of s. In this line, our second result determines m(n,2d−1−c) for c∈{3,4}. This solves more instances of the problem for small s and in particular solves a conjecture by Frankl and Watanabe.
We show that every k-uniform hypergraph on n vertices whose minimum (k−2)-degree is at least (5/9+o(1))n2/2 contains a Hamiltonian cycle. A construction due to Han and Zhao shows that this minimum degree condition is optimal. The same result was proved independently by Lang and Sahueza-Matamala.
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.