Umeå University's logo

umu.sePublications
Change search
Link to record
Permanent link

Direct link
Falgas-Ravry, VictorORCID iD iconorcid.org/0000-0001-8631-4745
Alternative names
Publications (10 of 30) Show all publications
Falgas-Ravry, V. (2024). On an extremal problem for locally sparse multigraphs. European journal of combinatorics (Print), 118, Article ID 103887.
Open this publication in new window or tab >>On an extremal problem for locally sparse multigraphs
2024 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 118, article id 103887Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Elsevier, 2024
National Category
Discrete Mathematics Probability Theory and Statistics
Identifiers
urn:nbn:se:umu:diva-217221 (URN)10.1016/j.ejc.2023.103887 (DOI)2-s2.0-85177206014 (Scopus ID)
Available from: 2023-11-29 Created: 2023-11-29 Last updated: 2023-11-29Bibliographically approved
Falgas-Ravry, V. & Pfenninger, V. (2023). 1-independent percolation on ℤ2×Kn. Random structures & algorithms (Print), 62(4), 887-910
Open this publication in new window or tab >>1-independent percolation on ℤ2×Kn
2023 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 62, no 4, p. 887-910Article in journal (Refereed) Published
Abstract [en]

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.).

Place, publisher, year, edition, pages
John Wiley & Sons, 2023
Keywords
extremal graph theory, locally dependent random graphs, percolation theory
National Category
Probability Theory and Statistics Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-202084 (URN)10.1002/rsa.21129 (DOI)000905090200001 ()2-s2.0-85144415026 (Scopus ID)
Funder
Swedish Research Council, 2016-03488Swedish Research Council, 2021-03687
Available from: 2023-01-03 Created: 2023-01-03 Last updated: 2023-06-16Bibliographically approved
Falgas-Ravry, V. & Sarkar, A. (2023). Bootstrap percolation in random geometric graphs. Advances in Applied Probability, 55(4), 1254-1300
Open this publication in new window or tab >>Bootstrap percolation in random geometric graphs
2023 (English)In: Advances in Applied Probability, ISSN 0001-8678, E-ISSN 1475-6064, Vol. 55, no 4, p. 1254-1300Article in journal (Refereed) Published
Abstract [en]

Following Bradonji´c and Saniee, we study a model of bootstrap percolation on the Gilbert random geometric graph on the 2-dimensional torus. In this model, the expected number of vertices of the graph is n, and the expected degree of a vertex is a log n for some fixed a>1. Each vertex is added with probability p to a set A0 of initially infected vertices. Vertices subsequently become infected if they have at least θa log n infected neighbours. Here p, θ ∈ [0, 1] are taken to be fixed constants.

We show that if θ <(1+p)/2, then a sufficiently large local outbreak leads with high probability to the infection spreading globally, with all but o(n) vertices eventually becoming infected. On the other hand, for θ >(1+p)/2, even if one adversarially infects every vertex inside a ball of radius O(√log n), with high probability the infection will spread to only o(n) vertices beyond those that were initially infected.

In addition we give some bounds on the (a, p, θ) regions ensuring the emergence of large local outbreaks or the existence of islands of vertices that never become infected. We also give a complete picture of the (surprisingly complex) behaviour of the analogous 1-dimensional bootstrap percolation model on the circle. Finally we raise a number of problems, and in particular make a conjecture on an ‘almost no percolation or almost full percolation’ dichotomy which may be of independent interest.

Place, publisher, year, edition, pages
Cambridge University Press, 2023
Keywords
bootstrap percolation, random geometric graphs, random processes
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:umu:diva-211166 (URN)10.1017/apr.2023.5 (DOI)2-s2.0-85162047124 (Scopus ID)
Funder
Swedish Research Council, 2016-03488Swedish Research Council, 2021-03687The Swedish Foundation for International Cooperation in Research and Higher Education (STINT), IB 2017-7360
Available from: 2023-07-04 Created: 2023-07-04 Last updated: 2024-01-11Bibliographically approved
Falgas-Ravry, V., Hancock, R., Strömberg, J. & Uzzell, A. (2023). Rectilinear approximation and volume estimates for hereditary bodies via [0, 1]-decorated containers. Journal of Graph Theory, 104(1), 104-132
Open this publication in new window or tab >>Rectilinear approximation and volume estimates for hereditary bodies via [0, 1]-decorated containers
2023 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 104, no 1, p. 104-132Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
John Wiley & Sons, 2023
Keywords
containers, entropy, graph limits, hereditary bodies, rectilinear approximation
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-206358 (URN)10.1002/jgt.22951 (DOI)000953626400001 ()2-s2.0-85150886932 (Scopus ID)
Available from: 2023-04-26 Created: 2023-04-26 Last updated: 2023-11-01Bibliographically approved
Falgas-Ravry, V., Pikhurko, O., Vaughan, E. & Volec, J. (2023). The codegree threshold of K-4. Journal of the London Mathematical Society, 107(5), 1660-1691
Open this publication in new window or tab >>The codegree threshold of K-4
2023 (English)In: Journal of the London Mathematical Society, ISSN 0024-6107, E-ISSN 1469-7750, Vol. 107, no 5, p. 1660-1691Article in journal (Refereed) Published
Abstract [en]

The codegree threshold ex2 (n, F) of a 3-graph F is the minimum d = d(n) such that every 3-graph on n vertices in which every pair of vertices is contained in at least d + 1 edges contains a copy of F as a subgraph. We study ex2 (n, F) when F = K-4 , the 3-graph on 4 vertices with 3 edges. Using flag algebra techniques, we prove that if n is sufficiently large, then

ex2 (n, K-4)⩽ (n + 1)/4.

This settles in the affirmative a conjecture of Nagle [Congressus Numerantium, 1999, pp. 119-128]. In addition, we obtain a stability result: for every near-extremal configuration G, there is a quasirandom tournament T on the same vertex set such that G is o(n3)-close in the edit distance to the 3-graph C(T) whose edges are the cyclically oriented triangles from T. For infinitely many values of n, we are further able to determine ex2(n, K-4) exactly and to show that tournament-based constructions C(T) are extremal for those values of n.

Place, publisher, year, edition, pages
John Wiley & Sons, 2023
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-205362 (URN)10.1112/jlms.12722 (DOI)000935215000001 ()2-s2.0-85148342895 (Scopus ID)
Funder
EU, European Research Council, 101020255Swedish Research Council, 2016‐03488Swedish Research Council, 2021‐03687
Available from: 2023-03-29 Created: 2023-03-29 Last updated: 2023-07-14Bibliographically approved
Day, A. N., Falgas-Ravry, V. & Treglown, A. (2022). Extremal problems for multigraphs. Journal of combinatorial theory. Series B (Print), 154, 1-48
Open this publication in new window or tab >>Extremal problems for multigraphs
2022 (English)In: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 154, p. 1-48Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Academia Press, 2022
Keywords
Multigraphs, Transcendental numbers, Turán-type problems
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-190943 (URN)10.1016/j.jctb.2021.12.003 (DOI)000751659000001 ()2-s2.0-85121584522 (Scopus ID)
Funder
Swedish Research Council, 2016-03488
Available from: 2022-01-05 Created: 2022-01-05 Last updated: 2023-09-05Bibliographically approved
Behrstock, J., Falgas-Ravry, V. & Susse, T. (2022). Square percolation and the threshold for quadratic divergence in random right-angled Coxeter groups. Random structures & algorithms (Print), 60(4), 594-630
Open this publication in new window or tab >>Square percolation and the threshold for quadratic divergence in random right-angled Coxeter groups
2022 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 60, no 4, p. 594-630Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
John Wiley & Sons, 2022
Keywords
divergence, geometric group theory, random graphs, random groups, right-angled Coxeter groups, square percolation
National Category
Discrete Mathematics Probability Theory and Statistics
Identifiers
urn:nbn:se:umu:diva-188161 (URN)10.1002/rsa.21049 (DOI)000698698600001 ()2-s2.0-85115638478 (Scopus ID)
Available from: 2021-10-06 Created: 2021-10-06 Last updated: 2022-07-20Bibliographically approved
Day, A. N. & Falgas-Ravry, V. (2021). Maker-Breaker percolation games I: crossing grids. Combinatorics, probability & computing, 30(2), 200-227
Open this publication in new window or tab >>Maker-Breaker percolation games I: crossing grids
2021 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 30, no 2, p. 200-227Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Cambridge University Press, 2021
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-187583 (URN)10.1017/S0963548320000097 (DOI)000625213500003 ()2-s2.0-85087372127 (Scopus ID)
Funder
Swedish Research Council, 2016-03488
Available from: 2021-09-17 Created: 2021-09-17 Last updated: 2021-09-17Bibliographically approved
Day, A. N. & Falgas-Ravry, V. (2021). Maker-breaker percolation games II: Escaping to infinity. Journal of combinatorial theory. Series B (Print), 151, 482-508
Open this publication in new window or tab >>Maker-breaker percolation games II: Escaping to infinity
2021 (English)In: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 151, p. 482-508Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Elsevier, 2021
Keywords
Maker-Breaker games, Shannon switching game, Positional games
National Category
Computer Sciences Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-191614 (URN)10.1016/j.jctb.2020.06.006 (DOI)000702280800020 ()2-s2.0-85087368785 (Scopus ID)
Funder
Swedish Research Council, 2016-03488
Available from: 2022-01-20 Created: 2022-01-20 Last updated: 2022-01-20Bibliographically approved
Falgas-Ravry, V., Markström, K. & Zhao, Y. (2021). Triangle-degrees in graphs and tetrahedron coverings in 3-graphs. Combinatorics, probability & computing, 30(2), 175-199
Open this publication in new window or tab >>Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
2021 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 30, no 2, p. 175-199Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Cambridges Institutes Press, 2021
National Category
Discrete Mathematics Computer Sciences
Identifiers
urn:nbn:se:umu:diva-187528 (URN)10.1017/S0963548320000061 (DOI)000625213500002 ()2-s2.0-85092279191 (Scopus ID)
Funder
Swedish Research Council, 2014-4897, 2016-03488
Available from: 2021-09-15 Created: 2021-09-15 Last updated: 2021-09-15Bibliographically approved
Projects
Extremal problems for codegree and discrepancy [2016-03488_VR]; Umeå University
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0001-8631-4745

Search in DiVA

Show all publications