Discrete Hardy Inequalities on Trees

ISEF Category: Mathematics

Subcategory: Analysis  ·  Difficulty: Advanced  ·  Setup: University Lab  ·  Time: Full Year

The Hook

A tree can hide a lot of structure in plain sight. In graph math, one small change in branching can change the best constant in an inequality. That makes this topic a great mix of proof work and computer checks. You get to ask where the bound comes from, and when it stays sharp.

What Is It?

A Hardy-type inequality is a rule that compares two ways of measuring a function on a graph. One side usually tracks how big the values are. The other side tracks how quickly they change from vertex to vertex. Think of it like comparing the total weight of a backpack to how unevenly that weight is packed.

On a tree, the graph has no cycles. That makes the structure easier to analyze, but the branching still matters a lot. A tree with one long path behaves differently from a tree that splits often. A sharp constant is the smallest or best number that makes the inequality true for every allowed function.

Your project can ask how that constant changes when branching is controlled. You can test small trees by computer, look for patterns, and compare those patterns with a proof by induction. The computer part does not replace the proof. It helps you guess the right statement and check whether your formula survives real examples.

Why This Is a Good Topic

This is a strong science fair topic because you can ask a precise math question, test it on many graphs, and then look for a proof pattern. It connects to network theory, optimization, and spectral graph ideas, so the work feels real and current. You can also build a clear result from small cases, which is perfect when you do not have a lab. The project teaches you how to move from examples, to conjecture, to proof.

Research Questions

• How does the sharp constant change when a tree’s branching factor increases?
• What is the effect of path length on the best Hardy constant for a family of trees?
• Does a tree with the same number of vertices but different branching patterns have the same sharp constant?
• To what extent can an induction formula predict the constant for larger trees from smaller ones?
• Which controlled-branching trees give the smallest or largest Hardy constant among graphs with the same size?
• How does the SDP-based estimate compare with the constant proved by induction?
• What is the effect of adding one extra leaf to a fixed tree on the inequality constant?

Basic Materials

• Laptop or desktop computer with internet access.
• Python installed on your computer.
• CVXPY package for semidefinite programming.
• NetworkX package for building and drawing graphs.
• Spreadsheet software for organizing graph data.
• Graph paper or a notebook for proof sketches.
• Calculator for checking small examples by hand.

Advanced Materials

• University or department computer access for larger SDP runs.
• Python with CVXPY, NumPy, SciPy, and NetworkX.
• A graph visualization tool such as Gephi or Graphviz.
• Access to a math library or journal database for reading related proofs.
• Symbolic algebra software for checking recurrence formulas.
• A shared folder or version control system for saving graph families and output files.

Software & Tools

• CVXPY: Solves semidefinite relaxations and lets you compare numerical bounds across graph families.
• Python: Builds tree families, runs experiments, and organizes output for analysis.
• NetworkX: Creates trees and measures graph properties like depth, degree, and branching.
• NumPy: Stores graph matrices and helps with fast numerical calculations.
• Matplotlib: Plots how the estimated constant changes across tree sizes and shapes.

Experiment Steps

1. Define one family of trees with a clear branching rule, so your results stay comparable.
2. Write down the exact discrete Hardy inequality you want to study, including the constant you want to optimize.
3. Generate small trees first, then compute numerical bounds for each graph to see the pattern.
4. Build a conjecture from the small cases, and compare it with known graph features such as depth and branching.
5. Set up an induction argument that follows the tree structure, and check where the proof needs a tight estimate.
6. Use SDP relaxations as a verification tool, then compare the numerical bound with the conjectured sharp constant.

Common Pitfalls

• Mixing up the graph inequality with a continuous Hardy inequality, which leads to the wrong formulas.
• Testing too many tree shapes at once, which makes it hard to see which structural change caused the result.
• Using graphs with inconsistent labels or root choices, which can change the way the branching rule is applied.
• Treating the SDP output as a proof, which it is not, because it only gives numerical evidence.
• Ignoring small-graph edge cases, which often break an induction step for the first few trees.

What Makes This Competitive

A strong version of this project would do more than check a few graphs. You would define a clean tree family, prove a general bound, and then test that bound against SDP output across many sizes. The best projects also explain why the constant is sharp, not just why it works. A careful comparison between numerical optimization and induction can make the work feel much more original.

Project Variations

• Study the same inequality on rooted binary trees instead of general controlled-branching trees.
• Compare trees with fixed vertex count but different degree distributions to see which shape changes the constant most.
• Replace the Hardy weight with a depth-based or degree-based weight and test whether the sharp constant still follows the same pattern.

Learn More

• MIT OpenCourseWare, Mathematics: Search for graph theory, optimization, and proof-based analysis courses to build your background.
• CVXPY documentation: Read the official examples for semidefinite programming and matrix constraints.
• NetworkX documentation: Find examples for constructing trees and computing graph properties.
• PubMed, NIH, and arXiv-style math archives are not the right fit here, so use MathSciNet or a university library to search for papers on discrete Hardy inequalities and graph inequalities.
• Linear Algebra and Its Applications: Search for articles on spectral graph theory, quadratic forms, and inequality bounds.
• SIAM Journal on Discrete Mathematics: Search for papers on graph inequalities, tree structure, and discrete analysis.