Competition graphs, threshold graphs and threshold Boolean functions

In this dissertation we study two concepts in discrete applied mathematics: competition graphs of acyclic digraphs and thresholdness of graphs and Boolean functions. These concepts are related in application models and in the techniques we use. Motivating applications come from ecology, resource allocation, neural network, etc.; In Chapter 2 we study Opsut's conjecture about competition number of graphs. This conjecture states that if the neighborhood of every vertex in a graph can be covered by at most two cliques, then the competition number of the graph is at most 2, and is exactly 2 if and only if the graph has no simplicial vertex and no isolated vertex. We introduce critical graphs for Opsut's conjecture and prove the conjecture is true if and only if it is true for critical graphs. We prove Opsut's conjecture for several classes of graphs. Among approaches proposed to study Opsut's conjecture, the inheritance of competition graphs is introduced to study competition numbers of graphs in general.; In Chapter 3 we study competition graphs and resource graphs of acyclic digraphs of low indegree. We characterize competition graphs and resource graphs of acyclic digraphs of indegree at most two. We study the fundamental problem of characterizing digraph whose competition graphs are interval graphs. We introduce restricted competition number and study the relationship between ordinary competition number and restricted competition number of those digraphs.; In Chapter 4 we study a generalization of threshold Boolean functions by using high order polynomial surfaces to separate Boolean functions. We study the characterization and recognition problems of Boolean functions of a certain threshold order. We introduce a Boolean minor operation on Boolean functions and study the problem of characterizing and recognizing classes of Boolean functions by means of Boolean minors.; In Chapter 5 the threshold weight of graphs is introduced to measure how far a graph is from being threshold. Threshold weight is derived from the study of nonlinear separation of Boolean functions in Chapter 4. Heavy graphs are introduced as graphs which have the maximum threshold weight possible and we characterize classes of heavy graphs.