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 vertex domination conjecture of Erd\H os, Faudree, Gould, Gyárfás, Rousseau, and Schelp, that for every n-vertex complete graph with edges coloured using three colours there exists a set of at most three vertices which have at least 2n/3 neighbours in one of the colours. Our proof makes extensive use of the ideas presented in "A New Bound for the 2/3 Conjecture" by Král', Liu, Sereni, Whalen, and Yilma.
Guessing games for directed graphs were introduced by Riis for studying multiple unicast network coding problems. In a guessing game, the players toss generalised dice and can see some of the other outcomes depending on the structure of an underlying digraph. They later guess simultaneously the outcome of their own die. Their objective is to find a strategy which maximises the probability that they all guess correctly. The performance of the optimal strategy for a graph is measured by the guessing number of the digraph. Christofides and Markström studied guessing numbers of undirected graphs and defined a strategy which they conjectured to be optimal. One of the main results of this paper is a disproof of this conjecture. The main tool so far for computing guessing numbers of graphs is information theoretic inequalities. In the paper we show that Shannon's information inequalities, which work particularly well for a wide range of graph classes, are not sufficient for computing the guessing number. Finally we pose a few more interesting questions some of which we can answer and some which we leave as open problems.
If F is a family of graphs then the Turán density of F is determined by the minimum chromatic number of the members of F. The situation for Turán densities of 3-graphs is far more complex and still very unclear. Our aim in this paper is to present new exact Turán densities for individual and finite families of 3-graphs, in many cases we are also able to give corresponding stability results. As well as providing new examples of individual 3-graphs with Turán densities equal to 2/9,4/9,5/9 and 3/4 we also give examples of irrational Turán densities for finite families of 3-graphs, disproving a conjecture of Chung and Graham. (Pikhurko has independently disproved this conjecture by a very different method.) A central question in this area, known as Turán's problem, is to determine the Turán density of K4(3)={123,124,134,234}. Turán conjectured that this should be 5/9. Razborov [On 3-hypergraphs with forbidden 4-vertex configurations, in SIAM J. Disc. Math. 24 (2010), 946-963] showed that if we consider the induced Turán problem forbidding K4(3) and E1, the 3-graph with 4 vertices and a single edge, then the Turán density is indeed 5/9. We give some new non-induced results of a similar nature, in particular we show that π(K4(3),H)=5/9 for a 3-graph H satisfying π(H)=3/4. We end with a number of open questions focusing mainly on the topic of which values can occur as Turán densities. Our work is mainly computational, making use of Razborov's flag algebra framework. However all proofs are exact in the sense that they can be verified without the use of any floating point operations. Indeed all verifying computations use only integer operations, working either over Q or in the case of irrational Turán densities over an appropriate quadratic extension of Q.
In this paper we describe a number of extensions to Razborov's semidefinite flag algebra method. We will begin by showing how to apply the method to significantly improve the upper bounds of edge and vertex Turán density type results for hypercubes. We will then introduce an improvement to the method which can be applied in a more general setting, notably to 3-uniform hypergraphs, to get a new upper bound of 0.5615 for π(K43). For hypercubes we improve Thomason and Wagner's result on the upper bound of the edge Turán density of a 4-cycle free subcube to 0.60318 and Chung's result on forbidding 6-cycles to 0.36577. We also show that the upper bound of the vertex Turán density of $\mc{Q}_3$ can be improved to 0.76900, and that the vertex Turán density of $\mc{Q}_3$ with one vertex removed is precisely 2/3.
We say that α∈[0,1) is a jump for an integer r≥2 if there exists c(α)>0 such that for all ε>0 and all t≥1 any r-graph with n≥n0(α,ε,t) vertices and density at least α+ε contains a subgraph on t vertices of density at least α+c. The Erd\H os--Stone--Simonovits theorem implies that for r=2 every α∈[0,1) is a jump. Erd\H os showed that for all r≥3, every α∈[0,r!/rr) is a jump. Moreover he made his famous "jumping constant conjecture" that for all r≥3, every α∈[0,1) is a jump. Frankl and Rödl disproved this conjecture by giving a sequence of values of non-jumps for all r≥3. We use Razborov's flag algebra method to show that jumps exist for r=3 in the interval [2/9,1). These are the first examples of jumps for any r≥3 in the interval [r!/rr,1). To be precise we show that for r=3 every α∈[0.2299,0.2316) is a jump. We also give an improved upper bound for the Turán density of K4−={123,124,134}: π(K4−)≤0.2871. This in turn implies that for r=3 every α∈[0.2871,8/27) is a jump.
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.