umu.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Falgas-Ravry, Victor
Alternative names
Publications (10 of 17) Show all publications
Falgas-Ravry, V., O'Connell, K. & Uzzell, A. (2019). Multicolor containers, extremal entropy, and counting. Random structures & algorithms (Print), 54(4), 676-720
Open this publication in new window or tab >>Multicolor containers, extremal entropy, and counting
2019 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 54, no 4, p. 676-720Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Wiley-Blackwell, 2019
Keywords
entropy, extremal graph theory, hereditary property, hypergraph container method
National Category
Computer Sciences Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-161443 (URN)10.1002/rsa.20777 (DOI)000470931400005 ()
Funder
Swedish Research Council
Available from: 2019-07-10 Created: 2019-07-10 Last updated: 2019-09-05Bibliographically approved
Falgas-Ravry, V., Markström, K. & Verstraëte, J. (2018). Full subgraphs. Journal of Graph Theory, 88(3), 411-427
Open this publication in new window or tab >>Full subgraphs
2018 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 88, no 3, p. 411-427Article in journal (Refereed) Published
Keywords
extremal graph theory, graph discrepancy, graph partitions
National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-144161 (URN)10.1002/jgt.22221 (DOI)000432013200004 ()2-s2.0-85034034448 (Scopus ID)
Funder
Swedish Research Council
Available from: 2018-01-23 Created: 2018-01-23 Last updated: 2018-06-13Bibliographically approved
Behrstock, J., Falgas-Ravry, V., Hagen, M. & Susse, T. (2018). Global Structural Properties of Random Graphs. International mathematics research notices (5), 1411-1441
Open this publication in new window or tab >>Global Structural Properties of Random Graphs
2018 (English)In: International mathematics research notices, ISSN 1073-7928, E-ISSN 1687-0247, no 5, p. 1411-1441Article in journal (Refereed) Published
Abstract [en]

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 ˝os–Rényi random graph model G(n, p), proving the existence of 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 the CFS property. As an application of our results, we show that for any constant p and any ∈ 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 [8]. Indeed, we show that at a large range of densities a random right-angled Coxeter group has quadratic divergence. 1

Place, publisher, year, edition, pages
Oxford University Press, 2018
National Category
Mathematics
Research subject
Mathematics; Mathematical Statistics
Identifiers
urn:nbn:se:umu:diva-144157 (URN)10.1093/imrn/rnw287 (DOI)000441654500006 ()
Funder
Swedish Research Council
Available from: 2018-01-23 Created: 2018-01-23 Last updated: 2018-09-03Bibliographically approved
Falgas-Ravry, V. & Lo, A. (2018). Subgraphs with large minimum ℓ-degree in hypergraphs where almost all ℓ-degrees are large. The Electronic Journal of Combinatorics, 25(2), Article ID P2.18.
Open this publication in new window or tab >>Subgraphs with large minimum ℓ-degree in hypergraphs where almost all ℓ-degrees are large
2018 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 25, no 2, article id P2.18Article in journal (Refereed) Published
Abstract [en]

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

Keywords
r-uniform hypergraphs, ℓ-degree, extremal hypergraph theory
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-148836 (URN)000432169900003 ()
Available from: 2018-06-13 Created: 2018-06-13 Last updated: 2018-06-13Bibliographically approved
Falgas-Ravry, V., Pikhurko, O., Vaughan, E. & Volec, J. (2017). The codegree threshold of K_4^-. In: Drmota Michael; Kang Mihyun; Krattenthaler Christian; Nešetřil Jaroslav (Ed.), The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17): . Paper presented at EUROCOMB 2017, The European Conference on Combinatorics, Graph Theory and Applications, Vienna, Italy, August 28 - September 1, 2017 (pp. 407-413). Elsevier, 61
Open this publication in new window or tab >>The codegree threshold of K_4^-
2017 (English)In: The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17) / [ed] Drmota Michael; Kang Mihyun; Krattenthaler Christian; Nešetřil Jaroslav, Elsevier, 2017, Vol. 61, p. 407-413Conference paper, Published paper (Refereed)
Abstract [en]

The codegree threshold ex2(n, F) of a non-empty 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

ex2(n, K− 4 ) = n 4 + o(n).

This settles in the affirmative a conjecture of Nagle [20]. In addition, we obtain a stability result: for every near-extremal configurations G, there is a quasirandom tournament T on the same vertex set such that G is 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
Elsevier, 2017
Series
Electronic Notes in Discrete Mathematics, ISSN 1571-0653
Keywords
extremal combinatorics, hypergraphs, codegree treshold, flag algebras
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-144158 (URN)10.1016/j.endm.2017.06.067 (DOI)
Conference
EUROCOMB 2017, The European Conference on Combinatorics, Graph Theory and Applications, Vienna, Italy, August 28 - September 1, 2017
Funder
Swedish Research Council
Available from: 2018-01-23 Created: 2018-01-23 Last updated: 2018-06-14Bibliographically approved
Falgas–Ravry, V. & Zhao, Y. (2016). Codegree thresholds for covering 3-uniform hypergraphs. SIAM Journal on Discrete Mathematics, 30(4), 1899-1917
Open this publication in new window or tab >>Codegree thresholds for covering 3-uniform hypergraphs
2016 (English)In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 30, no 4, p. 1899-1917Article in journal (Refereed) Published
Abstract [en]

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

Keywords
3-graphs, covering, codegree, extremal
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-130142 (URN)10.1137/15M1051452 (DOI)000391960000001 ()
Available from: 2017-01-12 Created: 2017-01-12 Last updated: 2018-06-09Bibliographically approved
Falgas-Ravry, V. & Markström, K. (2016). Random subcube intersection graphs I: cliques and covering. The Electronic Journal of Combinatorics, 23(3), Article ID P3.43.
Open this publication in new window or tab >>Random subcube intersection graphs I: cliques and covering
2016 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 23, no 3, article id P3.43Article in journal (Refereed) Published
Abstract [en]

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

Keywords
Random graphs, Random intersection graphs
National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-127244 (URN)000385228700002 ()
Available from: 2016-11-14 Created: 2016-11-03 Last updated: 2018-06-09Bibliographically approved
Björklund, J., Falgas-Ravry, V. & Holmgren, C. (2015). On percolation in one-dimensional stable Poisson graphs. Electronic Communications in Probability, 20(50), 1-6
Open this publication in new window or tab >>On percolation in one-dimensional stable Poisson graphs
2015 (English)In: Electronic Communications in Probability, ISSN 1083-589X, E-ISSN 1083-589X, Vol. 20, no 50, p. 1-6Article in journal (Refereed) Published
Abstract [en]

Equip each point x of a homogeneous Poisson point process P on R with D-x edge stubs, where the D-x are i.i.d. positive integer-valued random variables with distribution given by mu. Following the stable multi-matching scheme introduced by Deijfen, Haggstrom and Holroyd [1], we pair off edge stubs in a series of rounds to form the edge set of a graph G on the vertex set P. In this note, we answer questions of Deijfen, Holroyd and Peres [2] and Deijfen, Haggstrom and Holroyd [1] on percolation (the existence of an infinite connected component) in G. We prove that percolation may occur a.s. even if mu has support over odd integers. Furthermore, we show that for any epsilon > 0, there exists a distribution mu such that mu ({1}) > 1 - epsilon, but percolation still occurs a.s..

Keywords
Poisson process, Random graph, Matching, Percolation
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:umu:diva-130143 (URN)10.1214/ECP.v20-3958 (DOI)000357151400001 ()
Available from: 2017-01-12 Created: 2017-01-12 Last updated: 2018-06-09Bibliographically approved
Falgas-Ravry, V. (2015). Sperner's Problem for G-Independent Families. Combinatorics, probability & computing, 24(3), 528-550
Open this publication in new window or tab >>Sperner's Problem for G-Independent Families
2015 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 24, no 3, p. 528-550Article in journal (Refereed) Published
Abstract [en]

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 edgeless 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 that the size of a maximal antichain is of the same order as the size of a largest layer of Q(G).

National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-106332 (URN)10.1017/S0963548314000558 (DOI)000356495300005 ()
Available from: 2015-07-16 Created: 2015-07-10 Last updated: 2018-06-07Bibliographically approved
Falgas-Ravry, V., Marchant, E., Pikhurko, O. & Vaughan, E. R. (2015). The Codegree Threshold for 3-Graphs with Independent Neighborhoods. SIAM Journal on Discrete Mathematics, 29(3), 1504-1539
Open this publication in new window or tab >>The Codegree Threshold for 3-Graphs with Independent Neighborhoods
2015 (English)In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 29, no 3, p. 1504-1539Article in journal (Refereed) Published
Abstract [en]

Given a family of 3-graphs F, we define its codegree threshold 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,F-2 be the 3-graph on {a, b, c, d, e} with 3-edges abc, abd, abe, and cde. In this paper, we give two proofs that coex(n, {F-3,F-2}) = - (1/3 + o(1))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: coex(n, {F-3,F-2}) = [n/3] - 1 if n is congruent to 1 modulo 3, and [n/3] otherwise. In addition we determine the set of codegree-extremal configurations for all sufficiently large n.

Keywords
codegree, Turan density, Turan function, 3-graphs
National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-110602 (URN)10.1137/130926997 (DOI)000362419600021 ()
Available from: 2015-10-26 Created: 2015-10-23 Last updated: 2018-06-07Bibliographically approved
Organisations

Search in DiVA

Show all publications