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 every n-vertex graph with at least (2n)−(n−4) edges has a fractional triangle decomposition, for n≥7. This is a key ingredient in our proof, given in a companion paper, that every n-vertex 2-coloured complete graph contains n2/12+o(n2) edge-disjoint monochromatic triangles, which confirms a conjecture of Erdős.
An old and well-known conjecture of Frankl and Füredi states that the Lagrangian of an r-uniform hypergraph with m edges is maximised by an initial segment of colex. In this paper we disprove this conjecture by finding an infinite family of counterexamples for all r≥4. We also show that, for sufficiently large t∈N, the conjecture is true in the range (rt)≤m≤(rt+1)−(r−2t−1).
A well-known conjecture of Frankl and Füredi from 1989 states that an initial segment of colex of has the largest Lagrangian of any r-uniform hypergraph with m hyperedges. We show that this is true when r=3. We also give a new proof of a related conjecture of Nikiforov and a counterexample to an old conjecture of Ahlswede and Katona.
We prove that in every 2-edge-colouring of Kn there is a collection of n2/12+o(n2) edge-disjoint monochromatic triangles, thus confirming a conjecture of Erdős. We also prove a corresponding stability result, showing that 2-colourings that are close to attaining the aforementioned bound have a colour class which is close to bipartite. As part of our proof, we confirm a recent conjecture of Tyomkyn about the fractional version of this problem.
Let H be an induced subgraph of the hypercube Qk, for some k. We show that for some c=c(H), the vertices of Qn can be partitioned into induced copies of H and a remainder of at most O(nc) vertices. We also show that the error term cannot be replaced by anything smaller than logn.
Let G be an induced subgraph of the hypercube Qk for some k. We show that if ∣G∣ is a power of 2 then, for sufficiciently large n, the vertex set of Qn can be partitioned into induced copies of G. This answers a question of Offner. In fact, we prove a stronger statement: if X is a subset of {0,1}k for some k and if ∣X∣ is a power of 2, then, for sufficiently large n, {0,1}n can be partitioned into isometric copies of X.
We consider the problem of minimising the number of edges that are contained in triangles, among n-vertex graphs with a given number of edges. We prove a conjecture of Füredi and Maleki that gives an exact formula for this minimum, for sufficiently large n.
Let P be a poset of size 2k that has a greatest and a least element. We prove that, for sufficiently large n, the Boolean lattice 2[n] can be partitioned into copies of P. This resolves a conjecture of Lonc.
Let T be a tile in Zn, meaning a finite subset of Zn. It may or may not tile Zn, in the sense of Zn having a partition into copies of T. However, we prove that T does tile Zd for some d. This resolves a conjecture of Chalcraft.
In this paper we consider a pursuit-evasion game on a graph. A team of cats, which may choose any vertex of the graph at any turn, tries to catch an invisible mouse, which is constrained to moving along the vertices of the graph. Our main focus shall be on trees. We prove that ⌈(1/2)log2(n)⌉ cats can always catch a mouse on a tree of order n and give a collection of trees where the mouse can avoid being caught by (1/4−o(1))log2(n) cats.
Pór and Wood conjectured that for all k,l≥2 there exists n≥2 with the following property: whenever n points, no l+1 of which are collinear, are chosen in the plane and each of them is assigned one of k colours, then there must be a line (that is, a maximal set of collinear points) all of whose points have the same colour. The conjecture is easily seen to be true for l=2 (by the pigeonhole principle) and in the case k=2 it is an immediate corollary of the Motzkin-Rabin theorem. In this note we show that the conjecture is false for k,l≥3.
Let G be an r-uniform hypergraph. When is it possible to orient the edges of G in such a way that every p-set of vertices has some p-degree equal to 0? (The p-degrees generalise for sets of vertices what in-degree and out-degree are for single vertices in directed graphs.) Caro and Hansberg asked if the obvious Hall-type necessary condition is also sufficient. Our main aim is to show that this is true for r large (for given p), but false in general. Our counterexample is based on a new technique in sparse Ramsey theory that may be of independent interest.
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.