Quasi-randomness of graph balanced cut properties

DOI10.1002/RSA.20384MaRDI QIDQ2909245zbMATH OpenOpenAlexFDO

Authors Hao Huang, Choongbum Lee

Publication date 30 August 2012

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

cut propertiespseudo-random graphsquasi-random graphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Quasi-random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi-randomness of graphs. Let $kge2$ be a fixed integer, $alph{a}_1,\mathrm{...},alph{a}_k$ be positive reals satisfying $su{m}_{i}alph{a}_i=1$ and $(alph{a}_1,\mathrm{...},alph{a}_k)eq(1/k,\mathrm{...},1/k)$, and $G$ be a graph on $n$ vertices. If for every partition of the vertices of $G$ into sets $V_1,\mathrm{...},V_k$ of size $alph{a}_{1}n,\mathrm{...},alph{a}_{k}n$, the number of complete graphs on $k$ vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi-random. However, the method of quasi-random hypergraphs they used did not provide enough information to resolve the case $(1/k,\mathrm{...},1/k)$ for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi-random. Janson also posed the same question in his study of quasi-randomness under the framework of graph limits. In this paper, we positively answer their question.

Recommendations

• The quasi-randomness of hypergraph cut properties
• Quasi-randomness and the distribution of copies of a fixed graph
• Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets
• Weak quasi-randomness for uniform hypergraphs
• scientific article; zbMATH DE number 747030

Cites work

• A Certain Class of Incidence Matrices
• Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs
• scientific article; zbMATH DE number 4099367 (Why is no real title available?)
• Probability Inequalities for Sums of Bounded Random Variables
• Quasi-random graphs
• Quasi-random graphs and graph limits
• Quasi-random hypergraphs
• Quasi-Random Set Systems
• Quasi-random tournaments
• The quasi-randomness of hypergraph cut properties
• Weighted sums of certain dependent random variables

Cited in

(11)

• Balanced cut approximation in random geometric graphs
• Bipartite subgraphs and quasi-randomness
• More on quasi-random graphs, subgraph counts and graph limits
• Quasi-random graphs of given density and Ramsey numbers
• Quasi-random oriented graphs
• The quasi-randomness of hypergraph cut properties
• Forcing quasirandomness with triangles
• scientific article; zbMATH DE number 747030 (Why is no real title available?)
• Quasirandom graphs and the pantograph equation
• Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets
• Quasirandomness in hypergraphs

This page was built for publication: Quasi-randomness of graph balanced cut properties

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