58 research outputs found
An extremal construction for (5,24)-multigraphs
No full textIn the mid 1900s the area of extremal graph theory took its first propersteps with the proof of Turán’s theorem. In 1963 Pál Erdős asked for an extension of this fundamental result regarding (n, s, q)-graphs; graphs on n vertices in which any s-set of vertices spans at most q edges, and multiple edges are allowed; and raised the question of determining ex(n, s, q), the maximum number of edges spanning such a graph. More recently, Mubayi and Terry looked at the problem of determining the maximum productof the edges in (n, s, q)-graphs. Their proof was further investigated by Day, Falgas-Ravry and Treglown who, in particular, settled a conjecture of Mubayi and Terry regarding the case (s, q) = (4, 6a+3), for a ∈ Z≥2. In this thesis we look at the case (s, q) = (5, 24), which is mentioned as an open problem at the end of the paper by Day, Falgas-Ravry and Treglown. A hypothetical extremal construction was provided by Victor Falgas-Ravry, and we prove it to be asymptotically optimal
On an extremal problem for locally sparse multigraphs
No full textA multigraph is an -graph if every -set of vertices in
supports at most edges of , counting multiplicities. Mubayi and Terry
posed the problem of determining the maximum of the product of the
edge-multiplicities in an -graph on vertices. We give an asymptotic
solution to this problem for the family with . This greatly generalises previous results on the problem due to Mubayi and
Terry and to Day, Treglown and the author, who between them had resolved the
special case . Our result asymptotically confirms an infinite family of
cases in (and overcomes a major obstacle to a resolution of) a conjecture of
Day, Treglown and the author.Comment: 26 pages, minor revisions following two referees' helpful comment
Turan H-densities for 3-graphs
No full textGiven an r-graph H on h vertices, and a family F of forbidden subgraphs, we define ex H (n, F) to be the maximum number of induced copies of H in an F-free r-graph on n vertices. Then the Turan H-density of F is the limit pi(H)(F) = (lim)(n ->infinity) ex(H)(n, F)/((n)(h)) This generalises the notions of Turan-density (when H is an r-edge), and inducibility (when F is empty). Although problems of this kind have received some attention, very few results are known. We use Razborov's semi-definite method to investigate Turan H-densities for 3-graphs. In particular, we show that pi(-)(K4)(K-4) = 16/27, with Turans construction being optimal. We prove a result in a similar flavour for K-5 and make a general conjecture on the value of pi(Kt)-(K-t). We also establish that pi(4.2)(empty set) = 3/4, where 4: 2 denotes the 3-graph on 4 vertices with exactly 2 edges. The lower bound in this case comes from a random geometric construction strikingly different from previous known extremal examples in 3-graph theory. We give a number of other results and conjectures for 3-graphs, and in addition consider the inducibility of certain directed graphs. Let (S) over right arrow (k) be the out-star on k vertices; i.e. the star on k vertices with all k 1 edges oriented away from the centre. We show that pi((S) over right arrow3)(empty set) = 2 root 3 - 3, with an iterated blow-up construction being extremal. This is related to a conjecture of Mubayi and Rodl on the Turan density of the 3-graph C-5. We also determine pi((S) over right arrowk) (empty set) when k = 4, 5, and conjecture its value for general k
1-independent percolation on ℤ2×Kn
No full textA random graph model on a host graph (Formula presented.) is said to be 1-independent if for every pair of vertex-disjoint subsets (Formula presented.) of (Formula presented.), the state of edges (absent or present) in (Formula presented.) is independent of the state of edges in (Formula presented.). For an infinite connected graph (Formula presented.), the 1-independent critical percolation probability (Formula presented.) is the infimum of the (Formula presented.) such that every 1-independent random graph model on (Formula presented.) in which each edge is present with probability at least (Formula presented.) almost surely contains an infinite connected component. Balister and Bollobás observed in 2012 that (Formula presented.) tends to a limit in (Formula presented.) as (Formula presented.), and they asked for the value of this limit. We make progress on a related problem by showing that (Formula presented.) In fact, we show that the equality above remains true if the sequence of complete graphs (Formula presented.) is replaced by a sequence of weakly pseudorandom graphs on (Formula presented.) vertices with average degree (Formula presented.). We conjecture the answer to Balister and Bollobás's question is also (Formula presented.)
Random subcube intersection graphs I : cliques and covering
No full textWe study random subcube intersection graphs, that is, graphs obtained by selecting a random collection of subcubes of a fixed hypercube Qd to serve as the vertices of the graph, and setting an edge between a pair of subcubes if their intersection is non-empty. Our motivation for considering such graphs is to model 'random compatibility' between vertices in a large network. For both of the models considered in this paper, we determine the thresholds for covering the underlying hypercube Qd and for the appearance of s-cliques. In addition we pose a number of open problems
Subgraphs with large minimum ℓ-degree in hypergraphs where almost all ℓ-degrees are large
No full textLet G be an r-uniform hypergraph on n vertices such that all but at most ε(n ℓ) ℓ-subsets of vertices have degree at least p(n-ℓ r-ℓ). We show that G contains a large subgraph with high minimum ℓ-degree
Codegree Thresholds for Covering 3-Uniform Hypergraphs
No full textGiven two 3-uniform hypergraphs F and G = (V, E), we say that G has an F-covering if we can cover V with copies of F. The minimum codegree of G is the largest integer d such that every pair of vertices from V is contained in at least d triples from E. Define c(2)(n, F) to be the largest minimum codegree among all n-vertex 3-graphs G that contain no F-covering. Determining c(2)(n, F) is a natural problem intermediate (but distinct) from the well-studied Turan problems and tiling problems. In this paper, we determine c(2)(n, K-4) (for n > 98) and the associated extremal configurations (for n > 998), where K-4 denotes the complete 3-graph on 4 vertices. We also obtain bounds on c(2)(n, F) which are apart by at most 2 in the cases where F is K-4(-) (K-4 with one edge removed), K-5(-), and the tight cycle C-5 on 5 vertices.</p
The Maker-Breaker percolation game on a random board
No full textThe Maker-Breaker percolation game on , introduced
by Day and Falgas-Ravry, is played in the following way. Before the game
starts, each edge of is removed independently with probability
. After that, Maker chooses a vertex to protect. Then, in each round
Maker and Breaker claim respectively and unclaimed edges of .
Breaker wins if after the removal of the edges claimed by him the component of
becomes finite, and Maker wins if she can indefinitely prevent Breaker
from winning.
We show that for any , Breaker almost surely has a wining strategy for
the game on . This fully answers a question of Day
and Falgas-Ravry, who showed that for Maker has a winning strategy for
the game. Further, we show that in the game on
Maker almost surely has a winning strategy whenever , while Breaker almost surely has a winning strategy whenever . This shows that the threshold value of above which Maker has a
winning strategy for the game on is non-trivial. In
fact, we prove similar results in various settings, including other lattices
and biases .
These results extend also to the most general case, which we introduce, where
each edge is given to Maker with probability and to Breaker with
probability before the game starts.Comment: 34 pages, 6 figure
- …
