Tilings in graphons

DOI10.1016/J.EJC.2020.103284MaRDI QIDQ2225467zbMATH OpenOpenAlexFDO

Authors Jan Hladký, Ping Hu, Diana Piguet

Publication date 8 February 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.03113

zbMATH Keywords

asymptotically almost sure \(F\)-tiling number of inhomogeneous random graphsfractional \(F\)-tiling

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We introduce a counterpart to the notion of vertex disjoint tilings by copy of a fixed graph F to the setting of graphons. The case F=K_2 gives the notion of matchings in graphons. We give a transference statement that allows us to switch between the finite and limit notion, and derive several favorable properties, including the LP-duality counterpart to the classical relation between the fractional vertex covers and fractional matchings/tilings, and discuss connections with property testing. As an application of our theory, we determine the asymptotically almost sure F-tiling number of inhomogeneous random graphs mathbb{G}(n,W). As another application, in an accompanying paper [Hladky, Hu, Piguet: Komlos's tiling theorem via graphon covers, preprint] we give a proof of a strengthening of a theorem of Komlos [Komlos: Tiling Tur'an Theorems, Combinatorica, 2000].

Recommendations

• Komlós's tiling theorem via graphon covers
• On Komlós' tiling theorem in random graphs
• Tilings in randomly perturbed dense graphs
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Matching polytons

Cites work

• scientific article; zbMATH DE number 4029251 (Why is no real title available?)
• A Density Corrádi–Hajnal Theorem
• An Infinite-Dimensional LP Duality Theorem
• An epsilon of room. I: Real analysis. Pages from year three of a mathematical blog
• Borel oracles. An analytical approach to constant-time algorithms
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• First steps in combinatorial optimization on graphons: matchings
• Flag algebras
• Independent sets, cliques, and colorings in graphons
• Komlós's tiling theorem via graphon covers
• Large networks and graph limits
• Limits of dense graph sequences
• Matching polytons
• Matchings on infinite graphs
• On maximal paths and circuits of graphs
• On the Minimal Density of Triangles in Graphs
• Small subsets inherit sparse \(\varepsilon\)-regularity
• Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture
• Testing properties of graphs and functions
• The Independence Ratio of Regular Graphs
• Tiling Turán theorems

Cited in

(15)

• Tilings in randomly perturbed dense graphs
• Tessellation graph characterization using rosettas
• scientific article; zbMATH DE number 5139439 (Why is no real title available?)
• Counting Tilings by Taking Walks in a Graph
• Flows on measurable spaces
• Komlós's tiling theorem via graphon covers
• Tiling algebra for constraint-based layout editing
• scientific article; zbMATH DE number 3853097 (Why is no real title available?)
• First steps in combinatorial optimization on graphons: matchings
• Independent sets, cliques, and colorings in graphons
• Tiling arbitrarily nested loops by means of the transitive closure of dependence graphs
• Matching polytons
• scientific article; zbMATH DE number 851645 (Why is no real title available?)
• Fractional isomorphism of graphons
• Graph Tilings in Incompatibility Systems

This page was built for publication: Tilings in graphons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225467)