Electronic Journal of Graph Theory and Applications

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

Jamie Bishop^a, Rebekah Kuss^b, Benjamin Peet^a

^aSt. Martin's University, Lacey WA, USA

jamiebishop@stmartin.edu, kussr@oregonstate.edu, bpeet@stmartin.edu (corresponding author)

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 \(v_3\) 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 \(v_3\) configuration.

Keywords: Ramsey theory, configurations, colorings Mathematics Subject Classification: 05C55, 51E30, 05B30

DOI: 10.5614/ejgta.2023.11.2.8

1. Introduction

Ramsey numbers came from the mathematician, philosopher, and economist Frank Plumpton Ramsey. In the years since Ramsey, there have been many developments of Ramsey numbers and this paper seeks to first give an exposition of some different versions of Ramsey numbers specifically for triangles. For further reading on variations on Ramsey numbers see for example

Received: 25 July 2022, Revised: 11 June 2023, Accepted: 6 August 2023.

^&lt;sup>b</sup>Oregon State University¹, Corvallis OR, USA

^1. Paper completed while Rebekah Kuss was a student at St. Martin's University

[22]. In [11], the minimum number of monochromatic triangles given an edge 2-coloring was considered. We continue the theory on to an adaptation of Ramsey theory for configurations of points and lines considering the minimum number of monochromatic triangles given a 2-coloring.

Configurations of points and lines are a classical topic, but the literature has not brought these two subjects together. We discuss where graph theory and the theory of configurations diverge and how this relates to Ramsey theory. This paper gives a number of specific results regarding the number of non-disjoint monochromatic triangles in some notable configurations, as well as some results about the addition or connected sum (using incidence switches) of configurations and the maximum number of mutually intersecting lines.

2. Preliminary definitions and examples

2.1. Graph theory

We include the following preliminary definitions for completeness. These can be found in most introductory texts on graph theory. We referenced [14].

A graph consists of finite sets V and X. V is the set of vertices and X is the set of unordered pairs of distinct vertices of V . That is, the edges.

A subgraph G′ of a graph G consists of a subset of vertices V ′ of V and a subset X′ of X that contains only pairs of vertices from V ′ .

An r-coloring of a set S is a map x : s → (r) for s ∈ S, (x(s)) is called the color of s. This paper will deal only with 2-colorings or bi-colorings and as convention dictates consider these as red-blue edge colorings, hence x(s) = red or x(s) = blue.

A subgraph of a colored graph is monochromatic if all its edges have the same color.

A complete graph K^p is a graph of order p with all possible pairs of vertices connected by an edge.

Two subgraphs of a given graph are vertex disjoint if no vertices are shared. Two subgraphs of a given graph are edge disjoint if no edges are shared. Note that vertex disjoint implies edge disjoint but not the converse. For convenience here we deal only with vertex disjoint and simply say disjoint.

A sequence of distinct vertices x1x² . . . xⁿ is called a path if xixⁱ + 1 is an edge for all i such that 1 ≤ i ≤ n − 1. When x1xⁿ is also an edge, the sequence x1x² . . . xnx¹ is called cycle.

2.2. Ramsey theory

The Ramsey number r(G1, G2) is defined to be the least number of vertices p to guarantee that a red-blue colored (2-colored) complete graph on p vertices contains a red subgraph isomorphic to G¹ or a complete blue subgraph isomorphic to G2.

We then define the multiple Ramsey numbers [4] as r(kG1, nG2) being the least number of vertices p to guarantee that a red-blue colored (2-colored) complete graph on p vertices contains k disjoint red subgraphs isomorphic to G¹ or l disjoint blue subgraphs isomorphic to G2. Here kG¹ represents k disjoint copies of G1.

2.3. Configurations

An incidence geometry is given by a pair (P,L) where P = {p1, . . . , pn}; L = {l1, . . . , lm}; each lⁱ ⊂ P; and for any pair pⁱ¹ , pⁱ² there is at most one line l^j that contains both elements. Naturally, the elements of P are known as points and the elements of L are known as lines.

An incidence geometry is further known as a configuration if each point is incident with the same number of lines as any other (denoted s); each line is incident with the same number of points as any other (denoted k); and there are at least three points.

Configurations are here considered in a purely combinatorial sense.

When a configuration has the parameters (n, m, s, k), we term it a (ns, mk)-configuration. If n = m (and consequently s = k - see the foundational text on configurations of [13]) we call the configuration symmetric and usually denote it a v^k configuration according to the commonly used notation in papers such as [1] and [2].

A Menger graph is a representation of a configuration as an undirected graph where the points are shown as the vertices and the lines are made up by a collection of edges. See [23] and [7].

3. Preliminary results

The following is Ramsey's theorem. We used the version from [10]:

Theorem 3.1. For every pair of positive integers m and n, the value of r(Km, Kn) is finite. In other words, there is a positive integer N such that if the edges of K^N are coloured red or blue, then there exists a red subgraph isomorphic to K^m or a blue subgraph isomorphic to Kn.

We now give a Lemma possible due to [18] that we will use in our new results:

Lemma 3.1. Any red-blue coloring of K⁵ that does not contain a red triangle or a blue triangle must be composed of a blue 5-cycle and a red 5-cycle.

Proof. Take a 2-coloring of K⁵ with no monochromatic triangle. Note that no vertex is incident with three or more edges of the same color - if ab, ac, and ad are all red, the subgraph induced by b, c, d cannot contain any red edges without creating a red triangle. Furthermore, if all of its edges are blue, then it creates a blue triangle. Hence, every vertex must be incident with exactly two red edges and two blue edges.

Without loss of generality, label the vertices a, b, c, d, e. Let ab and ac be red and ad and ae be blue. So bc is also blue, de is red, and b must join to exactly one of d and e as a red edge. Again, without loss of generality, we can assume that bd is red and be is blue. This forces cd to be blue and ce to be red. This gives the red cycle abdeca and the blue cycle adcbea.

We now continue the theory by giving two more versions of Ramsey numbers. These are not new, just simplified versions of those seen in the literature where notation and terminology varies.

First of all we disregard which color the subgraph is. This leads us to:

Definition 3.1. Let r(G1, G² : k) be the least number of vertices to guarantee a total of at least k disjoint subgraphs that are either red and isomorphic to G¹ or blue and isomorphic to G2.

Note that in this paper we consider only when G1, G² are the same complete graph, but if m > n the specific statement of "k disjoint subgraphs that are either red and isomorphic to K^m or blue and isomorphic to Kn" as opposed to "k disjoint monochromatic subgraphs that are isomorphic to K^m or Kn" is required as a red K^m would contain many copies of a red Kn.

We also then consider removing the disjoint condition.

Definition 3.2. We define r ∗ (kG1, lG2) to be the least number of vertices to guarantee k red subgraphs isomoprhic to G¹ or l blue subgraphs isomorphic to G2.

The final definition is a combination of Definition 3.1 and 3.2:

Definition 3.3. We define r ∗ (G1, G² : k) to be the least number of vertices to guarantee a total of at least k subgraphs that are either red and isomorphic to G¹ or blue and isomorphic to G1.

We make the observation here that these numbers are closely related to Ramsey multiplicities. The general definition of a Ramsey multiplicity R(G1, G2) is given by the smallest possible total number of subgraphs that are red and isomorphic to G¹ or blue and isomorphic to G² among all 2-colorings of Kr(G1,G2) . Note the use of lower case r for Ramsey number and upper case R for Ramsey multiplicity.

We give a quick example for exposition:

Example 1. We will see in Proposition 3.4 that r ∗ (K3, K³ : 2) = 6 and it is a first result of Ramsey theory that r(K3, K3) = 6. Simply put, 6 vertices are required to guarantee a monochromatic triangle in any 2-coloring and in fact this guarantees 2 of them.

Now R(K3, K3)represents the least possible number of monochromatic triangles in Kr(K3,K3) = K6. Clearly, R(K3, K3) = 2.

We take this example to prove the following general result:

Proposition 3.1. \[r^*(G_1, G_2 : R(G_1, G_2)) = r(G_1, G_2)\]

Proof. Any 2-coloring of Kr(G1,G2) contains at a minimum R(G1, G2) subgraphs that are either red and isomorphic to G¹ or blue and isomorphic to G2.

Now r ∗ (G1, G² : R(G1, G2)) is the least number of vertices p so that any 2-coloring of K^p contains at a minimum R(G1, G2) subgraphs that are either red and isomorphic to G¹ or blue and isomorphic to G2.

Hence \[r^*(G_1, G_2 : R(G_1, G_2)) \le r(G_1, G_2)\].

Now, by definition there is a 2-coloring of Kr(G1,G2)−¹ that contains no subgraphs that are either red and isomorphic to G¹ or blue and isomorphic to G2. Hence it certainly cannot have at least R(G1, G2) of them.

So \[r^*(G_1, G_2 : R(G_1, G_2)) > r(G_1, G_2) - 1\] and the equality follows.

These Ramsey multiplicities have been considered in many places, in particular [5], [6], [15], and [17].

We now give a result without proof from [4]:

Theorem 3.2. \[r(kK_3, lK_3) = 3k + 2l\] for all \(k \ge l \ge 1\) and \(k \ge 2\).

Remark 3.1. We give here inequalities that are useful in relating the various Ramsey numbers:

\[r(G_1, G_2) \le r(kG_1, lG_2)\] \[r(G_1, G_2) \le r(G_1, G_2 : k) \le r(kG_1, lG_2)\] \[r^*(kG_1, lG_2) \le r(kG_1, lG_2)\] \[r^*(G_1, G_2 : k) \le r(G_1, G_2 : k)\]

3.1. Non-disjoint

We now establish the following value for exposition:

Proposition 3.2. \[r^*(K_3, K_3 : 2) = 6\]

Proof. It is clear that n = 5 is insufficient by Lemma 3.1. Figure 1 establishes that n = 6 is sufficient.

Figure 1. Complete graph on six vertices with two monochromatic triangles.

By the result that r(K3, K3) = 6 [10] [8], we can assume a monochromatic triangle and without loss of generality blue. If this were the only triangle, removing a vertex (and all associated edges) would leave us in the situation of Lemma 3.1.

Then by Lemma 3.1 we have an all blue pentagon labelled with vertices a, b, c, d, e. Add a center x (the vertex of the original monochromatic triangle) and two blue edges to make the known blue triangle {d, e, x}.

Then if there are no more monochromatic triangles then ax and bx are red. But if ab is blue this gives a blue triangle {a, b, c} and if ab is red this gives a red triangle {a, b, x}. Hence, there are at least two monochromatic triangles.

We now state the result of Goodman in [11] (which generalizes the above result) and which was proved more succinctly in [21].

Theorem 3.3. The minimum number of monochromatic triangles in a bi-colored complete graph on n vertices is given by:

\[\binom{n}{3} - \left\lfloor \frac{n}{2} \left\lfloor \frac{(n-1)^2}{4} \right\rfloor \right\rfloor\]

3.2. Disjoint

The following is a Theorem which as far as we aware has not appeared in the literature:

Theorem 3.4. \[r(K_3, K_3 : k) = 3k + 2\] for \(k \ge 2\).

Proof. We begin by showing that 3k + 1 vertices are not enough. We construct a 2-colored K3k+1 by taking a blue K3k−1, a blue K² and then joining the two by red edges.

Then necessarily there are no red monochromatic triangles and can only be k − 1 disjoint blue triangles from the blue K3k−¹ subgraph.

We now proceed by induction on k to show that 3k + 2 is sufficient.

Consider a red/blue coloring of K⁸ and assume that it does not contain at least two disjoint monochromatic triangles. Proposition 3.5 establishes that there are at least two non-disjoint monochromatic triangles. If they are disjoint then the result follows, hence we assume they are not. Then, consider the following cases:

Case 1. Suppose that in the 2-coloring of K8, there is a blue triangle and a red triangle, whose vertices are labeled in Figure 2.

Figure 2. One red triangle and one blue triangle.

Now consider the subgraph induced by {a, c, f, g, h}. If it contains a monochromatic triangle, then that triangle and the triangle formed by {b, d, e} gives at least two disjoint monochromatic triangles, which is a contradiction to our assumption. Then the subgraph generated by {a, b, f, g, h} must be colored according to Lemma 3.1, and edge ac must be included in the red 5-cycle. It follows that the subgraph induced by {f, g, h} must contain two red edges, say edges fg and gh must be red, otherwise one of the vertices in {e, f, g} will join both a and c to form a monochromatic triangle that is disjoint from the blue triangle with vertices {b, d, e}.

Similarly, using a similar logic as above, if we consider the subgraph of {d, e, f, g, h}, the subgraph must be colored in accordance with Lemma 3.1, and edge de must be included in the blue 5-cycle. It follows that the subgraph induced by {f, g, h} must contain two blue edges, say edges fg and gh must be blue to form a 5-cycle. Since {f, g, h} only has three edges, we obtain a contradiction. Hence all monochromatic triangles are the same color.

Case 2. Suppose that in the 2-coloring of K8, there are exactly two same-colored triangles, say red, that share an edge, whose vertices are labeled in Figure 3.

According to Lemma 3.1, so that the subgraph generated by {c, e, f, g, h} does not yield a monochromatic triangle, we must have that without loss of generality cefghc is a red 5-cycle. But then to avoid a monochromatic triangle from the subgraph generated by {b, e, f, g, h} we must have that befghb is a red 5-cycle. But then again by Lemma 3.1, edges bg and gc must be blue. So

Figure 3. Two red triangles sharing an edge.

that we do not have a blue triangle, bc must be red. Repeating this argument, we see that aefgha and defghd must be red 5-cycles. Then we yield two disjoint red triangles generated by {b, e, d} and {a, c, h}, this is in contradiction to our assumption.

Case 3. Suppose that in the 2-coloring of K8, there are two same-colored, say red, triangles that share only one vertex, whose vertices are labeled in Figure 4.

Figure 4. Two red triangles.

By a similar argument to the one used twice in case 1, the subgraph generated by {f, g, h} must contain two red edges and without loss of generality we assume that fg and gh are red also.

Then again without further loss of generality, we assume that afghca and dfghed are the red 5-cycles. Then ad must be red to avoid a blue triangle {a, g, d} and ce must be red to avoid a blue triangle {c, g, e}. But then we have red triangles {a, f, d} and {c, e, h} which are disjoint. Another contradiction.

Hence there are at least two disjoint monochromatic triangles. Note that three triangles cannot be disjoint by the pigeon hole principle. Hence there are exactly two disjoint monochromatic triangles.

For the inductive step, suppose that the result is true for k monochromatic triangles. So taking a 2-colored complete graph on 3(k + 1) + 2 = 3k + 5 vertices we can assume the existence of at least one monochromatic triangle. Deleting the vertices of this triangle (and all associated edges) leaves a 2-colored complete graph on 3k + 2 vertices which by the inductive hypothesis contains at least k monochromatic triangles. Hence the 2-colored complete graph on 3(k + 1) + 2 vertices contains k + 1 monochromatic triangles as required.

Corollary 3.1. The minimum number of disjoint monochromatic triangles in a 2-coloring of a complete graph on n vertices is:

\[\left\lfloor \frac{n-2}{3} \right\rfloor\]

Proof. This follows as the least integer inverse of n = 3k + 2 as established by Theorem 3.4.

These results lead us into the theory of configurations by an approach that asks what the minimum number of triangles in a particular graph is as opposed to how many vertices are required to have a certain minimum number of monochromatic triangles.

Ramsey numbers are dependent upon the fact that complete graphs form a totally ordered set. Configurations of points and lines certainly do not form a totally ordered set. However, as is recognized in [12], we can always compute minimum numbers of monochromatic triangles given a particular graph. We will take this approach with some specific configurations that are symmetric with three points per line.

4. Ramsey theory for configurations

We begin by making the note that by [19], a Menger graph does not uniquely determine the configuration. Hence, Ramsey theory on configurations cannot be simply defined by Ramsey theory on the Menger graph.

As this paper deals entirely with the number of monochromatic triangles, we must define what we mean by a triangle in a configuration.

Definition 4.1. We say that the points p1, p2, p³ ∈ P form a triangle if there are lines l1, l2, l³ such that:

• 1. p1, p² ∈ l¹ but p³ ̸∈ l¹
• 2. p2, p³ ∈ l² but p¹ ̸∈ l²
• 3. p1, p³ ∈ l³ but p² ̸∈ l³

Note that by definition, the lines l1, l2, l³ are unique as given any two points there is only one line that contains both. Hence, given a triangle it is equivalent to give the three points p1, p2, p³ or the three lines l1, l2, l3.

Example 2. For the Fano configuration, the usual Menger graph is given by Figure 5.

Figure 5. Fano configuration.

As a graph, the points (vertices) p1, p4, p⁶ do not form a triangle, yet as a configuration they certainly do.

From this example we also see that disjointness is less clear. Triangle p1, p2, p⁵ is disjoint from triangle p3, p4, p⁷ as graph triangles, but p² and p⁴ lie on the same line so can they be considered disjoint in a configuration context? To avoid this ambiguity we will stick to the non-disjoint case.

We now give the following definition:

Definition 4.2. Given a configuration, we define a line 2-coloring to be an assigning of the color red or blue to each line of the configuration.

A triangle is monochromatic if each of the lines l1, l2, l³ are the same color.

We now immediately give the following results:

Theorem 4.1. The minimum number of monochromatic triangles in a line 2-coloring of the Fano configuration is 4.

Proof. We give a coloring that has only 4 monochromatic triangles, three blue and one red in Figure 6.

Figure 6. Minimal Fano coloring.

To see that this is minimal, suppose there are no monochromatic triangles. Without loss of generality color a triangle with 2 red lines, line 125 and line 567, and 1 blue line, line 147, so that no red triangle is created. Color another line blue, line 136. In order to create no red triangles, color another line blue. Thus, there will be at least 1 blue triangle.

So we may assume that there is at least one monochromatic triangle. Without loss of generality color a red triangle, lines 147, 567, and 125. In order to create no other red triangles, all the other lines have to be colored blue. Thus, given only one monochromatic triangle of a given color, there will be 3 monochromatic triangles of the opposite color, and there are at least 4 monochromatic triangles.

Finally, assume there are exactly two monochromatic triangles of a given color. Without loss of generality color a red triangle, lines 147, 567, and 125. To create a second red triangle, color any other line red, line 136. Note that given the symmetry of the Fano configuration, any two such red triangles must be as such. Then necessarily there are then 3 red triangles.

Given the three red triangles, there are either more red triangles or a blue triangle formed by coloring the remaining lines blue. The result then follows.

Corollary 4.1. Given a line 2-coloring of the Fano configuration with 4 monochromatic triangles, the minimum number of blue triangles is 1.

Figure 7. Minimally colored Young configuration.

Theorem 4.2. The minimum number of monochromatic triangles in a line 2-coloring of the Young configuration is 0.

Proof. We give the following coloring in Figure 7 for proof.

Theorem 4.3. The minimum number of monochromatic triangles in a line 2-coloring of the Mobius- ¨ Kantor configuration is 0.

Proof. Again we present a minimal coloring in Figure 8.

Figure 8. Minally colored Mobius-Kantor configuration. ¨

Theorem 4.4. The minimum number of monochromatic triangles in a line 2-coloring of the Pappus configuration is 0.

Proof. We give the following coloring in Figure 9 to illustrate the result.

Theorem 4.5. The minimum number of monochromatic triangles in a line 2-coloring of the Desargues configuration is 0.

Proof. We give here in Figure 10 the coloring that achieves zero monochromatic colorings. Note how the configuration is represented as in Desargues' theorem. See [9] for more details.

Figure 9. Pappus' configuration.

Figure 10. Desargues' configuration.

The code written in the GAP coding language in the github repository at [16] can both verify the above results and compute the minimum number of monochromatic triangles given a line 2 coloring of a configuration.

We make the remark here that if a configuration is triangle-free, then trivially the minimum number of monochromatic triangles will of course be zero.

5. Incidence switches

In [3] and [20], the concept of the addition of configurations or an incidence switch is given. We define this here as a connected sum (using the terminology of algebraic topology) in order to provide a constructive result for computing the minimum number of monochromatic triangles.

Definition 5.1. Given two (ns, mk)-configurations we define a connected sum of the two configurations to be a (2ns, 2mk)-configuration constructed as follows: Take points p¹ and p² from each configuration and lines l¹ and l² that each are on. Then replace p¹ with p² in l¹ and similarly p² with p¹ in l2.

Visually, we can see this connected sum in Figure 11.

It is clear that this connected sum is still a configuration and indeed a (2ns, 2mk)-configuration. Recall that a configuration is flag-transitive if for any two incidences of points and lines (flags) there exists a line-preserving bijection of the point set that sends the first incidence to the second.

Figure 11. Connected sum.

It then follows that these connected sums are not necessarily unique if the configurations are not flag-transitive - dependent on the choices of points and line.

We now give the following proposition:

Proposition 5.1. Given a connected sum of two (ns, mk)-configurations, the point set can be partitioned into points from the first configuration and points from the second. Given this partition there is no triangle that has points from both partitioning sets.

Proof. This follows as the connected sum has only two lines that contain points from both the original configurations. Three lines would be required to form a triangle.

This then immediately leads to the following corollaries:

Corollary 5.1. Given a connected sum of two (ns, mk)-configurations the number of triangles is less than or equal to the sum of the number of triangles of the two configurations.

Corollary 5.2. Given a connected sum of two (ns, mk)-configurations and a line 2-coloring, the minimum number of monochromatic triangles is less than or equal to the sum of the minimum number of monochromatic triangles given line 2-colorings of the two configurations.

6. Maximal sets of mutually intersecting lines

We here make the observation that the minimum number of monochromatic triangles was only non-zero for the Fano plane (for the configurations that we dealt with in section 4). We also note that the Fano plane consists of seven mutually intersecting lines, whereas for example Pappus's configuration contains maximally three intersecting lines and the Mobius-Kantor four. We take this observation to state formally the result:

Theorem 6.1. Suppose a symmetric v³ configuration contains a maximal set of mutually intersecting lines of size i. Then i ≥ 6 implies that the minimum number of a monochromatic 2-colorings is non-zero. Furthermore, given such a subset of six mutually intersecting lines, the minimum number of monochromatic triangles given a line 2-coloring of the set is two.

We note here that the maximum size of a set of mutually intersecting lines is seven (given a line, each of the three points on the line can be on two more lines) and this refers exactly to the Fano configuration where we have seen the minimum number of monochromatic triangles given a line 2-coloring is four.

Proof. Take a set of six mutually intersecting lines. It is clear that the only possible arrangement of six such lines is as in Figure 12.

Figure 12. Six mutually intersecting lines.

It then follows that without loss of generality if lines abc and cde are blue and aef is red, then bge must be red, but in that case fgc and agd both form monochromatic triangles whether red or blue. Minimally two are formed if fgc and agd are different colors as seen in Figure 13.

Figure 13. Six mutually intersecting lines with necessary coloring.

This yields the required two monochromatic triangles.

The immediate corollary is the following.

Corollary 6.1. If a symmetric v³ configuration has k disjoint sets of 6 mutually intersecting lines then the minimum number of monochromatic triangles given a line 2-coloring will be greater than or equal to 2k.

We then see that the connected sum of configurations gives an excellent example of this corollary:

Example 3. Take a connected sum of two Fano configurations. The Fano configuration is flagtransitive so this is unique. It is then clear that there are two disjoint sets of six mutually intersecting lines - one each from the original configurations. By the corollary, the minimum number of monochromatic triangles given a line 2-coloring should be greater than or equal to 4. Our GAP code confirms this and establishes that it is exactly 4.

We here also give a couple of particular examples of configurations with maximally 5 mutually intersecting lines. The first has minimally no monochromatic triangles given a line 2-coloring and the second has minimally one monochromatic triangle given a line 2-coloring.

Example 4.

{{1,2,3},{3,4,5},{1,5,6},{3,6,7},{2,5,7},{1,8,9},{6,9,10},{2,11,13},
{7,12,13},{4,8,10},{4,11,12},{9,13,14},{8,11,14},{10,12,14}}

Example 5.

{{1,2,3},{1,4,5},{3,5,6},{1,6,7},{3,4,7},{4,6,8},{1,10,15},{2,13,14},
{5,9,11},{7,12,16},{8,9,10},{11,12,13},{14,15,16},{8,11,14},{9,12,15},
{10,13,16}}

This second example makes it clear that the converse of Theorem 6.1 is not true. We conjecture that the following partial converse is true:

Conjecture 1. Suppose a symmetric v³ configuration contains a maximal set of mutually intersecting lines of size i. If minimum number of monochromatic triangles in a line 2-colorings is non-zero, then i > 4.

Acknowledgement

We would like to thank Misha Lavrov for his very helpful contribution to Theorem 3.4 and connecting us with the relevant background literature for this paper, as well as the anonymous reviewer for their comprehensive report which greatly improved the paper.

References

• [1] A. Betten, G. Brinkmann, and T. Pisanski. Counting symmetric configurations v3. Discrete Applied Mathematics, 99(1-3):331–338, 2000.
• [2] M. Boben. Irreducible (v3) configurations and graphs. Discrete mathematics, 307(3-5):331– 344, 2007.
• [3] M. Bras-Amoros and K. Stokes. The semigroup of combinatorial configurations. In ´ Semigroup forum, volume 84, pages 91–96. Springer, 2012.
• [4] 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.
• [5] 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.
• [6] D. Conlon. On the Ramsey multiplicity of complete graphs. arXiv preprint arXiv:0711.4999, 2007.
• [7] H.S.M. Coxeter. Configurations and maps. In Bulletin of the Mathematical Society, volume 53, pages 921–921, 1947.
• [8] C. Dalfo and M.A. Fiol. Graphs, friends and acquaintances. Electronic Journal of Graph Theory and Applications (EJGTA), 6(2):282–305, 2018.

• [9] P. Dembowski. Finite Geometries, volume 44. Springer Science & Business Media, 1997.
• [10] N. Do. Party problems and Ramsey theory. Vinculum, 56(2):18–19, 2019.
• [11] A.W. Goodman. On sets of acquaintances and strangers at any party. The American Mathematical Monthly, 66(9):778–783, 1959.
• [12] R.L. Graham, B.L. Rothschild, and J.H. Spencer. Ramsey Theory, volume 20. John Wiley & Sons, 1990.
• [13] B. Grunbaum. ¨ Configurations of Points and Lines, volume 103. American Mathematical Soc., 2009.
• [14] F. Harary. Graph Theory (on Demand Printing Of 02787). Addison-Wesley series in mathematics. Avalon Publishing, 1969.
• [15] F. Harary and G. Prins. Generalized Ramsey theory for graphs iv, the Ramsey multiplicity of a graph. Networks, 4(2):163–173, 1974.
• [16] https://github.com/benjaminpeet/minmonotrianglesofconfigurations. GAP code for minimum number of monochromatic triangles in a configuration, 4 2022.
• [17] M.S. Jacobson. A note on Ramsey multiplicity. Discrete Mathematics, 29(2):201–203, 1980.
• [18] G. Kery. On a theorem of Ramsey. Matematikai Lopok, 15:204–224, 1964.
• [19] N.S. Mendelsohn, R. Padmanabhan, and B. Wolk. Planar projective configurations (part 1). Note di Matematica, 7(1):91–112, 1987.
• [20] T. Pisanski and B. Servatius. Configurations from a graphical viewpoint. Springer Science & Business Media, 2012.
• [21] A.J. Schwenk. Acquaintance graph party problem. The American Mathematical Monthly, 79(10):1113–1117, 1972.
• [22] 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.
• [23] M.P. Van Straten. The Topology of the Configuration of Desargues and Pappus. PhD thesis, University of Notre Dame, 1947.