Variations on Ramsey numbers and minimum numbers of monochromatic triangles in line $2$-colorings of configurations

Jamie Bishop, Rebekah Kuss, Benjamin Peet

Abstract


This paper begins by exploring some old and new results about Ramsey numbers and minimum numbers of monochromatic triangles in 2-colorings of complete graphs, both in the disjoint and non-disjoint cases. We then extend the theory, by defining line 2-colorings of configurations of points and lines and considering the minimum number of non-disjoint monochromatic triangles. We compute specific examples for notable symmetric v3 configurations before considering a general result regarding the addition or connected sum of configurations through incidence switches. The paper finishes by considering the maximal number of mutually intersecting lines and how this relates to the minimum number of triangles given a line 2-coloring of a symmetric v3 configuration.

Keywords


Ramsey theory, configurations, colorings

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2023.11.2.8

References

A. Betten, G. Brinkmann, and T. Pisanski. Counting symmetric configurations v3. Discrete Applied Mathematics, 99(1-3):331–338, 2000.

M. Boben. Irreducible (v3) configurations and graphs. Discrete mathematics, 307(3-5):331–344, 2007.

M. Bras-Amoros and K. Stokes. The semigroup of combinatorial configurations. In Semigroup forum, volume 84, pages 91–96. Springer, 2012.

S.A. Burr, P. Erdos, and J.H. Spencer. Ramsey theorems for multiple copies of graphs. Transactions of the American Mathematical Society, 209:87–99, 1975.

S.A Burr and V. Rosta. On the Ramsey multiplicities of graphs—problems and recent results. Journal of Graph Theory, 4(4):347–361, 1980.

D. Conlon. On the Ramsey multiplicity of complete graphs. arXiv preprint arXiv:0711.4999, 2007.

H.S.M. Coxeter. Configurations and maps. In Bulletin of the Mathematical Society, volume 53, pages 921–921, 1947.

C. Dalfo and M.A. Fiol. Graphs, friends and acquaintances. Electronic Journal of Graph Theory and Applications (EJGTA), 6(2):282–305, 2018

P. Dembowski. Finite Geometries, volume 44. Springer Science & Business Media, 1997.

N. Do. Party problems and Ramsey theory. Vinculum, 56(2):18–19, 2019.

A.W. Goodman. On sets of acquaintances and strangers at any party. The American Mathematical Monthly, 66(9):778–783, 1959.

R.L. Graham, B.L. Rothschild, and J.H. Spencer. Ramsey Theory, volume 20. John Wiley & Sons, 1990.

B. Grunbaum. Configurations of Points and Lines, volume 103. American Mathematical Soc., 2009.

F. Harary. Graph Theory (on Demand Printing Of 02787). Addison-Wesley series in mathematics. Avalon Publishing, 1969.

F. Harary and G. Prins. Generalized Ramsey theory for graphs iv, the Ramsey multiplicity of a graph. Networks, 4(2):163–173, 1974.

https://github.com/benjaminpeet/minmonotrianglesofconfigurations. GAP code for minimum number of monochromatic triangles in a configuration, 4 2022.

M.S. Jacobson. A note on Ramsey multiplicity. Discrete Mathematics, 29(2):201–203, 1980.

G. Kery. On a theorem of Ramsey. Matematikai Lopok, 15:204–224, 1964.

N.S. Mendelsohn, R. Padmanabhan, and B. Wolk. Planar projective configurations (part 1).Note di Matematica, 7(1):91–112, 1987.

T. Pisanski and B. Servatius. Configurations from a graphical viewpoint. Springer Science & Business Media, 2012.

A.J. Schwenk. Acquaintance graph party problem. The American Mathematical Monthly, 79(10):1113–1117, 1972.

D.R. Silaban, E.T. Baskoro, and S. Uttunggadewa. Restricted size Ramsey number for path of order three versus graph of order five. Electronic Journal of Graph Theory and Applications,5(1):55843, 2017.

M.P. Van Straten. The Topology of the Configuration of Desargues and Pappus. PhD thesis, University of Notre Dame, 1947.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats