Source author record

Victor Falgas-Ravry

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.PR Discrete Mathematics math.GR math.GT

Catalog footprint

Research overview

20works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

$1$ -independent percolation on $\mathbb{Z}^2 \times K_n$

A random graph model on a host graph H is said to be 1-independent if for every pair of vertex-disjoint subsets A,B of E(H), the state of edges (absent or present) in A is independent of the state of edges in B. For an infinite connected graph H, the 1-independent critical percolation probability $p_{1,c}(H)$ is the infimum of the p in [0,1] such that every 1-independent random graph model on H in which each edge is present with probability at least p almost surely contains an infinite connected component. Balister and Bollobás observed in 2012 that $p_{1,c}(\mathbb{Z}^d)$ is nonincreasing and tends to a limit in [1/2, 1] as d tends to infinity. They asked for the value of this limit. We make progress towards this question by showing that $\lim_{n\rightarrow \infty}p_{1,c}(\mathbb{Z}^2\times K_n)=4-2\sqrt{3}=0.5358\ldots \ .$ In fact, we show that the equality above remains true if the sequence of complete graphs $K_n$ is replaced by a sequence of weakly pseudorandom graphs on n vertices with average degree $ω(\log n)$ . We conjecture that the equality also remains true if $K_n$ is replaced instead by the n-dimensional hypercube $Q_n$ . This latter conjecture would imply the answer to Balister and Bollobás's question is $4-2\sqrt{3}$ . Using our results, we are also able to resolve a problem of Day, Hancock and the first author on the emergence of long paths in 1-independent random graph models on $\mathbb{Z}\times K_n$ . Finally, we prove some results on component evolution in 1-independent random graphs, and discuss a number of open problems arising from our work that may pave the way for further progress on the question of Balister and Bollobás.

preprint2020arXiv

Existence thresholds and Ramsey properties of random posets

Let $\mathcal P(n)$ denote the power set of $[n]$ , ordered by inclusion, and let $\mathcal P (n,p)$ denote the random poset obtained from $\mathcal P(n)$ by retaining each element from $\mathcal P (n)$ independently at random with probability $p$ and discarding it otherwise. Given any fixed poset $F$ we determine the threshold for the property that $\mathcal P(n,p)$ contains $F$ as an induced subposet. We also asymptotically determine the number of copies of a fixed poset $F$ in $\mathcal P(n)$ . Finally, we obtain a number of results on the Ramsey properties of the random poset $\mathcal P(n,p)$ .

preprint2020arXiv

Long paths and connectivity in { $1$ }-independent random graphs

Given a graph $G$ , a probability measure $μ$ on the subsets of the edge set of $G$ is said to be $1$ -independent if events determined by edge sets that are at graph distance at least $1$ apart in $G$ are independent. Call such a probability measure a $1$ -ipm on $G$ , and denote by $\mathbf{G}_μ$ the associated random spanning subgraph of $G$ . Let $\mathcal{M}_{1,\geqslant p}(G)$ (resp. $\mathcal{M}_{1,\leqslant p}(G)$ ) denote the collection of $1$ -ipms $μ$ on $G$ for which each edge is included in $\mathbf{G}_μ$ with probability at least $p$ (resp. at most $p$ ). Let $\mathbb{Z}^2$ denote the square integer lattice. Balister and Bollobás raised the question of determining the critical value $p_{\star}=p_{1,c}(\mathbb{Z}^2)$ such that for all $p>p_{\star}$ and all $μ\in \mathcal{M}_{1,\geqslant p}(\mathbb{Z}^2)$ , $\left(\mathbf{\mathbb{Z}^2}\right)_μ$ almost surely contains an infinite component. This can be thought of as asking for a $1$ -independent analogue of the celebrated Harris--Kesten theorem. In this paper we investigate both this problem and connectivity problems for $1$ -ipms more generally. We give two lower bounds on $p_{\star}$ that significantly improve on the previous bounds. Furthermore, motivated by the Russo--Seymour--Welsh lemmas, we define a $1$ -independent critical probability for long paths and determine its value for the line and ladder lattices. Finally, for finite graphs $G$ we study $f_{1,G}(p)$ (respectively $F_{1,G}(p)$ ), the infimum (resp. supremum) over all $μ\in \mathcal{M}_{1,\geqslant p}(G)$ (resp. all $μ\in \mathcal{M}_{1,\leqslant p}(G)$ ) of the probability that $\mathbf{G}_μ$ is connected. We determine $f_{1,G}(p)$ and $F_{1,G}(p)$ exactly when $G$ is a path, a complete graph and a cycle of length at most $5$ . Many new problems arise from our work, which are discussed in the final section of the paper.

preprint2020arXiv

Maker-Breaker Percolation Games I: Crossing Grids

Motivated by problems in percolation theory, we study the following 2-player positional game. Let $Λ_{m \times n}$ 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 $Λ_{m \times n}$ , 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 $Λ_{m \times n}$ . Given $m,n\in \mathbb{N}$ , for which pairs $(p,q)$ does Maker have a winning strategy for the $(p,q)$ -crossing game on $Λ_{m \times n}$ ? 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: $\bullet$ If $p\geqslant 2q$ , then Maker wins the game on arbitrarily long versions of the narrowest board possible, i.e. Maker has a winning strategy for the $(2q, q)$ -crossing game on $Λ_{m \times(q+1)}$ for any $m\in \mathbb{N}$ ; $\bullet$ if $p\leqslant 2q-1$ , then for every width $n$ of the board, Breaker has a winning strategy for the $(p,q)$ -crossing game on $Λ_{m \times n}$ 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.

preprint2020arXiv

Maker-Breaker Percolation Games II: Escaping to Infinity

Let $Λ$ be an infinite connected graph, and let $v_0$ be a vertex of $Λ$ . We consider the following positional game. Two players, Maker and Breaker, play in alternating turns. Initially all edges of $Λ$ 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 $(Λ, 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 $Λ= \mathbb{Z}^2$ and $v_0$ is any vertex, Maker has a winning strategy whenever $p\geq 2q$ , while Breaker has a winning strategy whenever $2p\leq q$ . In addition, we completely determine which of the two players has a winning strategy for every pair $(p,q)$ when $Λ$ is an infinite $d$ -regular tree. Finally, we give some results for general graphs and lattices and pose some open problems.

preprint2016arXiv

Full subgraphs

Let $G=(V,E)$ be a graph of density $p$ on $n$ vertices. Following Erdős, Łuczak and Spencer, an $m$ -vertex subgraph $H$ of $G$ is called {\em full} if $H$ has minimum degree at least $p(m - 1)$ . Let $f(G)$ denote the order of a largest full subgraph of $G$ . If $p\binom{n}{2}$ is a non-negative integer, define $f(n,p) = \min\{f(G) : \vert V(G)\vert = n, \ \vert E(G)\vert = p\binom{n}{2} \}.$ Erdős, Łuczak and Spencer proved that for $n \geq 2$ , $(2n)^{\frac{1}{2}} - 2 \leq f(n, {\frac{1}{2}}) \leq 4n^{\frac{2}{3}}(\log n)^{\frac{1}{3}}.$ In this paper, we prove the following lower bound: for $n^{-\frac{2}{3}} <p_n <1-n^{-\frac{1}{7}}$ , $f(n,p) \geq \frac{1}{4}(1-p)^{\frac{2}{3}}n^{\frac{2}{3}} -1.$ Furthermore we show that this is tight up to a multiplicative constant factor for infinitely many $p$ near the elements of $\{\frac{1}{2},\frac{2}{3},\frac{3}{4},\dots\}$ . In contrast, we show that for any $n$ -vertex graph $G$ , either $G$ or $G^c$ contains a full subgraph on $Ω(\frac{n}{\log n})$ vertices. Finally, we discuss full subgraphs of random and pseudo-random graphs, and several open problems.

preprint2016arXiv

Global Structural Properties of Random Graphs

We study two global structural properties of a graph $Γ$ , denoted AS and CFS, which arise in a natural way from geometric group theory. We study these properties in the Erdös--Rényi random graph model G(n,p), proving a sharp threshold for a random graph to have the AS property asymptotically almost surely, and giving fairly tight bounds for the corresponding threshold for CFS. As an application of our results, we show that for any constant p and any $Γ\in G(n,p)$ , the right-angled Coxeter group $W_Γ$ asymptotically almost surely has quadratic divergence and thickness of order 1, generalizing and strengthening a result of Behrstock--Hagen--Sisto.

preprint2016arXiv

Multicolour containers and the entropy of decorated graph limits

In recent breakthrough results, Saxton--Thomason and Balogh--Morris--Samotij have developed powerful theories of hypergraph containers. These theories have led to a large number of new results on transference, and on counting and characterising typical graphs in hereditary properties. In a different direction, Hatami--Janson--Szegedy proved results on the entropy of graph limits which count and characterise graphs in dense hereditary properties. In this paper, we make a threefold contribution to this area of research: 1) We generalise results of Saxton--Thomason to obtain container theorems for general, dense hereditary properties of multicoloured graphs. Our main tool is the adoption of an entropy-based framework. As corollaries, we obtain general counting, characterization and transference results. We further extend our results to cover a variety of combinatorial structures: directed graphs, oriented graphs, tournaments, multipartite graphs, multi-graphs, hypercubes and hypergraphs. 2) We generalise the results of Hatami--Janson--Szegedy on the entropy of graph limits to the setting of decorated graph limits. In particular we define a cut norm for decorated graph limits and prove compactness of the space of decorated graph limits under that norm. 3) We explore a weak equivalence between the container and graph limit approaches to counting and characterising graphs in hereditary properties. In one direction, we show how our multicolour container results may be used to recover decorated versions of the results of Hatami--Janson--Szegedy. In the other direction, we show that our decorated extensions of Hatami--Janson--Szegedy's results on graph limits imply counting and characterization applications. Similar container results were recently obtained independently by Terry.

preprint2016arXiv

Separating path systems

We study separating systems of the edges of a graph where each member of the separating system is a path. We conjecture that every $n$ -vertex graph admits a separating path system of size $O(n)$ and prove this in certain interesting special cases. In particular, we establish this conjecture for random graphs and graphs with linear minimum degree. We also obtain tight bounds on the size of a minimal separating path system in the case of trees.

preprint2016arXiv

Speed and concentration of the covering time for structured coupon collectors

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 $X_1, X_2, \ldots$ , where the $X_i$ are independent random variables with distribution given by $X$ . The covering time $T$ is the smallest integer $t\geq 0$ such that $\bigcup_{i=1}^tX_i=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.

preprint2015arXiv

Codegree thresholds for covering 3-uniform hypergraphs

Given two 3-uniform hypergraphs F and G, we say that G has an F-covering if we can cover V(G) by copies of F. The minimum codegree of G is the largest integer d such that every pair of vertices from V(G) is contained in at least d triples from E(G). Define c_2(n,F) to be the largest minimum codegree among all n-vertex 3-graphs G that contain no F-covering. This is a natural problem intermediate (but distinct) from the well-studied Turán 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.

preprint2015arXiv

Random subcube intersection graphs I: cliques and covering

We study random subcube intersection graphs, that is, graphs obtained by selecting a random collection of subcubes of a fixed hypercube $Q_d$ 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 $Q_d$ and for the appearance of s-cliques. In addition we pose some open problems.

preprint2015arXiv

The codegree threshold for 3-graphs with independent neighbourhoods

Given a family of 3-graphs $F$ , we define its codegree threshold $\mathrm{coex}(n, F)$ to be the largest number $d=d(n)$ such that there exists an $n$ -vertex 3-graph in which every pair of vertices is contained in at least $d$ 3-edges but which contains no member of $F$ as a subgraph. Let $F_{3,2}$ be the 3-graph on $\{a,b,c,d,e\}$ with 3-edges $\{abc,abd,abe,cde\}$ . In this paper, we give two proofs that $\mathrm{coex}(n, F_{3,2})= n/3 +o(n)$ , the first by a direct combinatorial argument and the second via a flag algebra computation. Information extracted from the latter proof is then used to obtain a stability result, from which in turn we derive the exact codegree threshold for all sufficiently large $n$ : $\mathrm{coex}(n, F_{3,2})= \lfloor n/3 \rfloor -1$ if $n$ is congruent to $1$ modulo $3$ , and $\lfloor n/3 \rfloor$ otherwise. In addition we determine the set of codegree-extremal configurations.

preprint2014arXiv

On percolation in Poisson graphs

Equip each point $x$ of a homogeneous Poisson process $\mathcal{P}$ on $\mathbb{R}$ with $D_x$ edge stubs, where the $D_x$ are i.i.d. positive integer-valued random variables with distribution given by $μ$ . Following the stable multi-matching scheme introduced by Deijfen, Häggstrom and Holroyd (2012), we pair off edge stubs in a series of rounds to form the edge set of an infinite component $G$ on the vertex set $\mathcal{P}$ . In this note, we answer questions of Deijfen, Holroyd and Peres (2011) and Deijfen, Häggström and Holroyd (2012) on percolation (the existence of an infinite connected component) in $G$ . We prove that percolation may occur a.s. even if $μ$ has support over odd integers. Furthermore, we show that for any $\varepsilon>0$ there exists a distribution $μ$ such that $μ(\{1\})>1-\varepsilon$ such that percolation still occurs a.s..

preprint2013arXiv

Distribution of components in the k-nearest neighbour random geometric graph for k below the connectivity threshold

Let S_{n,k} denote the random geometric graph obtained by placing points inside a square of area n according to a Poisson point process of intensity 1 and joining each such point to the k=k(n) points of the process nearest to it. In this paper we show that if Pr(S_{n,k} connected) > n^{-γ_1} then the probability that S_{n,k} contains a pair of `small' components `close' to each other is o(n^{-c_1}) (in a precise sense of `small' and 'close'), for some absolute constants γ_1>0 and c_1 >0. This answers a question of Walters. (A similar result was independently obtained by Balister.) As an application of our result, we show that the distribution of the connected components of S_{n,k} below the connectivity threshold is asymptotically Poisson.

preprint2013arXiv

On the codegree density of complete 3-graphs and related problems

Given a family of 3-graphs F its codegree threshold coex(n, F) is the largest number d=d(n) such that there exists an n-vertex 3-graph in which every pair of vertices is contained in at least d 3-edges but which contains no member of F as a subgraph. The codegree density gamma(F) is the limit of coex(n,F)/(n-2) as n tends to infinity. In this paper we generalise a construction of Czygrinow and Nagle to bound below the codegree density of complete 3-graphs: for all integers s>3, the codegree density of the complete 3-graph on s vertices K_s satisfies gamma(K_s)\geq 1-1/(s-2). We also provide constructions based on Steiner triple systems which show that if this lower bound is sharp, then we do not have stability in general. In addition we prove bounds on the codegree density for two other infinite families of 3-graphs.

preprint2013arXiv

Sperner's problem for G-independent families

Given a graph G, let Q(G) denote the collection of all independent (edge-free) sets of vertices in G. We consider the problem of determining the size of a largest antichain in Q(G). When G is the edge-less graph, this problem is resolved by Sperner's Theorem. In this paper, we focus on the case where G is the path of length n-1, proving the size of a maximal antichain is of the same order as the size of a largest layer of Q(G).

preprint2012arXiv

On applications of Razborov's flag algebra calculus to extremal 3-graph theory

In this paper, we prove several new Turán density results for 3-graphs with independent neighbourhoods. We show: π(K_4^-, C_5, F_{3,2})=12/49, π(K_4^-, F_{3,2})=5/18, and π(J_4, F_{3,2})=π(J_5, F_{3,2})=3/8, where J_t is the 3-graph consisting of a single vertex x together with a disjoint set A of size t and all $\binom{|A|}{2}$ 3-edges containing x. We also prove two Turán density results where we forbid certain induced subgraphs: π(F_{3,2}, induced K_4^-)=3/8 and π(K_5, 5-set spanning 8 edges)=3/4. The latter result is an analogue for K_5 of Razborov's result that π(K_4, 4-set spanning 1 edge)=5/9. We give several new constructions, conjectures and bounds for Turán densities of 3-graphs which should be of interest to researchers in the area. Our main tool is `Flagmatic', an implementation of Razborov's flag algebra calculus, which we are making publicly available. In a bid to make the power of Razborov's method more widely accessible, we have tried to make Flagmatic as user-friendly as possible, hoping to remove thereby the major hurdle that needs to be cleared before using the flag algebra calculus. Finally, we spend some time reflecting on the limitations of our approach, and in particular on which problems we may be unable to solve. Our discussion of the `complexity barrier' for the flag algebra calculus may be of general interest.

preprint2012arXiv

Turán H-densities for 3-graphs

Given an $r$ -graph $H$ on $h$ vertices, and a family $\mathcal{F}$ of forbidden subgraphs, we define $\ex_{H}(n, \mathcal{F})$ to be the maximum number of induced copies of $H$ in an $\mathcal{F}$ -free $r$ -graph on $n$ vertices. Then the \emph{Turán $H$ -density} of $\mathcal{F}$ is the limit \[π_{H}(\mathcal{F})= \lim_{n\rightarrow \infty}\ex_{H}(n, \mathcal{F})/\binom{n}{h}. \] This generalises the notions of \emph{Turán density} (when $H$ is an $r$ -edge), and \emph{inducibility} (when $\mathcal{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 Turán $H$ -densities for 3-graphs. In particular, we show that $π_{K_4^-}(K_4) = 16/27,$ with Turán's construction being optimal. We prove a result in a similar flavour for $K_5$ and make a general conjecture on the value of $π_{K_t^-}(K_t)$ . We also establish that $π_{4.2}(\emptyset)=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 $\vec{S}_k$ be the \emph{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 $π_{\vec{S}_3}(\emptyset)=2\sqrt3-3,$ with an iterated blow-up construction being extremal. This is related to a conjecture of Mubayi and Rödl on the Turán density of the 3-graph $C_5$ . We also determine $π_{\vec{S}_k}(\emptyset)$ when $k=4$ , and conjecture its value for general $k$ .

preprint2011arXiv

Sharpness in the k-nearest neighbours random geometric graph model

Let $S_{n,k}$ denote the random geometric graph obtained by placing points in a square box of area $n$ according to a Poisson process of intensity 1 and joining each point to its $k$ nearest neighbours. Balister, Bollobás, Sarkar and Walters conjectured that for every $0< ε<1$ and all $n$ sufficiently large there exists $C=C(ε)$ such that whenever the probability $S_{n,k}$ is connected is at least $ε$ then the probability $S_{n,k+C}$ is connected is at least $1-ε$ . In this paper we prove this conjecture. As a corollary we prove that there is a constant $C'$ such that whenever $k=k(n)$ is a sequence of integers such that the probability $S_{n,k(n)}$ is connected tends to one as $n$ tends to infinity, then for any $s(n)$ with $s(n)=o(\log n)$ , the probability that $S_{n,k(n)+C's\log \log n}$ is $s$ -connected tends to one This proves another conjecture of Balister, Bollobás, Sarkar and Walters.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Victor Falgas-Ravry

Research overview

Is this your work?

20 publications

$1$ -independent percolation on $\mathbb{Z}^2 \times K_n$

Existence thresholds and Ramsey properties of random posets

Long paths and connectivity in { $1$ }-independent random graphs

Maker-Breaker Percolation Games I: Crossing Grids

Maker-Breaker Percolation Games II: Escaping to Infinity

Full subgraphs

Global Structural Properties of Random Graphs

Multicolour containers and the entropy of decorated graph limits

Separating path systems

Speed and concentration of the covering time for structured coupon collectors

Codegree thresholds for covering 3-uniform hypergraphs

Random subcube intersection graphs I: cliques and covering

The codegree threshold for 3-graphs with independent neighbourhoods

On percolation in Poisson graphs

Distribution of components in the k-nearest neighbour random geometric graph for k below the connectivity threshold

On the codegree density of complete 3-graphs and related problems

Sperner's problem for G-independent families

On applications of Razborov's flag algebra calculus to extremal 3-graph theory

Turán H-densities for 3-graphs

Sharpness in the k-nearest neighbours random geometric graph model

See the researcher in context

Building this map preview

Victor Falgas-Ravry

Research overview

Is this your work?

20 publications

111-independent percolation on Z2×Kn\mathbb{Z}^2 \times K_nZ2×Kn​

Existence thresholds and Ramsey properties of random posets

Long paths and connectivity in {111}-independent random graphs

Maker-Breaker Percolation Games I: Crossing Grids

Maker-Breaker Percolation Games II: Escaping to Infinity

Full subgraphs

Global Structural Properties of Random Graphs

Multicolour containers and the entropy of decorated graph limits

Separating path systems

Speed and concentration of the covering time for structured coupon collectors

Codegree thresholds for covering 3-uniform hypergraphs

Random subcube intersection graphs I: cliques and covering

The codegree threshold for 3-graphs with independent neighbourhoods

On percolation in Poisson graphs

Distribution of components in the k-nearest neighbour random geometric graph for k below the connectivity threshold

On the codegree density of complete 3-graphs and related problems

Sperner's problem for G-independent families

On applications of Razborov's flag algebra calculus to extremal 3-graph theory

Turán H-densities for 3-graphs

Sharpness in the k-nearest neighbours random geometric graph model

See the researcher in context

Building this map preview

$1$ -independent percolation on $\mathbb{Z}^2 \times K_n$

Long paths and connectivity in { $1$ }-independent random graphs