Percolation Cluster Size Concentration

ISEF Category: Mathematics

Subcategory: Probability and Statistics  ·  Difficulty: Advanced  ·  Setup: University Lab  ·  Time: Full Year

The Hook

A tiny change in random connections can make a graph go from scattered dots to one giant cluster. That jump shows up in networks, materials, and spread models. You can study when that cluster stays small and when it suddenly grows. This project turns a deep probability idea into something you can simulate and measure.

What Is It?

Bond percolation is a random graph process. You start with a grid or network, then keep each edge with some probability. The largest cluster is the biggest connected group that forms. Think of it like water soaking through a sponge, except you control which tiny links are open.

Concentration inequalities tell you how tightly a random outcome stays around its typical value. Talagrand's inequality is one of the tools mathematicians use to prove that a random quantity does not wander too far very often. In this project, you can test that idea by simulating cluster sizes on planar graphs such as triangular and hexagonal lattices, then checking how the distribution changes as edge probability changes.

Why This Is a Good Topic

This topic works well because it is clear, measurable, and tied to a real math idea. You can change one variable, the edge probability, and measure one outcome, the largest cluster size. That makes the project testable without needing a physical lab. You also get to practice simulation, data cleaning, graph theory, and statistical analysis, which are all strong skills for research competitions.

Research Questions

• How does edge probability affect the average size of the largest cluster on a triangular lattice? ?
• What is the effect of graph type, triangular versus hexagonal, on the spread of largest cluster sizes? ?
• Does the variance of the largest cluster size shrink as the edge probability moves away from the percolation threshold? ?
• To what extent do simulated cluster sizes match the concentration predicted by a Talagrand-style bound? ?
• Which lattice shape produces the sharpest concentration of cluster sizes near the threshold? ?
• How does increasing the graph size change the concentration of the largest cluster size? ?

Basic Materials

• Laptop with enough memory to run simulations.
• Python installed.
• Graph-paper sketches of triangular and hexagonal lattices.
• Spreadsheet software for data tables.
• Random number generator or Python random module.
• Notebook for recording simulation settings and results.

Advanced Materials

• Access to a workstation or university computer cluster.
• Python with NumPy, SciPy, and NetworkX.
• Access to a symbolic math system for checking inequality steps.
• Data visualization software for histograms and density plots.
• Version control software such as Git for tracking code changes.
• Access to journal articles on percolation and concentration inequalities.

Software & Tools

• Python: Runs the simulations and computes cluster-size statistics.
• NetworkX: Builds lattice graphs and finds connected components.
• NumPy: Handles repeated trials and summary statistics quickly.
• Matplotlib: Makes plots that compare distributions across edge probabilities.
• Jupyter Notebook: Keeps code, notes, and outputs in one place.

Experiment Steps

1. Define the graph family you will study and decide how large each lattice should be.
2. Choose the main output you will measure, such as the size of the largest connected cluster.
3. Build a simulation plan that repeats the random edge process many times at each probability value.
4. Create controls that let you compare triangular and hexagonal lattices under the same graph size rules.
5. Plan how you will summarize spread, such as variance, percentiles, and tail counts, not just averages.
6. Design your analysis so you can compare simulation patterns with the shape of a concentration bound.

Common Pitfalls

• Using too few simulation trials, which makes the largest-cluster estimates noisy and unstable.
• Comparing lattices of different sizes without controlling for graph size, which confuses shape effects with scale effects.
• Measuring only the mean cluster size, which hides the distribution spread that concentration inequalities care about.
• Changing the random seed setup between runs in a way that makes results hard to reproduce.
• Treating one simulated threshold-like jump as proof, instead of checking the pattern across many probabilities and graph sizes.

What Makes This Competitive

A strong version of this project does more than show that cluster sizes change. It asks whether the change follows a sharp, measurable pattern and how that pattern depends on graph shape and scale. You can push it further by comparing several concentration metrics, testing finite-size effects, and checking whether different lattices show different tail behavior. Clear statistical reasoning and careful controls matter more here than flashy visuals.

Project Variations

• Study site percolation instead of bond percolation and compare how the largest cluster concentration changes.
• Test the same ideas on square, triangular, and hexagonal lattices to see whether geometry changes the spread.
• Analyze the second-largest cluster size or cluster count instead of the largest cluster to compare concentration patterns.

Learn More

• MIT OpenCourseWare: Search for probability, random graphs, and discrete mathematics lecture notes and assignments that support the theory behind percolation.
• Introduction to Probability Models by Sheldon M. Ross: A standard reference for random processes, available through many libraries and used bookstores.
• NIH PubMed: Search for review articles on percolation models in networks and biological spread.
• MathSciNet or Zentralblatt MATH: Search abstracts for research papers on concentration inequalities and percolation.
• arXiv: Search for recent preprints on percolation, random graphs, and concentration bounds.