Franklin Kenter: Research

RESEARCH INTERESTS:
My research focuses on spectral graph theory, graph coloring, graph modeling, and Markov chains with a focus on directed graphs.

The primary tools I use are probabilistic methods and spectral methods in graph theory and combinatorics. However, my research also utilizes aspects from complex analysis, real analysis, probability, and enumerative combinatorics. requires the implementation of computer simulations or the development of algorithms in order to generate examples and conjectures. Additionally, some of my research requires acquiring and analyzing large real-world data sets.

My focus on directed graph presents additional challenges, as many of the tools and techniques used for undirected graphs do not apply for directed case. Hence, as part of my research, I develop new tools and techniques for directed graphs.

RESEARCH PUBLICATIONS:

Title	Brief Abstract	Picture
Necessary Spectral Conditions for Coloring Hypergraphs	(J. Combinatorial Computing and Machine Computing, to appear) The problem of k-coloring hypergraphs so that every edge is not monochromatic is known to be NP-Hard (i.e., easy to verify but difficult to solve). Therefore, it would be useful to develop an easily computable test that would help to determine whether or not a given hypergraph can be colored with k colors. We combine probabilistic and spectral methods in order derive a necessary condition for 2-coloring hypergraphs thereby establishing a computable non-trivial test that all 2-colorable hypergraphs must pass. Also included, is a probabilistic proof of Hoffman's Theorem regarding graph-coloring. Preprint
Discrepancy Inequalities for Directed Graphs Joint work with	(Discrete Applied Mathematics, to appear) We define the skew-discrepancy, a new type of discrepancy specific to directed graphs. Loosely speaking, the skew-discrepancy measures how "directed" the graph is when considering large sets of vertices. We show the skew-discrepancy is tightly controlled by an eigenvalue of a skew-symmetric matrix to within a logarithmic factor. Additional applications and examples are given. Preprint
An Analysis of the Basketball Endgame: When to Foul When Leading and Trailing	(abstract submitted to Sloane Sports Analytics Conference 2014) In basketball, it is common tactic for the trailing team to foul toward the end of the game in order to increase their chances of a comeback. This begs the question: "When should the leading begin to foul?" Surprisingly, this question has not been concretely answered before. In order to answer this question, we present a probabilistic combinatorial game to model basketball where during each possession, both teams make choices regarding when and if to shoot (as offense), and when and if to foul (as defense). These choice dictate the probability and quantity of points the offense can score during that possession as well as the amount of time removed from the clock. We solve this game using a recursive algorithm. This algorithm determines the optimal moves for each team during each possession. Further, the algorithm determines the probability of either team winning based on time remaining and point difference. Most specifically, we are able to determine when the defense should foul. Not only are we able to determine when the trailing team should foul, we show that, in fact, the leading team should foul roughly as often as the trailing team. Preprint
Concentration of the Stationary Distribution on General Random Directed Graphs	(to be submitted) Over the past decade there have been numerous Markov chain-based ranking systems, from the notable PageRank and HITS for web search to NCAA Random Walkers and LRMC for sports ranking to NetRank for cancer research. These ranking systems are not only viable, but they often outclass classical statistical methods! However, despite these successes, these is no probabilistic or statistical justification for these rankings. In this paper we aim to give justification to these rankings by demonstrating that the stationary distribution of a general random directed graph, in certain cases, is in fact concentrated around its "expected" distribution. Preprint
Adapting Markov Rankings for Predicting Score Differences	(In Progress) Given a set S and a partial ordering of S, a score difference, is a function f: S x S -> R such that both f(a,b) > 0 if and only if a > b, and f(b,a) = -f(a,b). Specifically, a score difference quantifies a partial ordering. Given only a small fraction of values for a score difference f, we develop a Markov chain ranking algorithm that, under mild assumptions, is able to estimate all values of f. We prove its effectiveness and give real-world applications.
Jensen's Inequality, The Law of Large Numbers and NCAA March Madness	(submitted to American Mathematical Monthly) Every March, millions of people participate in NCAA March Madness betting pools. Each participant in a betting pool fills out a bracket to predict the outcome of the NCAA Division-I Basketball Championship Tournament then earns points based upon the games he or she predicted correctly. The one with the most points wins the betting pool, earning a large share of the prize. For most pools, the scoring system is structured so that one who predicts the winner of the tournament outscores others who do not. Hence, in order win the pool, one should aim to predict the winner of the tournament. However, if more than one player chooses the tournament winner correctly, the winner of the pool is decided on the basis of other games. Therefore, in order to win the pool, a participant must balance his or her choice for the winning team with the popularity of that choice. We give a simple compact proof for the limiting optimal strategy for these betting pools- using only- as the title suggests- Jensen's Inequality and the Law of Large Numbers Preprint potentially available upon request

RESEARCH PRESENTATIONS:

Title	Conference(s)	Brief Abstract
Discrepancy Inequalities for Directed Graphs Joint work with Slides	AMS Western Regional Meeting 2011 and	(See Above)
Necessary Spectral Conditions for Coloring Hypergraphs Slides (revised Sept 2013)	and and	(See Above)
Optimizing Economic Boundaries of Multinational Organizations: A Graph Theoretic Approach	UC Berkeley	We present a mathematical model to determine the efficiency of international economic unions. We model international trade as a directed graph which we analyze using a variety of graph theoretic tools. We apply our model to the European Union as a case study and show that our methods produce viable results. We demonstrate that expelling any current member of the EU will increase the Cheeger ratio, resulting in reduced effectiveness of the conglomerate. Moreover, adding countries such as Switzerland (whose trade lies mostly with members of the EU) would decrease the Cheeger ratio, signifying that such additions would be desirable from an economic standpoint.
Using Eigenvalues and Eigenvectors to Find Needles in a Haystack		Finding a needle in a haystack was once a hard problem. However, magnets made finding that needle much easier. In the modern age, the vast amount of information is our haystack, and a particular piece of information is our needle, and as the title suggests, eigenvalues and eigenvectors are our magnets. We explore specific examples including the PageRank algorithm and spectral bipartitioning to demonstrate the power of eigenvalues and eigenvectors.