| 1. |
- Behrstock, Jason, et al.
(författare)
-
Square percolation and the threshold for quadratic divergence in random right-angled Coxeter groups
- 2022
-
Ingår i: Random structures & algorithms (Print). - : John Wiley & Sons. - 1042-9832 .- 1098-2418. ; 60:4, s. 594-630
-
Tidskriftsartikel (refereegranskat)abstract
- Given a graph (Formula presented.), its auxiliary square-graph (Formula presented.) is the graph whose vertices are the non-edges of (Formula presented.) and whose edges are the pairs of non-edges which induce a square (i.e., a 4-cycle) in (Formula presented.). We determine the threshold edge-probability (Formula presented.) at which the Erdős–Rényi random graph (Formula presented.) begins to asymptotically almost surely (a.a.s.) have a square-graph with a connected component whose squares together cover all the vertices of (Formula presented.). We show (Formula presented.), a polylogarithmic improvement on earlier bounds on (Formula presented.) due to Hagen and the authors. As a corollary, we determine the threshold (Formula presented.) at which the random right-angled Coxeter group (Formula presented.) a.a.s. becomes strongly algebraically thick of order 1 and has quadratic divergence.
|
|
| 2. |
- Falgas-Ravry, Victor, et al.
(författare)
-
1-independent percolation on ℤ2×Kn
- 2023
-
Ingår i: Random structures & algorithms (Print). - : John Wiley & Sons. - 1042-9832 .- 1098-2418. ; 62:4, s. 887-910
-
Tidskriftsartikel (refereegranskat)abstract
- A 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.).
|
|
| 3. |
- Falgas-Ravry, Victor
(författare)
-
On an extremal problem for locally sparse multigraphs
- 2024
-
Ingår i: European journal of combinatorics (Print). - : Elsevier. - 0195-6698 .- 1095-9971. ; 118
-
Tidskriftsartikel (refereegranskat)abstract
- A multigraph G is an (s,q)-graph if every s-set of vertices in G supports at most q edges of G, counting multiplicities. Mubayi and Terry posed the problem of determining the maximum of the product of the edge-multiplicities in an (s,q)-graph on n vertices. We give an asymptotic solution to this problem for the family (s,q)=(2r,a(2r2)+ex(2r,Kr+1)−1) with r,a ∈ Z≥2. 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 r=2. 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.
|
|
| 4. |
- Day, A. Nicholas, et al.
(författare)
-
Extremal problems for multigraphs
- 2022
-
Ingår i: Journal of combinatorial theory. Series B (Print). - : Academia Press. - 0095-8956 .- 1096-0902. ; 154, s. 1-48
-
Tidskriftsartikel (refereegranskat)abstract
- An (n,s,q)-graph is an n-vertex multigraph in which every s-set of vertices spans at most q edges. Turán-type questions on the maximum of the sum of the edge multiplicities in such multigraphs have been studied since the 1990s. More recently, Mubayi and Terry (2019) [13] posed the problem of determining the maximum of the product of the edge multiplicities in (n,s,q)-graphs. We give a general lower bound construction for this problem for many pairs (s,q), which we conjecture is asymptotically best possible. We prove various general cases of our conjecture, and in particular we settle a conjecture of Mubayi and Terry on the (s,q)=(4,6a+3) case of the problem (for a≥2); this in turn answers a question of Alon. We also determine the asymptotic behaviour of the problem for ‘sparse’ multigraphs (i.e. when q≤2(s2)). Finally we introduce some tools that are likely to be useful for attacking the problem in general.
|
|
| 5. |
- Day, A. Nicholas, et al.
(författare)
-
Maker-Breaker percolation games I : crossing grids
- 2021
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press. - 0963-5483 .- 1469-2163. ; 30:2, s. 200-227
-
Tidskriftsartikel (refereegranskat)abstract
- Motivated by problems in percolation theory, we study the following two-player positional game. Let ?(mxn) be a rectangular grid-graph with m vertices in each row and n vertices in each column. Two players, Maker and Breaker, play in alternating turns. On each of her turns, Maker claims p (as yet unclaimed) edges of the board ?(mxn), while on each of his turns Breaker claims q (as yet unclaimed) edges of the board and destroys them. Maker wins the game if she manages to claim all the edges of a crossing path joining the left-hand side of the board to its right-hand side, otherwise Breaker wins. We call this game the (p, q)-crossing game on ?(mxn). Given m, n is an element of N, for which pairs (p, q) does Maker have a winning strategy for the (p, q)-crossing game on ?(mxn)? The (1, 1)-case corresponds exactly to the popular game of Bridg-it, which is well understood due to it being a special case of the older Shannon switching game. In this paper we study the general (p, q)-case. Our main result is to establish the following transition. If >= 2, then Maker wins the game on arbitrarily long versions of the narrowest board possible, that is, Maker has a winning strategy for the (2, )-crossing game on ?x(+1 for any is an element of N. pqqqmq)mIf p <= 2q - 1, then for every width n of the board, Breaker has a winning strategy for the (p, q)-crossing game on ?mxn for all sufficiently large board-lengths m. Our winning strategies in both cases adapt more generally to other grids and crossing games. In addition we pose many new questions and problems.
|
|
| 6. |
- Day, A. Nicholas, et al.
(författare)
-
Maker-breaker percolation games II : Escaping to infinity
- 2021
-
Ingår i: Journal of combinatorial theory. Series B (Print). - : Elsevier. - 0095-8956 .- 1096-0902. ; 151, s. 482-508
-
Tidskriftsartikel (refereegranskat)abstract
- Let Lambda be an infinite connected graph, and let v(0) be a vertex of Lambda. We consider the following positional game. Two players, Maker and Breaker, play in alternating turns. Initially all edges of Lambda are marked as unsafe. On each of her turns, Maker marks p unsafe edges as safe, while on each of his turns Breaker takes q unsafe edges and deletes them from the graph. Breaker wins if at any time in the game the component containing v(0) becomes finite. Otherwise if Maker is able to ensure that v(0) remains in an infinite component indefinitely, then we say she has a winning strategy. This game can be thought of as a variant of the celebrated Shannon switching game. Given (p, q) and (Lambda, v(0)), we would like to know: which of the two players has a winning strategy?Our main result in this paper establishes that when Lambda = Z(2) and v(0) is any vertex, Maker has a winning strategy whenever p >= 2q, while Breaker has a winning strategy whenever 2p <= q. In addition, we completely determine which of the two players has a winning strategy for every pair (p, q) when Lambda is an infinite d -regular tree. Finally, we give some results for general graphs and lattices and pose some open problems. (C) 2020 Elsevier Inc. All rights reserved.
|
|
| 7. |
- Falgas-Ravry, Victor, 1986-
(författare)
-
Minimal weight in union-closed families
- 2011
-
Ingår i: The Electronic Journal of Combinatorics. - : Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 18:1, s. P95-
-
Tidskriftsartikel (refereegranskat)abstract
- Let Omega be a finite set and let S subset of P(Omega) be a set system on Omega. For x is an element of Omega, we denote by d(S)(x) the number of members of S containing x.Along-standing conjecture of Frankl states that if S is union-closed then there is some x is an element of Omega with d(S)(x)>= 1/2|S|. We consider a related question. Define the weight of a family S to be w(S) := A.S|A|.SupposeSisunion-closed. How small can w(S) be? Reimer showed w(S) >= 1/2|S|log(2)|S|, and that this inequality is tight. In this paper we show how Reimer's bound may be improved if we have some additional information about the domain Omega of S: if S separates the points of its domain, then w(S) >= ((vertical bar Omega vertical bar)(2)). This is stronger than Reimer's Theorem when |Omega| > root|S|log(2)|S|. In addition we constructa family of examples showing the combined bound on w(S)istightexcept in the region |Omega| = Theta(root|S|log(2)|S|), where it may be off by a multiplicative factor of 2. Our proof also gives a lower bound on the average degree: if S is a point-separating union-closed family on Omega, then 1/ |Omega|Sigma(x is an element of Omega)d(S)(x)>= 1/2 root|S|log(2)|S| broken vertical bar O(1), and this is best possible except for a multiplicative factor of 2.
|
|
| 8. |
- Falgas-Ravry, Victor, et al.
(författare)
-
Multicolor containers, extremal entropy, and counting
- 2019
-
Ingår i: Random structures & algorithms (Print). - : Wiley-Blackwell. - 1042-9832 .- 1098-2418. ; 54:4, s. 676-720
-
Tidskriftsartikel (refereegranskat)abstract
- In breakthrough results, Saxton-Thomason and Balogh-Morris-Samotij developed powerful theories of hypergraph containers. In this paper, we explore some consequences of these theories. We use a simple container theorem of Saxton-Thomason and an entropy-based framework to deduce container and counting theorems for hereditary properties of k-colorings of very general objects, which include both vertex- and edge-colorings of general hypergraph sequences as special cases. In the case of sequences of complete graphs, we further derive characterization and transference results for hereditary properties in terms of their stability families and extremal entropy. This covers within a unified framework a great variety of combinatorial structures, some of which had not previously been studied via containers: directed graphs, oriented graphs, tournaments, multigraphs with bounded multiplicity, and multicolored graphs among others. Similar results were recently and independently obtained by Terry.
|
|
| 9. |
|
|
| 10. |
- Falgas-Ravry, Victor, et al.
(författare)
-
Rectilinear approximation and volume estimates for hereditary bodies via [0,1]-decorated containers
- 2023
-
Ingår i: Journal of Graph Theory. - : John Wiley & Sons. - 0364-9024 .- 1097-0118. ; 104:1, s. 104-132
-
Tidskriftsartikel (refereegranskat)abstract
- We use the hypergraph container theory of Balogh-Morris-Samotij and Saxton-Thomason to obtain general rectilinear approximations and volume estimates for sequences of bodies closed under certain families of projections. We give a number of applications of our results, including a multicolour generalisation of a theorem of Hatami, Janson and Szegedy on the entropy of graph limits. Finally, we raise a number of questions on geometric and analytic approaches to containers.
|
|
