umu.sePublications

Please wait ... |

Link to record
http://umu.diva-portal.org/smash/person.jsf?pid=authority-person:64927 $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt129_recordDirectLink",{id:"formSmash:upper:j_idt129:recordDirectLink",widgetVar:"widget_formSmash_upper_j_idt129_recordDirectLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt129_j_idt131",{id:"formSmash:upper:j_idt129:j_idt131",widgetVar:"widget_formSmash_upper_j_idt129_j_idt131",target:"formSmash:upper:j_idt129:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Direct link

Falgas-Ravry, Victor

Open this publication in new window or tab >>Multicolor containers, extremal entropy, and counting### Falgas-Ravry, Victor

### O'Connell, Kelly

### Uzzell, Andrew

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_0_j_idt195_some",{id:"formSmash:j_idt191:0:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_0_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_0_j_idt195_otherAuthors",{id:"formSmash:j_idt191:0:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_0_j_idt195_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_0_j_idt195_j_idt366",{id:"formSmash:j_idt191:0:j_idt195:j_idt366",widgetVar:"widget_formSmash_j_idt191_0_j_idt195_j_idt366",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_0_j_idt195_j_idt372",{id:"formSmash:j_idt191:0:j_idt195:j_idt372",widgetVar:"widget_formSmash_j_idt191_0_j_idt195_j_idt372",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_0_j_idt195_j_idt378",{id:"formSmash:j_idt191:0:j_idt195:j_idt378",widgetVar:"widget_formSmash_j_idt191_0_j_idt195_j_idt378",multiple:true});
#####

##### Funder

Swedish Research Council
Available from: 2019-07-10 Created: 2019-07-10 Last updated: 2019-09-05Bibliographically approved

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

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.

Open this publication in new window or tab >>Full subgraphs### Falgas-Ravry, Victor

### Markström, Klas

### Verstraëte, Jacques

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_1_j_idt195_some",{id:"formSmash:j_idt191:1:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_1_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_1_j_idt195_otherAuthors",{id:"formSmash:j_idt191:1:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_1_j_idt195_otherAuthors",multiple:true}); 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)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_1_j_idt195_j_idt366",{id:"formSmash:j_idt191:1:j_idt195:j_idt366",widgetVar:"widget_formSmash_j_idt191_1_j_idt195_j_idt366",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_1_j_idt195_j_idt372",{id:"formSmash:j_idt191:1:j_idt195:j_idt372",widgetVar:"widget_formSmash_j_idt191_1_j_idt195_j_idt372",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_1_j_idt195_j_idt378",{id:"formSmash:j_idt191:1:j_idt195:j_idt378",widgetVar:"widget_formSmash_j_idt191_1_j_idt195_j_idt378",multiple:true});
#####

##### Funder

Swedish Research Council
Available from: 2018-01-23 Created: 2018-01-23 Last updated: 2018-06-13Bibliographically approved

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

University of California-San Diego.

Open this publication in new window or tab >>Global Structural Properties of Random Graphs### Behrstock, Jason

### Falgas-Ravry, Victor

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Hagen, Mark

### Susse, Tim

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_2_j_idt195_some",{id:"formSmash:j_idt191:2:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_2_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_2_j_idt195_otherAuthors",{id:"formSmash:j_idt191:2:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_2_j_idt195_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_2_j_idt195_j_idt366",{id:"formSmash:j_idt191:2:j_idt195:j_idt366",widgetVar:"widget_formSmash_j_idt191_2_j_idt195_j_idt366",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_2_j_idt195_j_idt372",{id:"formSmash:j_idt191:2:j_idt195:j_idt372",widgetVar:"widget_formSmash_j_idt191_2_j_idt195_j_idt372",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_2_j_idt195_j_idt378",{id:"formSmash:j_idt191:2:j_idt195:j_idt378",widgetVar:"widget_formSmash_j_idt191_2_j_idt195_j_idt378",multiple:true});
#####

##### Funder

Swedish Research Council
Available from: 2018-01-23 Created: 2018-01-23 Last updated: 2018-09-03Bibliographically approved

Lehman College, CUNY.

University of Cambridge.

University of Nebraska-Lincoln.

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

Open this publication in new window or tab >>Subgraphs with large minimum ℓ-degree in hypergraphs where almost all ℓ-degrees are large### Falgas-Ravry, Victor

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Lo, Allan

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_3_j_idt195_some",{id:"formSmash:j_idt191:3:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_3_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_3_j_idt195_otherAuthors",{id:"formSmash:j_idt191:3:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_3_j_idt195_otherAuthors",multiple:true}); 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]

##### Place, publisher, year, edition, pages

N.J. Calkin and H.S. Wilf, 2018
##### Keywords

r-uniform hypergraphs, ℓ-degree, extremal hypergraph theory
##### National Category

Discrete Mathematics
##### Identifiers

urn:nbn:se:umu:diva-148836 (URN)10.37236/6553 (DOI)000432169900003 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_3_j_idt195_j_idt366",{id:"formSmash:j_idt191:3:j_idt195:j_idt366",widgetVar:"widget_formSmash_j_idt191_3_j_idt195_j_idt366",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_3_j_idt195_j_idt372",{id:"formSmash:j_idt191:3:j_idt195:j_idt372",widgetVar:"widget_formSmash_j_idt191_3_j_idt195_j_idt372",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_3_j_idt195_j_idt378",{id:"formSmash:j_idt191:3:j_idt195:j_idt378",widgetVar:"widget_formSmash_j_idt191_3_j_idt195_j_idt378",multiple:true});
#####

Available from: 2018-06-13 Created: 2018-06-13 Last updated: 2020-03-11Bibliographically approved

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.

Open this publication in new window or tab >>The codegree threshold of K_4^-### Falgas-Ravry, Victor

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Pikhurko, Oleg

### Vaughan, Emil

### Volec, Jan

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_4_j_idt195_some",{id:"formSmash:j_idt191:4:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_4_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_4_j_idt195_otherAuthors",{id:"formSmash:j_idt191:4:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_4_j_idt195_otherAuthors",multiple:true}); 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]

##### 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
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_4_j_idt195_j_idt366",{id:"formSmash:j_idt191:4:j_idt195:j_idt366",widgetVar:"widget_formSmash_j_idt191_4_j_idt195_j_idt366",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_4_j_idt195_j_idt372",{id:"formSmash:j_idt191:4:j_idt195:j_idt372",widgetVar:"widget_formSmash_j_idt191_4_j_idt195_j_idt372",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_4_j_idt195_j_idt378",{id:"formSmash:j_idt191:4:j_idt195:j_idt378",widgetVar:"widget_formSmash_j_idt191_4_j_idt195_j_idt378",multiple:true});
#####

##### Funder

Swedish Research Council
Available from: 2018-01-23 Created: 2018-01-23 Last updated: 2018-06-14Bibliographically approved

University of Warwick.

Center for Discrete Mathematics, University of London.

McGill University.

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.

Open this publication in new window or tab >>Codegree thresholds for covering 3-uniform hypergraphs### Falgas–Ravry, Victor

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Zhao, Yi

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_5_j_idt195_some",{id:"formSmash:j_idt191:5:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_5_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_5_j_idt195_otherAuthors",{id:"formSmash:j_idt191:5:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_5_j_idt195_otherAuthors",multiple:true}); 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]

##### Keywords

3-graphs, covering, codegree, extremal
##### National Category

Discrete Mathematics
##### Identifiers

urn:nbn:se:umu:diva-130142 (URN)10.1137/15M1051452 (DOI)000391960000001 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_5_j_idt195_j_idt366",{id:"formSmash:j_idt191:5:j_idt195:j_idt366",widgetVar:"widget_formSmash_j_idt191_5_j_idt195_j_idt366",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_5_j_idt195_j_idt372",{id:"formSmash:j_idt191:5:j_idt195:j_idt372",widgetVar:"widget_formSmash_j_idt191_5_j_idt195_j_idt372",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_5_j_idt195_j_idt378",{id:"formSmash:j_idt191:5:j_idt195:j_idt378",widgetVar:"widget_formSmash_j_idt191_5_j_idt195_j_idt378",multiple:true});
#####

Available from: 2017-01-12 Created: 2017-01-12 Last updated: 2018-06-09Bibliographically approved

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.

Open this publication in new window or tab >>Random subcube intersection graphs I: cliques and covering### Falgas-Ravry, Victor

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Markström, Klas

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_6_j_idt195_some",{id:"formSmash:j_idt191:6:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_6_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_6_j_idt195_otherAuthors",{id:"formSmash:j_idt191:6:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_6_j_idt195_otherAuthors",multiple:true}); 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]

##### Keywords

Random graphs, Random intersection graphs
##### National Category

Mathematics
##### Identifiers

urn:nbn:se:umu:diva-127244 (URN)000385228700002 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_6_j_idt195_j_idt366",{id:"formSmash:j_idt191:6:j_idt195:j_idt366",widgetVar:"widget_formSmash_j_idt191_6_j_idt195_j_idt366",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_6_j_idt195_j_idt372",{id:"formSmash:j_idt191:6:j_idt195:j_idt372",widgetVar:"widget_formSmash_j_idt191_6_j_idt195_j_idt372",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_6_j_idt195_j_idt378",{id:"formSmash:j_idt191:6:j_idt195:j_idt378",widgetVar:"widget_formSmash_j_idt191_6_j_idt195_j_idt378",multiple:true});
#####

Available from: 2016-11-14 Created: 2016-11-03 Last updated: 2018-06-09Bibliographically approved

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 a number of open problems.

Open this publication in new window or tab >>On percolation in one-dimensional stable Poisson graphs### Björklund, Johan

### Falgas-Ravry, Victor

### Holmgren, Cecilia

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_7_j_idt195_some",{id:"formSmash:j_idt191:7:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_7_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_7_j_idt195_otherAuthors",{id:"formSmash:j_idt191:7:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_7_j_idt195_otherAuthors",multiple:true}); 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]

##### 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 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_7_j_idt195_j_idt366",{id:"formSmash:j_idt191:7:j_idt195:j_idt366",widgetVar:"widget_formSmash_j_idt191_7_j_idt195_j_idt366",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_7_j_idt195_j_idt372",{id:"formSmash:j_idt191:7:j_idt195:j_idt372",widgetVar:"widget_formSmash_j_idt191_7_j_idt195_j_idt372",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_7_j_idt195_j_idt378",{id:"formSmash:j_idt191:7:j_idt195:j_idt378",widgetVar:"widget_formSmash_j_idt191_7_j_idt195_j_idt378",multiple:true});
#####

Available from: 2017-01-12 Created: 2017-01-12 Last updated: 2018-06-09Bibliographically approved

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

Open this publication in new window or tab >>Sperner's Problem for G-Independent Families### Falgas-Ravry, Victor

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_8_j_idt195_some",{id:"formSmash:j_idt191:8:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_8_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_8_j_idt195_otherAuthors",{id:"formSmash:j_idt191:8:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_8_j_idt195_otherAuthors",multiple:true}); 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]

##### National Category

Discrete Mathematics
##### Identifiers

urn:nbn:se:umu:diva-106332 (URN)10.1017/S0963548314000558 (DOI)000356495300005 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_8_j_idt195_j_idt366",{id:"formSmash:j_idt191:8:j_idt195:j_idt366",widgetVar:"widget_formSmash_j_idt191_8_j_idt195_j_idt366",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_8_j_idt195_j_idt372",{id:"formSmash:j_idt191:8:j_idt195:j_idt372",widgetVar:"widget_formSmash_j_idt191_8_j_idt195_j_idt372",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_8_j_idt195_j_idt378",{id:"formSmash:j_idt191:8:j_idt195:j_idt378",widgetVar:"widget_formSmash_j_idt191_8_j_idt195_j_idt378",multiple:true});
#####

Available from: 2015-07-16 Created: 2015-07-10 Last updated: 2018-06-07Bibliographically approved

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

Open this publication in new window or tab >>The Codegree Threshold for 3-Graphs with Independent Neighborhoods### Falgas-Ravry, Victor

### Marchant, Edward

### Pikhurko, Oleg

### Vaughan, Emil R.

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_9_j_idt195_some",{id:"formSmash:j_idt191:9:j_idt195:some",widgetVar:"widget_formSmash_j_idt191_9_j_idt195_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_9_j_idt195_otherAuthors",{id:"formSmash:j_idt191:9:j_idt195:otherAuthors",widgetVar:"widget_formSmash_j_idt191_9_j_idt195_otherAuthors",multiple:true}); 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]

##### Keywords

codegree, Turan density, Turan function, 3-graphs
##### National Category

Mathematics
##### Identifiers

urn:nbn:se:umu:diva-110602 (URN)10.1137/130926997 (DOI)000362419600021 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_9_j_idt195_j_idt366",{id:"formSmash:j_idt191:9:j_idt195:j_idt366",widgetVar:"widget_formSmash_j_idt191_9_j_idt195_j_idt366",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_9_j_idt195_j_idt372",{id:"formSmash:j_idt191:9:j_idt195:j_idt372",widgetVar:"widget_formSmash_j_idt191_9_j_idt195_j_idt372",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt191_9_j_idt195_j_idt378",{id:"formSmash:j_idt191:9:j_idt195:j_idt378",widgetVar:"widget_formSmash_j_idt191_9_j_idt195_j_idt378",multiple:true});
#####

Available from: 2015-10-26 Created: 2015-10-23 Last updated: 2018-06-07Bibliographically approved

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics. Vanderbilt Univ, Dept Math, Nashville, TN 37240 USA.

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.