Concentration of maximum degree in random planar graphs

DOI10.1016/J.JCTB.2022.05.005MaRDI QIDQ2673490zbMATH OpenOpenAlexFDO

Authors Mihyun Kang, Michael Missethan

Publication date 10 June 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

balls into binsmaximum degreePrüfer sequencerandom graphsrandom planar graphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Let $P(n,m)$ be a graph chosen uniformly at random from the class of all planar graphs on vertex set $[n]:=left1,ldots,night$ with $m=m(n)$ edges. We show that in the sparse regime, when $m/nleq1$, with high probability the maximum degree of $P(n,m)$ takes at most two different values. In contrast, this is not true anymore in the dense regime, when $m/n>1$, where the maximum degree of $P(n,m)$ is not concentrated on any subset of $[n]$ with bounded size.

Recommendations

• The maximum degree of random planar graphs
• The maximum degree of random planar graphs
• On the Maximum Degree of a Random Planar Graph
• On the degree distribution of random planar graphs
• Random planar graphs with bounds on the maximum and minimum degrees

Cites work

• 3-Connected Cores In Random Planar Graphs
• A course in combinatorics.
• Asymptotic enumeration and limit laws for graphs of fixed genus
• Asymptotic enumeration and limit laws of planar graphs
• Degree distribution in random planar graphs
• Degree sequences of random graphs
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• Further results on random cubic planar graphs
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3548141 (Why is no real title available?)
• scientific article; zbMATH DE number 1301967 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 6319745 (Why is no real title available?)
• scientific article; zbMATH DE number 4183464 (Why is no real title available?)
• Invitation to discrete mathematics
• Limit laws of planar maps with prescribed vertex degrees
• Longest and shortest cycles in random planar graphs
• Maximal biconnected subgraphs of random planar graphs
• On the Asymptotic Behavior of Degrees of Vertices in a Random Graph
• On the chromatic index of almost all graphs
• On the degree distribution of random planar graphs
• On the diameter of random planar graphs
• On the maximum degree in a random tree
• On the Maximum Degree of a Random Planar Graph
• On the Number of Edges in Random Planar Graphs
• On the probability of planarity of a random graph near the critical point
• Paths in graphs
• Pattern occurrences in random planar maps
• Phase transitions in graphs on orientable surfaces
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Random graphs on surfaces
• Random planar graphs
• Random planar graphs with n nodes and a fixed number of edges
• Random planar graphs with given average degree
• The birth of the giant component
• The degree sequence of a random graph. I. The models
• The distribution of the maximum degree of a random graph
• The Evolution of Random Graphs on Surfaces
• The maximum degree in a random tree and related problems
• The maximum degree of a random graph
• The maximum degree of random planar graphs
• The random planar graph process
• The Structure of a Random Graph at the Point of the Phase Transition
• Two critical periods in the evolution of random planar graphs
• Uniform random sampling of planar graphs in linear time
• Vertices of given degree in a random graph

Cited in

(8)

• The mesoscopic geometry of sparse random maps
• The maximum degree of random planar graphs
• On the Maximum Degree of a Random Planar Graph
• Maximum planar subgraphs in dense graphs
• Sharp concentration of the number of submaps in random planar triangulations
• The maximum degree of random planar graphs
• Random planar graphs with bounds on the maximum and minimum degrees
• Sparse random planar graphs

This page was built for publication: Concentration of maximum degree in random planar graphs

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