| 1. |
- 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.
|
|
| 2. |
- Falgas-Ravry, Victor, et al.
(författare)
-
Speed and concentration of the covering time for structured coupon collectors
- 2020
-
Ingår i: Advances in Applied Probability. - : Cambridge University Press. - 0001-8678 .- 1475-6064. ; 52:2, s. 433-462
-
Tidskriftsartikel (refereegranskat)abstract
- Let V be an n-set, and let X be a random variable taking values in the powerset of V. Suppose we are given a sequence of random coupons X1,X2,…, where the Xi are independent random variables with distribution given by X. The covering time T is the smallest integer t≥0 such that ⋃ti=1Xi=V. The distribution of T is important in many applications in combinatorial probability, and has been extensively studied. However the literature has focussed almost exclusively on the case where X is assumed to be symmetric and/or uniform in some way.In this paper we study the covering time for much more general random variables X; we give general criteria for T being sharply concentrated around its mean, precise tools to estimate that mean, as well as examples where T fails to be concentrated and when structural properties in the distribution of X allow for a very different behaviour of T relative to the symmetric/uniform case.
|
|
| 3. |
- Larsson, Joel, 1987-
(författare)
-
On random satisfiability and optimization problems
- 2018
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In Paper I, we study the following optimization problem: in the complete bipartite graph where edges are given i.i.d. weights of pseudo-dimension q>0, find a perfect matching with minimal total weight. The generalized Mézard-Parisi conjecture states that the limit of this minimum exists and is given by the solution to a certain functional equation. This conjecture has been confirmed for q=1 and for q>1. We prove it for the last remaining case 0<q<1.In Paper II, we study generalizations of the coupon collector problem. Versions of this problem shows up naturally in various context and has been studied since the 18th century. Our focus is on using existing methods in greater generality in a unified way, so that others can avoid ad-hoc solutions.Papers III & IV concerns the satisfiability of random Boolean formulas. The classic model is to pick a k-CNF with m clauses on n variables uniformly at random from all such formulas. As the ratio m/n increases, the formulas undergo a sharp transition from satisfiable (w.h.p.) to unsatisfiable (w.h.p.). The critical ratio for which this occurs is called the satisfiability threshold.We study two variations where the signs of variables in clauses are not chosen uniformly. In paper III, variables are biased towards occuring pure rather than negated. In paper IV, there are two types of clauses, with variables in them biased in opposite directions. We relate the thresholds of these models to the threshold of the classical model.
|
|
| 4. |
- 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.
|
|
| 5. |
- 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.
|
|
| 6. |
- 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.
|
|
| 7. |
- Falgas-Ravry, Victor, et al.
(författare)
-
Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
- 2021
-
Ingår i: Combinatorics, probability & computing. - : Cambridges Institutes Press. - 0963-5483 .- 1469-2163. ; 30:2, s. 175-199
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate a covering problem in 3-uniform hypergraphs (3-graphs): Given a 3-graph F, what is c(1)(n, F), the least integer d such that if G is an n-vertex 3-graph with minimum vertex-degree delta(1)(G) > d then every vertex of G is contained in a copy of F in G?We asymptotically determine c(1)(n, F) when F is the generalized triangle K-4((3)), and we give close to optimal bounds in the case where F is the tetrahedron K-4((3)) (the complete 3-graph on 4 vertices).This latter problem turns out to be a special instance of the following problem for graphs: Given an nvertex graph G with m> n(2)/4 edges, what is the largest t such that some vertex in G must be contained in t triangles? We give upper bound constructions for this problem that we conjecture are asymptotically tight. We prove our conjecture for tripartite graphs, and use flag algebra computations to give some evidence of its truth in the general case.
|
|
| 8. |
- 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.
|
|
| 9. |
- 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.).
|
|
| 10. |
- 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.
|
|
