Quasi-randomness of graph balanced cut properties

Details Quasi-randomness of graph balanced cut properties Quasi-randomness of graph balanced cut properties

2010-09-13

arxiv.org/abs/1009.2307v3

Mathematics

Combinatorics

20 pages, 1 figures

Scientific paper

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 $k \ge 2$ be a fixed integer, $\alpha_1,...,\alpha_k$ be positive reals satisfying $\sum_{i} \alpha_i = 1$ and $(\alpha_1,..., \alpha_k) \neq (1/k,...,1/k)$, and $G$ be a graph on $n$ vertices. If for every partition of the vertices of $G$ into sets $V_1,..., V_k$ of size $\alpha_1 n,..., \alpha_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,..., 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.

Affiliated with

Also associated with

No associations

Rating

Quasi-randomness of graph balanced cut properties does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quasi-randomness of graph balanced cut properties, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quasi-randomness of graph balanced cut properties will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-337218