Which carefully scoped question can become an independent project?
A useful project has a precise instance space, a claim that could be proved or refuted, a method you can actually carry out, and a clear account of what is already known. A famous unsolved problem supplies motivation; it does not make every small experiment a new contribution. An educational reproduction, a verified construction, a restricted theorem, and a conjecture are different deliverables. Name yours before beginning.
Our foundation uses two-color edge colorings of complete graphs. The complete graph $K_n$ has $n$ vertices and an edge between each pair of distinct vertices. Color every edge red or blue. A monochromatic triangle is a set of three vertices whose three edges have the same color. We will classify the colorings of $K_5$ without such a triangle, prove that none exist on $K_6$, and audit the claims by exhaustive computation. This supplies a complete project without requiring any specialization section.
Write $G$ for the graph consisting of the red edges. The blue graph is its complement, containing precisely the pairs missing from $G$. A clique is a set of mutually adjacent vertices; an independent set contains no adjacent pair. Thus the question asks for graphs with neither a three-vertex clique nor a three-vertex independent set. This translation links a construction problem to a pair of forbidden configurations.
Use the habits from experimental and computational combinatorics and reading, developing and publishing research: specify the encoding, check witnesses independently, reproduce a lemma, and distinguish local findings from current research status. Each numbered section is an optional studio offering a different specialization, with enough vocabulary to examine one finite example.
Which carefully scoped question can become an independent project?
Instance. Label five vertices $0,1,2,3,4$. Make the cycle edges $01,12,23,34,04$ red and the other five edges blue. The red graph is a five-cycle $C_5$. The blue edges form the cycle $0,2,4,1,3,0$. Neither cycle contains a triangle.
Trace to investigate. A sixth vertex would have five new incident edges. At least three must share a color. If three red neighbors have a red edge between them, that edge and the new vertex form a red triangle; if they have no red edges, they form a blue triangle. Interchanging the colors gives the same contradiction when three blue neighbors occur.
Scoped questions. Is every valid coloring of $K_5$ a labeled five-cycle in red? How many labeled colorings exist? What is the minimum number of monochromatic triangles on $K_6$? We will prove the answers and then check all $2^{10}$ and $2^{15}$ colorings. These are established training problems, not newly open questions.
56.1 Ramsey-number bounds and constructions
Optional extension; not required to complete the chapter foundation.
The Ramsey number $R(s,t)$ is the smallest $n$ such that every graph on $n$ vertices contains a clique of size $s$ or an independent set of size $t$. A construction on $n$ vertices avoiding both proves $R(s,t)>n$; proving that no such graph exists on $n$ vertices proves $R(s,t)\le n$. A lower-bound witness and an upper-bound exclusion therefore require different evidence.
The optional background is Sections 21.9 and 21.10 in Ramsey theory. The bridge to probabilistic lower bounds is simple: if the expected number of forbidden configurations in a random coloring is less than one, some coloring has none. Hypergraph Ramsey theory replaces pairs by larger subsets; neither topic is needed for the five-cycle argument here.
Solved exact example. The opening construction proves $R(3,3)>5$. In any coloring of $K_6$, choose a vertex and three incident edges of the same color. If one edge among their other endpoints has that color, a monochromatic triangle uses the chosen vertex. If none does, the three endpoints form a triangle in the opposite color. Thus $R(3,3)\le6$, and together these prove $R(3,3)=6$.
For contrast, independently color each edge red or blue with equal probability. A fixed triangle is monochromatic with probability $2(1/2)^3=1/4$. If $T$ counts monochromatic triangles, linearity of expectation gives $\mathbb E T=\binom n3/4$. On five vertices this is $5/2$, so the expectation-less-than-one criterion does not establish the five-cycle construction. Failure of a sufficient criterion is not a proof of impossibility.
Current research target, checked 13 October 2026. The verified interval remains $43\le R(5,5)\le46$. The primary paper by Angeltveit and McKay, $R(5,5)\le46$, version 2, establishes the upper bound; its introduction records Exoo's lower bound of 43. Determining the exact value is the open question used for this studio. We do not reproduce the large computational proof or claim an improved bound. A realistic first project is to understand its local restrictions and build a trustworthy verifier for candidate constructions.
Exercise. What does a verified graph on 42 vertices with no clique or independent set of size five prove? Hint: the defining property must fail at 42. Solution: $R(5,5)>42$, hence $R(5,5)\ge43$. It does not prove equality, and an unsuccessful heuristic search on 43 vertices does not prove an upper bound.
A Ramsey construction proves existence by supplying a checkable witness; an upper bound must exclude every permitted instance. Keep the graph order, forbidden sizes, labeling convention, and completeness of the search explicit before interpreting an experimental result as a bound.
56.2 Turán and forbidden-subgraph problems
Optional extension; not required to complete the chapter foundation.
For a fixed graph $H$, the extremal number $\operatorname{ex}(n,H)$ is the largest number of edges in an $n$-vertex simple graph containing no copy of $H$ as a subgraph. Here containment is not induced: extra edges do not prevent a copy. A stability question asks whether graphs close to the extremal edge count must resemble an extremal construction. A supersaturation question asks how many forbidden copies appear once that count is exceeded.
Section 45.10 in modern extremal combinatorics provides optional background. The bridge is the distinction between finding one dense avoiding graph and proving an upper bound for all avoiding graphs. Neither a search table nor a stability heuristic supplies the latter by itself. The triangle case below is established; more general forbidden-subgraph problems require separate status checks.
Turán and forbidden-subgraph problems: a worked example
Determine $\operatorname{ex}(5,K_3)$. The complete bipartite graph $K_{2,3}$ has six edges and no triangle, because every edge crosses its two parts. This gives a lower bound of six.
For the upper bound, let $G$ be triangle-free with $n$ vertices and $m$ edges. For an edge $uv$, the neighborhoods of $u$ and $v$ are disjoint: a shared neighbor would create a triangle. Consequently $d(u)+d(v)\le n$, where $d$ denotes degree. Summing over edges gives
$$\sum_v d(v)^2\le nm.$$
Also $\sum_v d(v)=2m$. Cauchy–Schwarz gives $4m^2\le n\sum_v d(v)^2\le n^2m$. If $m=0$ the desired conclusion is immediate; otherwise divide by $m$ to obtain $m\le n^2/4$. Thus $m\le\lfloor n^2/4\rfloor$, and at $n=5$ this is six. Both bounds agree.
Assumptions checked: the graph is finite, simple, undirected, and has no triangle of either induced or non-induced type; these coincide for $K_3$. The degree sum and neighborhood argument need no randomness. Balanced complete bipartite graphs attain the general bound, which is Mantel's theorem.
Solved studio comparison. The red five-cycle in our Ramsey example has five edges, below the triangle-free maximum of six. Maximizing red edges alone therefore selects a different problem: $K_{2,3}$ avoids a red triangle but its three-vertex part is an independent set, yielding a blue triangle. Ramsey avoidance constrains both a graph and its complement.
Exercise. Find a six-vertex triangle-free graph with nine edges, and explain why it is not a valid $(3,3)$ Ramsey graph. Hint: split the vertices evenly. Solution: $K_{3,3}$ has nine edges and no triangle, but each part is an independent triple. Its complement contains two blue triangles. For a research reading connection, the independent-set viewpoint used in modern extremal work is developed in the primary hypergraph-container paper of Saxton and Thomason; the advanced theorem is not needed for this proof.
56.3 Sunflower conjecture and related set-family bounds
Optional extension; not required to complete the chapter foundation.
A set family is $k$-uniform if every member has size $k$. Distinct members $A_1,\ldots,A_r$ form an $r$-sunflower if every pairwise intersection equals the same set $C$, called the core. The petals $A_i\setminus C$ are pairwise disjoint. An empty core is allowed, so disjoint sets are also a sunflower. Merely having a nonempty common intersection is insufficient: every pair must have exactly that intersection.
The optional bridge from Section 18.7 in extremal set theory is the classical sunflower lemma: a sufficiently large family of bounded-size sets contains many members with their overlap organized into a single core. The conjectured improvement asks, for each fixed $r\ge3$, for a constant $C_r$ independent of $k$ and the ground-set size such that more than $C_r^k$ distinct $k$-sets force an $r$-sunflower.
Solved instance. Take $A_1=\{c,a,b\}$, $A_2=\{c,d,e\}$, and $A_3=\{c,f,g\}$. All three pairwise intersections are $\{c\}$. The three petals have size two, are disjoint, and their union with the core has seven elements. The incidence table below records nine memberships: three in the shared core column and six private memberships.
Current reading record, checked 13 October 2026. Alweiss, Lovett, Wu, and Zhang's primary paper proves a major improvement over the classical bound. Recent primary preprints address restricted families: Ge, Wang, Xu, and Zhao report the conjectured exponential form for bounded VC-dimension, and Shangguan reports a further improvement there. Bounded VC-dimension limits which membership traces a family can realize; it is an additional hypothesis, not a property of every uniform family. The unrestricted exponential assertion remains the conjectural target in these current sources. Do not transfer a restricted theorem to all families.
Exercise. Are $\{1,2\},\{2,3\},\{1,3\}$ a three-sunflower? Hint: compute all three pairwise intersections. Solution: no: they are $\{2\},\{1\},\{3\}$. The three-way intersection is empty, but the sets are not pairwise disjoint. A safe local project is to classify small sunflower-free families and prove the resulting finite statements, without calling their already known special cases new results.
56.4 Permutation-pattern enumeration
Optional extension; not required to complete the chapter foundation.
A permutation $\sigma$ of $\{1,\ldots,n\}$ contains a pattern $\pi$ of length $k$ if some $k$ entries, selected in increasing position order, have the relative value order of $\pi$. It avoids $\pi$ otherwise. Let $a_n(\pi)$ count avoiding permutations, with $a_0(\pi)=1$. Pattern avoidance requires a comparison of relative ranks; selected values need not be consecutive integers.
Sections 8.6 and 53.5 supply optional background; research topics in combinatorial structures gives the fuller pattern-enumeration treatment. The bridge is to replace raw sequence fitting by a reversible decomposition: count smaller objects, explain how they are combined, and prove that every object has exactly one such description.
Solved example: avoiding 231. Write a permutation as $L\,n\,R$, splitting at its largest entry. If some entry of $L$ exceeds some entry of $R$, those two entries and $n$ form 231. Thus every value in $L$ is smaller than every value in $R$. Conversely, this separation, together with avoidance in both parts, prevents a crossing 231 pattern. If $L$ has $j$ entries, its value set must be $\{1,\ldots,j\}$; the other values lie in $R$. Standardizing each part gives
$$a_n(231)=\sum_{j=0}^{n-1}a_j(231)a_{n-1-j}(231).$$
Starting from $a_0=1$, this yields $a_1=1$, $a_2=2$, $a_3=5$, and $a_4=14$. At length three the only excluded permutation is 231. At length four, the four summands are $5,2,2,5$. These calculations reproduce the Catalan recurrence, rather than merely noticing the Catalan numbers in a table.
The historical Stanley–Wilf conjecture is an established theorem: Marcus and Tardos prove that for each fixed pattern there is an exponential upper bound on its avoidance counts. That does not give an exact enumeration for every pattern. A studio must specify which further question it asks; no general claim that all individual growth rates are known is made here. Advanced enumeration results beyond this decomposition are omitted prerequisites.
Exercise. Use the recurrence to compute $a_5(231)$. Hint: use the five splits at the largest entry. Solution: $14+5+4+5+14=42$. A project can reproduce this decomposition, verify all 120 length-five permutations, and investigate a changed pattern; the changed question requires a fresh literature check before being labeled open.
56.5 Asymptotic enumeration and random structures
Optional extension; not required to complete the chapter foundation.
An asymptotic estimate describes behavior as size tends to infinity. The notation $f_n\sim g_n$ means $f_n/g_n\to1$. A random combinatorial model also needs a probability distribution: uniform labeled objects, uniform isomorphism classes, and uniform encodings can give different laws. Define the distribution before interpreting an average or a typical structure.
Sections 26.10 in analytic combinatorics and 23.10 in random graphs and random combinatorial structures are optional background. Generating functions connect exact decompositions to growth estimates; local limits describe neighborhoods in large random structures. The bridge here is to separate exact formulas, limiting statements, and finite experiments. Flajolet and Sedgewick's author-hosted book resources provide the primary analytical treatment; its general transfer machinery is an omitted prerequisite.
Solved counting example. The recurrence in Section 56.4 gives the Catalan number $C_n=\binom{2n}{n}/(n+1)$. Using Stirling's factorial estimate gives
$$C_n\sim\frac{4^n}{\sqrt\pi\,n^{3/2}}.$$
This derivation uses the classical Stirling estimate as an explicitly imported prerequisite. Its conclusion is relative asymptotic accuracy, not exact equality. For $n=4$, the exact count is 14, while the leading approximation is approximately 18.05. Small-size disagreement does not refute an asymptotic theorem, and numerical agreement at a few sizes does not prove one.
Solved probability example. Under uniform independent edge coloring of $K_5$, all 1,024 labeled colorings are equally likely. Exactly 12 have no monochromatic triangle, so the success probability is $12/1024=3/256$. By the classification proved in the capstone, they all have red graph isomorphic to $C_5$. Selecting uniformly from valid labeled colorings and selecting a uniform valid isomorphism class happen to give the same graph type here; that coincidence disappears when more than one class is present.
Exercise. If a randomized search samples colorings independently and uniformly, what is the probability that ten samples all fail? Hint: multiply independent failure probabilities. Solution: $(253/256)^{10}$, approximately 0.889. Failure in a short random run is unsurprising even though witnesses exist. Report the sampling model and seed when reproducing a run; a general probability calculation is separate from any particular observed run.
56.6 Hypergraph matching, coloring, and containers
Optional extension; not required to complete the chapter foundation.
A hypergraph $\mathcal H=(V,E)$ has a vertex set $V$ and a collection $E$ of subsets called edges. It is $r$-uniform when every edge has size $r$. A matching is a collection of pairwise disjoint edges. A proper two-coloring gives each vertex a color so that no edge is monochromatic. An independent vertex set contains no complete hyperedge. These are three distinct questions; a small matching number does not by itself prevent proper coloring.
The optional background is Sections 20.8 in hypergraph theory and 45.4 in modern extremal combinatorics. A container family covers every independent set by a containing vertex set, preferably with few hyperedges and with economical indexing. The primary works of Saxton–Thomason and Balogh–Morris–Samotij establish general container methods. Their quantitative hypotheses and conclusions are omitted here; a small cover is not a proof of either general theorem.
Solved finite instance. Take $V=\{1,2,3,4,5,6\}$ and edges $123,345,156$, where these strings denote sets. Each pair of edges intersects: the intersections are $\{3\},\{1\},\{5\}$. Consequently the largest matching has size one. Color $\{1,3,5\}$ red and $\{2,4,6\}$ blue. Every edge has two red vertices and one blue vertex, so this is a proper coloring despite the pairwise intersections.
For a small container cover, set $D_i=V\setminus\{i\}$ for $i=1,2,3$. Every independent set must miss at least one vertex of edge $123$, and hence belongs to some $D_i$. These containers contain, respectively, one, two, and one of the three original edges. The cover gives the coarse count $\lvert\operatorname{Ind}(\mathcal H)\rvert\le3\cdot2^5=96$. It overcounts heavily and even exceeds the trivial bound $2^6=64$; coverage alone is not enough for an effective enumeration theorem.
An exact inclusion–exclusion calculation does better. Each forbidden edge is contained in eight vertex subsets. Any pair of edges has a union of size five, giving two subsets containing that pair; the union of all three is $V$, giving one subset. Thus the number of independent sets is $64-3\cdot8+3\cdot2-1=45$. Exhaustive checking of 64 subsets confirms it.
Exercise. Is the red vertex set independent in this example? Hint: inspect whether it contains an entire edge, not just two vertices of one. Solution: yes; every edge also needs its blue vertex. Both color classes in a proper hypergraph two-coloring are independent. The container studio can investigate better finite covers and their overlap, while clearly separating those local questions from general container bounds.
56.7 Additive-combinatorial configurations
Optional extension; not required to complete the chapter foundation.
A nontrivial three-term arithmetic progression is a triple $a,a+d,a+2d$ with $d>0$ in the integer setting. A subset of $\{1,\ldots,N\}$ is progression-free if it contains no such triple. Define $r_3(N)$ to be the largest size of a progression-free subset. Requiring distinct terms matters: otherwise every nonempty set would contain the trivial progression $a,a,a$.
Sections 33.9 in additive combinatorics and 34.4 in arithmetic combinatorics and higher-order Fourier analysis provide optional background. Their bridge is that unusually many additive coincidences can force structure, while Fourier or uniformity estimates can detect configurations. These deeper mechanisms are omitted prerequisites; our finite question needs only exact arithmetic.
Solved instance. On $\{1,\ldots,8\}$ the set $\{1,2,4,8\}$ is progression-free. Check each of its four three-element subsets; none has its middle element equal to the average of the other two. For example, $\{1,2,3\}$, $\{4,5,6\}$, $\{2,5,8\}$, and $\{1,4,7\}$ are forbidden triples, but checking these four alone is not a complete exclusion. We use the following explicit finite verification of all twelve progressions.
There are $\binom85=56$ five-element subsets. Testing each against the twelve progressions in $\{1,\ldots,8\}$ excludes all 56. Any larger set contains a five-element subset, so it too is excluded. Together with the construction this establishes $r_3(8)=4$ by an exhaustive finite proof, contingent on the stated complete enumeration. Checking all 256 subsets gives 106 progression-free sets, of which 25 have size four. Supply the enumerator and independently verified outputs in a project claiming this computational proof.
For research context, Bloom and Sisask's primary exposition of the Kelley–Meka bounds presents much stronger large-scale bounds for progression-free sets. This section does not assert a best current numerical rate or an exact asymptotic for $r_3(N)$; those require more literature and prerequisites than the finite studio.
Exercise. List all progressions of common difference three in $\{1,\ldots,8\}$. Hint: require $a+6\le8$. Solution: $(1,4,7)$ and $(2,5,8)$. This checks one boundary case in the enumerator. A finite-field version must explicitly change the ambient group and the interpretation of nontriviality; integer and modular predicates are not interchangeable.
56.8 Matroid structure and log-concavity
Optional extension; not required to complete the chapter foundation.
A matroid consists of a finite ground set and a family of independent subsets containing the empty set, closed under taking subsets, and satisfying exchange: if independent sets $A,B$ have $\lvert A\rvert\lt\lvert B\rvert$, some element of $B\setminus A$ can be added to $A$ while preserving independence. Let $I_k$ count independent sets of size $k$. A nonnegative sequence is log-concave if $I_k^2\ge I_{k-1}I_{k+1}$ at each interior index.
Sections 32.8 in matroid theory and 44.9 in advanced algebraic combinatorics supply optional background. Deletion and contraction reduce the ground set while retaining matroid structure; Hodge-theoretic methods explain inequalities not apparent from elementary counting. These advanced prerequisites are omitted. Brändén and Huh's primary paper proves the strongest form of Mason's conjecture; it is an established result, not an open studio target.
Solved example. In the uniform matroid $U_{2,4}$, a subset is independent exactly when its size is at most two. Exchange follows because adding one element to a smaller set cannot make its size exceed two when the larger independent set has at most two elements. The counts are $I_0=1,I_1=4,I_2=6$, with higher counts zero. At the only nontrivial interior index, $4^2\ge1\cdot6$.
The stronger normalization uses $J_k=I_k/\binom4k$ for $0\le k\le4$. Here the sequence is $1,1,1,0,0$, which is log-concave as well. Distinguish these two inequalities: raw and normalized counts are different statements, even though this example satisfies both.
Choose an element $e$. Deleting it gives $U_{2,3}$; contracting it gives $U_{1,3}$. Partitioning independent pairs according to whether they contain $e$ yields $I_2(U_{2,4})=I_2(U_{2,3})+I_1(U_{1,3})=3+3=6$. This is a concrete structural decomposition. A numerical inequality checked in this example does not reproduce the general theorem.
Exercise. Compute the independent-set counts of $U_{2,5}$ and their normalized values. Hint: count subsets of sizes zero, one, and two. Solution: the raw counts are $1,5,10,0,0,0$; division by $\binom5k$ gives $1,1,1,0,0,0$. A responsible project might compare elementary proofs in this class with the general theorem, rather than advertising a solved conjecture as open.
56.9 Discrepancy and geometric arrangements
Optional extension; not required to complete the chapter foundation.
For a finite point set $X$ and a family of subsets $\mathcal R$, a signing is a function $\chi:X\to\{-1,1\}$. Its imbalance on a range $S$ is $\sum_{x\in S}\chi(x)$, and the discrepancy is the minimum, over signings, of the largest absolute range imbalance. Geometric ranges can come from intervals, disks, or halfspaces. The range family matters as much as the point set.
Sections 52.4 and 52.8 in combinatorial discrepancy and geometric functional methods are optional background. The bridge from geometry to linear algebra forms an incidence matrix with a row for each range and a column for each point. A signing becomes a vector, and matrix multiplication records every range imbalance. Geometric or analytic structure may then constrain these products.
Solved interval instance. Take ordered points $x_1\lt x_2\lt x_3\lt x_4\lt x_5$ on a line and all nonempty intervals of these points as ranges. Sign them $+1,-1,+1,-1,+1$. Every range is a consecutive segment: even-length segments have sum zero, and odd-length segments have sum one or minus one. Thus discrepancy is at most one. Singleton ranges have absolute imbalance one under any signing, proving that the discrepancy is exactly one. The same proof works for any positive number of ordered points.
In an interval arrangement, changing an endpoint without crossing a point leaves its membership set unchanged. The continuous geometric choices therefore reduce to finitely many consecutive subsets, exactly $n(n+1)/2$ nonempty ranges for $n$ ordered distinct points. For five points there are fifteen. This reduction is part of a rigorous finite search specification, not an approximation to geometry.
Current status lesson, checked 13 October 2026. The September 2026 primary preprint by Guo, Fang, and Lu reports a dimension-independent Komlós bound below $3\sqrt{2\pi}$ for unit Euclidean vectors and the corresponding Beck–Fiala square-root dependence. Record these as recent reported results, and inspect their proofs and later literature when planning a seminar. Reusing an older list that labels these assertions simply “open” would misstate the current reading record. This chapter does not reproduce their analytical proof or assert an optimal constant.
Exercise. If only the single range $X$ is retained for five points, what is the discrepancy? Hint: odd parity prevents a zero total. Solution: one. For six points and only the full-set range it is zero, while the family of all intervals still has discrepancy one because it includes singletons. Changing the ranges changes the question.
56.10 Research capstone: formulate, investigate, and present a problem
Optional extension; not required to complete the chapter foundation.
A capstone begins with a problem contract: definitions, scope, dated literature status, desired claim, proposed method, and evidence needed for acceptance. A certificate can verify one construction; a completeness argument is needed to exclude all constructions. State whether the outcome is reproduction, finite classification, a restricted theorem, or a new proposed conjecture.
Solved project contract. Classify labeled graphs on five vertices with neither a triangle nor an independent triple. First show every vertex has degree at most two: three neighbors either contain an edge, creating a triangle with the vertex, or are an independent triple. Apply the same argument to the complement. Since complementary degrees sum to four, every original degree is also at least two. Therefore every degree is exactly two.
A finite simple graph with every degree two is a disjoint union of cycles of length at least three. To see this, start in a component and follow successive unused edges; degree two forces a cycle, and a further vertex attached to it would create degree at least three. On five vertices the only possible such component decomposition is a five-cycle: a three-cycle would require another cycle on two vertices, which is impossible in a simple graph, and would itself violate triangle avoidance. Conversely, a five-cycle and its complement are triangle-free. This proves the classification completely.
Count labeled cycles by ordering five vertices around a cycle: there are $5!$ orders, each cycle counted five times by rotation and twice by reversal. Thus there are $5!/(5\cdot2)=12$ valid colorings with named red and blue colors. Color complementation does not require dividing this count again: red-edge assignments are the labeled objects being counted.
The current $R(5,5)$ problem provides a larger reading target. Using the established value $R(4,5)=25$ recorded in the linked Angeltveit–McKay paper, any graph of order $n$ avoiding both five-cliques and independent five-sets must satisfy $n-25\le d(v)\le24$. Its neighborhood avoids a four-clique and independent five-set; its nonneighborhood avoids a five-clique and independent four-set. Each therefore has at most 24 vertices, giving the two inequalities. At order 43, every degree is between 18 and 24. These are necessary conditions, not sufficient ones and not a new result. The proof of $R(4,5)=25$ is an omitted prerequisite in this larger exercise.
Exercise. Does degree two alone certify a valid Ramsey graph on six vertices? Hint: compare $C_6$ and two disjoint triangles. Solution: no. Two triangles violate clique avoidance; $C_6$ has the independent triple of alternating vertices. A pruning condition can discard impossible candidates without certifying those that remain.
For presentation, lead with the contract, show one witness, prove the key structural restriction, then explain what the experiment audits. Finish with the dated open question and the exact limits of the project. A well-scoped result that another person can check is a successful capstone even when it does not improve a famous bound.
Formulate, investigate, and present a combinatorial research problem
The final studio connects the construction/exclusion distinction in Ramsey theory with the problem contract, proof, computation, and presentation of the capstone. You will complete a finite classification and prepare a current-problem reading brief. The small questions are solved training tasks; the exact value of $R(5,5)$ is the dated research motivation, with verified bounds stated above. No novelty claim or publication submission is required.
A cross-disciplinary interpretation treats vertices as agents and red and blue as two kinds of pairwise relationship. Ramsey guarantees describe unavoidable uniform triples in a completely specified pairwise system. They also suggest small adversarial tests for graph-analysis software: the five-cycle should evade both triangle predicates, while every six-vertex input should trigger at least one. Real relationship networks need not be complete or have only two kinds of relation, so state those modeling assumptions before applying the theorem.
Formulate, investigate, and present a combinatorial research problem
Inputs. Use simple graphs with labeled vertex set $\{0,\ldots,n-1\}$ for $n=5,6$. List unordered vertex pairs lexicographically; bit $i$ in a mask specifies whether pair $i$ is red. Blue is the bitwise complement on exactly those pairs. This gives $2^{\binom n2}$ distinct colorings without duplicate encodings. Let $T$ count monochromatic vertex triples.
Warm-up and scope, 15 points. Verify both cycles in the opening construction, state the two forbidden configurations, and compute the sample-space sizes 1,024 and 32,768. Write a contract saying which claims you aim to prove, which require computation, and which belong to the current literature. Attach a primary-source record for the interval $43\le R(5,5)\le46$, checked 13 October 2026; if undertaking the project later, refresh it.
Classification proof, 25 points. Prove that every valid five-vertex graph has all degrees two, conclude that it is $C_5$, and count its labeled realizations. Hint: use the same neighborhood argument in the graph and its complement. Include the converse construction and explain why labeled counting differs from counting isomorphism classes. The worked answer is one graph type, twelve labeled red-edge assignments, and $R(3,3)=6$ after the six-vertex exclusion.
Quantitative proof, 20 points. Prove that every coloring of $K_6$ has at least two monochromatic triangles. Count mixed-color wedges: at vertex $v$ there are $d(v)(5-d(v))$ pairs of incident edges with different colors. Each nonmonochromatic triangle contributes exactly two such wedges; a monochromatic triangle contributes none. Hence
$$T=20-\frac12\sum_v d(v)(5-d(v)).$$
For integer degrees between zero and five, $d(v)(5-d(v))\le6$. There are six vertices, so $T\ge20-18=2$. Attainment comes from taking red graph $K_{3,3}$: red has no triangles, and the blue graph consists of two triangles. This is a complete lower bound and matching construction, not merely a computational minimum.
Finite audit, 20 points. Enumerate every mask, count triples whose three pair bits agree, and independently compute the wedge formula. Compare the two values for every input. At order five, exactly twelve masks have $T=0$, and all twelve have every red degree two. At order six, the minimum is two, attained by 1,760 masks; no input has zero or one monochromatic triangle.
| Monochromatic triangles $T$ on six vertices | Number of labeled colorings |
|---|---|
| 2 | 1,760 |
| 3 | 5,760 |
| 4 | 7,500 |
| 5 | 6,264 |
| 6 | 5,040 |
| 7 | 3,360 |
| 8 | 1,530 |
| 9 | 720 |
| 10 | 432 |
| 11 | 160 |
| 12 | 90 |
| 13 | 120 |
| 16 | 30 |
| 20 | 2 |
All omitted counts are zero, and the displayed counts sum to 32,768. Their weighted mean is five, agreeing with $\binom63/4$. Color complementation preserves $T$, giving an additional check. A straightforward streaming enumerator uses $O(2^{\binom n2}n^3)$ time and $O(n^2)$ working memory when it stores one adjacency matrix and an aggregate histogram. Include the script, bit-order definition, interpreter version, invocation, and exact output in the project package.
Research brief and seminar, 20 points. Write a short manuscript explaining the classification, quantitative theorem, audit, and limitations. Add a one-page primary-literature brief on the current $R(5,5)$ interval and the neighborhood restriction in Section 56.10. Prepare a twelve-minute seminar: two minutes for the question and construction, four for classification, three for the wedge proof, two for validation, and one for the current-problem brief. Clearly label the training results as established and the large exact-value question as unresolved in the checked literature.
Validation and rubric. Proof credit requires both directions of the classification, correct cycle counting, and a justified wedge multiplicity of two. Experiment credit requires complete enumeration with agreement between independent predicates, the correct totals, and documented encodings. Research credit requires inspected primary statements with dates and hypotheses, rather than an outdated open-problem list. Presentation credit requires a listener to distinguish a witness from an exclusion and a finite audit from a new bound. A heuristic failure to find a graph is not an exclusion certificate.
Worked solution summary. The red five-cycle and its blue complement establish existence on five vertices. Three same-color neighbors exclude existence on six. Degree restrictions classify the five-vertex witnesses as cycles and give twelve labeled realizations. The wedge identity strengthens the six-vertex exclusion to two unavoidable monochromatic triangles, attained by $K_{3,3}$ in red. The exhaustive histogram checks all 32,768 finite cases; the structural proofs explain why the reported extrema occur.
Optional independent extension. Choose one of the specialization studios and propose a restricted question with a construction, an upper-bound plan, or a reproducibility target. For the Ramsey frontier, a first step is a candidate verifier and a proof of the degree restriction, not a brute-force promise to solve $R(5,5)$. For sunflowers, containers, or discrepancy, record the exact family and inspect recent primary work before using the word “open.” A new local conjecture should be labeled proposed, with tested range and counterexample search documented. Approval of a project should depend on its clear question and evidence plan, not on a promised breakthrough.