Multiplicities of subgraphs
type: Item
instance of: scholarly article
title: Multiplicities of subgraphs
zbMATH Open document ID: 0846.05061
DOI: 10.1007/BF01300130
author: Chris Jagger
author: P. Št'ovíček
author: Andrew Thomason
published in: Combinatorica
publication date: 1996-06-23T00:00:00Z
review text: To each graph \(H\) on \(n\) vertices we may associate a 2-coloring of the edges of the complete graph \(K_n\) by taking the edges of \(H\) to be one color class and the edges of its complement \(\overline H\) to be the other. Given a coloring \(H\), we define \(c(G; H)\) to be the proportion of the copies of \(G\) in \(K_n\) which are monochromatic and \(c(G; n)\) to be the minimum of \(c(G; H)\) over all colorings \(H\) of \(K_n\). It is not difficult to show that \(c(G; n)\) has a limit as \(n\to \infty\), which we denote by \(c(G)\). The average value of \(c(G; H)\) over all graphs \(H\) is \(2^{1- e(G)}\); hence, \(c(G)\leq 2^{1- e(G)}\). A graph \(G\) is said to be common if the equality holds and uncommon if the strict inequality holds. The authors prove several interesting results about these concepts including Theorem 8: The even wheel \(W_{2k}\) is common for \(k\geq 2\). And their main result is Theorem 12: Every graph containing \(K_4\) is uncommon.
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 878266
zbMATH Keywords: common graph
zbMATH Keywords: coloring
zbMATH Keywords: wheel
reviewed by: Jack E. Graver
MaRDI profile type: Publication
cites work: On the Ramsey multiplicities of graphs—problems and recent results
cites work: Q5724802
cites work: On Subgraphs of the Complete Bipartite Graph
cites work: Supersaturated graphs and hypergraphs
cites work: 2-colorings of complete graphs with a small number of monochromatic \(K_ 4\) subgraphs
cites work: Sur le problème de Goodman pour les quadrangles et la majoration des nombres de Ramsey
cites work: On Sets of Acquaintances and Strangers at any Party
cites work: Blue-Empty Chromatic Graphs
cites work: Cycles in graphs and functional inequalities
cites work: A correlation inequality for bipartite graphs
cites work: Inequalities for functionals generated by bipartite graphs
cites work: A Disproof of a Conjecture of Erdős in Ramsey Theory
Recommended article: On the Profile of Multiplicities of Complete Subgraphs
Recommended article: Domination subdivision and domination multisubdivision numbers of graphs
Recommended article: Total domination multisubdivision number of a graph
Recommended article: Supersaturation for subgraph counts
Recommended article: Graphs with many copies of a given subgraph
Recommended article: On the number of connected subgraphs of graphs
Recommended article: Counting subgraphs via homomorphisms
Recommended article: Counting Subgraphs via Homomorphisms
Recommended article: Combinatorial Geometry and Graph Theory
Recommended article: Q4697562
description: scientific article; zbMATH DE number 878266