Minimal Number of Monochromatic Edges in Bicolored Graphs

Overview

The max-cut problem as part of extremal combinatorics was formulated by Paul Erdos in the 1960s. Multiple papers have been written on the topic regarding its role in mathematics as an extremal combinatorics problem and from an algorithmic perspective. This problem has been previously analyzed for various types of graphs, such as complete and H-free graphs for specific graphs H. In this project, we provide several bounds on the minimal number of edges in the maximum cut of various graphs. Sharp bounds are derived for the vertex-neighboring graph of a three-dimensional grid using a computer-aided double counting argument, and based on our results, we formulate a conjecture for the optimal coloring of these graphs. A general bound in terms of the chromatic number of the graph is obtained using the probabilistic method. This result is used to prove two bounds on the size of the maximal cut for planar graphs in terms of the number of its vertices and the number of its edges, respectively.

Awards (1)

• University of Arizona: Renewal Tuition Scholarship

Competition history

• ISEF 2022 Mathematics · Entry MATH006 · Atlanta, Georgia, United States

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.