Partitioning problems via random processes

DOI10.1112/JLMS.70010MaRDI QIDQ6658754zbMATH OpenFDO

Authors Michael Anastos, Oliver Cooley, Mihyun Kang, Matthew Kwan

Publication date 8 January 2025

Published in Journal of the London Mathematical Society. Second Series (Search for Journal in Brave)

Copyright license File:Creative commons license with attribution.png Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1112/JLMS.70010

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Recommendations

• Majority colorings of sparse digraphs
• Internal partitions of regular graphs
• Partitioning random graphs into monochromatic components
• On generalised majority edge-colourings of graphs
• Generalized Majority Colourings of Digraphs

Cites work

• (Dis)assortative partitions on random regular graphs
• A constructive proof of the general Lovász local lemma
• A multivariate Berry-Esseen theorem with explicit constants
• Almost all Steiner triple systems have perfect matchings
• Asymptotically almost every \(2r\)-regular graph has an internal partition
• Best response dynamics on random graphs
• Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
• Dismantling Sparse Random Graphs
• Epidemics and rumours in complex networks.
• Extremal cuts of sparse random graphs
• Friendly bisections of random graphs
• Generalized Majority Colourings of Digraphs
• scientific article; zbMATH DE number 4191687 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1933255 (Why is no real title available?)
• scientific article; zbMATH DE number 944226 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• scientific article; zbMATH DE number 3043546 (Why is no real title available?)
• Integer Linear Programs and Local Search for Max-Cut
• Internal partitions of regular graphs
• Linear bound for majority colourings of digraphs
• Local max-cut in smoothed polynomial time
• Local minima in disordered mean-field ferromagnets
• Local optima of the Sherrington-Kirkpatrick Hamiltonian
• Majority choosability of countable graphs
• Majority choosability of digraphs
• Majority colorings of sparse digraphs
• Majority colourings of digraphs
• On a packing and covering problem
• On the independence number of random graphs
• On the max-cut of sparse random graphs
• Opinion exchange dynamics
• Problems and results on judicious partitions
• Random Graphs
• Random graphs.
• Settling the complexity of local max-cut (almost) completely
• Simple Local Search Problems that are Hard to Solve
• Smoothed complexity of local max-cut and binary max-CSP
• Subgraphs of random graphs with specified degrees
• The Accuracy of the Gaussian Approximation to the Sum of Independent Variates
• The probabilistic method
• The probability that a random multigraph is simple. II
• The rank of random graphs
• Unfriendly partitions of a graph
• Zero-temperature dynamics in the dilute Curie-Weiss model

Cited in

(1)

• A note on digraph splitting

This page was built for publication: Partitioning problems via random processes

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