تسجيل الدخول

تسجيل

Goodman,s Formula

المؤلف:  Goodman, A. W.

المصدر:  "On Sets of Acquaintances and Strangers at Any Party." Amer. Math. Monthly 66

الجزء والصفحة:  ...

28-3-2022

2592

Goodman's Formula

A two-coloring of a complete graph  of  nodes which contains exactly the number of monochromatic forced triangles and no more (i.e., a minimum of  where  and  are the number of red and blue triangles) is called an extremal graph. Goodman (1959) showed that for an extremal graph,

{1/3m(m-1)(m-2) for n=2m; 2/3m(m-1)(4m+1) for n=4m+1; 2/3m(m+1)(4m-1) for n=4m+3. " src="https://mathworld.wolfram.com/images/equations/GoodmansFormula/NumberedEquation1.svg" style="height:93px; width:292px" />

(1)

Schwenk (1972) rewrote the equation in the form

(2)

where  is a binomial coefficient and  is the floor function.

---

REFERENCES

Goodman, A. W. "On Sets of Acquaintances and Strangers at Any Party." Amer. Math. Monthly 66, 778-783, 1959.

Schwenk, A. J. "Acquaintance Party Problem." Amer. Math. Monthly 79, 1113-1117, 1972.