Matching polytons

MaRDI QIDQ2278115zbMATH OpenFDO

Authors Martin Doležal, Jan Hladký

Publication date 9 December 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.06958, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i4p38

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

fractional vertex covers in a graphon

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Hladky, Hu, and Piguet [Tilings in graphons, preprint] introduced the notions of matching and fractional vertex covers in graphons. These are counterparts to the corresponding notions in finite graphs. Combinatorial optimization studies the structure of the matching polytope and the fractional vertex cover polytope of a graph. Here, in analogy, we initiate the study of the structure of the set of all matchings and of all fractional vertex covers in a graphon. We call these sets the matching polyton and the fractional vertex cover polyton. We also study properties of matching polytons and fractional vertex cover polytons along convergent sequences of graphons. As an auxiliary tool of independent interest, we prove that a graphon is $r$-partite if and only if it contains no graph of chromatic number $r+1$. This in turn gives a characterization of bipartite graphons as those having a symmetric spectrum.

Recommendations

• First steps in combinatorial optimization on graphons: matchings
• Independent sets, cliques, and colorings in graphons
• Tilings in graphons
• Matchings on infinite graphs
• Fractional perfect \(b\)-matching polytopes. I: General theory

Cites work

• Blow-up lemma
• Cliques in dense inhomogeneous random graphs
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• First steps in combinatorial optimization on graphons: matchings
• Flag algebras
• Hamiltonian circuits in random graphs
• Komlós's tiling theorem via graphon covers
• Large networks and graph limits
• Limits of dense graph sequences
• On maximal paths and circuits of graphs
• Polyhedral combinatorics and combinatorial optimization
• Regularity partitions and the topology of graphons
• Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture
• The large deviation principle for the Erdős-Rényi random graph
• Tiling Turán theorems
• Tilings in graphons

Cited in

(6)

• Characteristic power series of graph limits
• Tilings in graphons
• Relating the cut distance and the weak* topology for graphons
• First steps in combinatorial optimization on graphons: matchings
• Independent sets, cliques, and colorings in graphons
• Approximating fractionally isomorphic graphons

This page was built for publication: Matching polytons

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