Booth Id:
MATH006
Category:
Mathematics
Year:
2022
Finalist Names:
Noman, Iliyas (School: Sofia High School of Mathematics)
Abstract:
The max-cut problem as part of extremal combinatorics was formulated by Paul Erdős 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 Won:
University of Arizona: Renewal Tuition Scholarship