In the setting of tropical mathematics, geometric objects are rich with inherent combinatorial structure. For example, each polynomial $p(x,y)$ in the tropical setting corresponds to a tropical curve; these tropical curves correspond to unbounded graphs embedded in $\R^2$. Each of these graphs is dual to a particular subdivision of its Newton polytope; we classify tropical curves by combinatorial type based on these corresponding subdivisions. In this thesis, we aim to gain an understanding of the likeliness of the combinatorial type of a randomly chosen tropical curve by using methods from polytope geometry. We focus on tropical curves corresponding to quadratics, but we hope to expand our exploration to higher degree polynomials.

In their recent paper ``Edge-transitive products," Hammack, Imrich, and Klavzar showed that the direct product of connected, non-bipartite graphs is edge-transitive if and only if both factors are edge-transitive, and at least one is arc-transitive. However, little is known when the product is bipartite. This thesis extends this result (in part) for the case of bipartite graphs using a new technique called "stacking." For R-thin, connected, bipartite graphs A and B, we show that A x B is arc-transitive if and only if A and B are both arc-transitive. Further, we show A x B is edge-transitive only if at least one of A, B is also edge-transitive, and give evidence that strongly suggests that in fact both factors must be edge-transitive.

The chromatic polynomial of a graph, is a polynomial that when evaluated at a positive integer k, is the number of proper k colorings of the graph. We can then find the orbital chromatic polynomial of a graph and a group of automorphisms of the graph, which is a polynomial whose value at a positive integer k is the number of orbits of k-colorings of a graph when acted upon by the group. By considering the roots of the orbital chromatic and chromatic polynomials, the similarities and differences of these polynomials is studied. Specifically we work toward proving a conjecture concerning the gap between the real roots of the chromatic polynomial and the real roots of the orbital chromatic polynomial.

Esta dissertação descreve um jogo de baralho com caráter pedagógico, Resto Zero, o qual apresenta forte ligação com probabilidade, divisibilidade, análise combinatória e operações aritméticas elementares. Especificamente calculamos a probabilidade de alguns eventos principais que ocorrem no desenvolvimento do jogo. Apresentamos também uma relação do uso do Resto Zero aos anos/séries em que pode ser trabalhado. / In this dissertation we present and develop a simple game based upon a deck of cards which we call Residue Zero. We study and describe some characteristics of this game by observing its strong connections with probability, combinatorics and basic arithmetic operations. In particular, we compute the probability of several events that occur during the development of this game. We finally provide a relation of the scholar grades in which some features of this game could be worked out.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O objetivo central deste projeto é precisar matematicamente certos objetos combinatórios que servem como ponto de partida nas apresentações usuais da Análise Combinatória e são comumente apresentados de maneira informal e intuitiva. Estabelecido este referencial teórico preciso, pretendemos, a partir dele, reapresentar os conceitos de Análise Combinatória de modo mais rigoroso privilegiando sempre a apresentação mais natural possível. Mais precisamente, estaremos interessados em reapresentar os resultados referentes ao capítulo dois do livro do professor Augusto C. Morgado a partir de uma versão matematicamente mais precisa dos Princípios Aditivo e Multiplicativo. Além disso, pretendemos que os argumentos usados em nossas deduções usem predominantemente indução ou construção de bijeções, o que é um dos grandes objetos de estudo da combinatória moderna

A polyhedron P is a subset of a rational vector space V bounded by hyperplanes. If we fix a lattice in V , then we may consider the exponential integral and sum, two meromorphic functions on the dual vector space which serve to generalize the notion of volume of and number of lattice points contained in P, respectively. In 2007, Berline and Vergne constructed an Euler-Maclaurin formula that relates the exponential sum of a given polyhedron to the exponential integral of each face. This formula was "local", meaning that the coefficients in this formula had certain properties independent of the given polyhedron. In this dissertation, the author finds a new construction for this formula which is very different from that of Berline and Vergne. We may 'perturb' any polyhedron by tranlsating its bounding hyperplanes. The author defines a ring of differential operators R(P) on the exponential volume of the perturbed polyhedron. This definition is inspired by methods in the theory of toric varieties, although no knowledge of toric varieties is necessary to understand the construction or the resulting Euler-Maclaurin formula. Each polyhedron corresponds to a toric variety, and there is a dictionary between combinatorial properties of the polyhedron and algebro-geometric properties of this variety. In particular, the equivariant cohomology ring and the group of equivariant algebraic cycles on the corresponding toric variety are equal to a quotient ring and subgroup of R(P), respectively. Given an inner product (or, more generally, a complement map) on V , there is a canonical section of the equivariant cohomology ring into the group of algebraic cycles. One can use the image under this section of a particular differential operator called the Todd class to define the Euler-Maclaurin formula. The author shows that this formula satisfies the same properties which characterize the Berline-Vergne formula.

The Bernoulli distribution is a basic, well-studied distribution in probability. In this thesis, we will consider repeated Bernoulli trials in order to study runs of identical outcomes. More formally, for t ∈ N, we let Xt ∼ Bernoulli(p), where p is the probability of success, q = 1 − p is the probability of failure, and all Xt are independent. Then Xt gives the outcome of the tth trial, which is 1 for success or 0 for failure. For n, m ∈ N, we define Tn to be the number of trials needed to first observe n consecutive successes (where the nth success occurs on trial XTn ). Likewise, we define Tn,m to be the number of trials needed to first observe either n consecutive successes or m consecutive failures. We shall primarily focus our attention on calculating E[Tn] and E[Tn,m]. Starting with the simple cases of E[T2] and E[T2,2], we will use a variety of techniques, such as counting arguments and Markov chains, in order to derive the expectations. When possible, we shall also provide closed-form expressions for the probability mass function, cumulative distribution function, variance, and other values of interest. Eventually we will work our way to general formulas for E[Tn] and E[Tn,m]. We will also derive formulas for conditional averages, and discuss how famous results from probability such as Wald’s Identity apply to our problem. Numerical examples will also be given in order to supplement the discussion and clarify the results.

Richard Ehrenborg conjectured that in a bipartite graph G with parts X and Y, the number of spanning trees is at most the product of the vertex degrees divided by |X|⋅|Y|. We make two main contributions. First, using techniques from spectral graph theory, we show that the conjecture holds for sufficiently dense graphs containing a cut vertex of degree 2. Second, using electrical network analysis, we show that the conjecture holds under the operation of removing an edge whose endpoints have sufficiently large degrees. Our other results are combinatorial proofs that the conjecture holds for graphs having |X| ≤ 2, for even cycles, and under the operation of connecting two graphs by a new edge. We also make two new conjectures based on empirical data, each of which is stronger than Ehrenborg's conjecture.

A tournament graph G is a vertex set V of size n, together with a directed edge set E ⊂ V × V such that (i, j) ∈ E if and only if (j, i) ∉ E for all distinct i, j ∈ V and (i, i) ∉ E for all i ∈ V. We explore the following generalization: For a fixed k we orient every k-subset of V by assigning it an orientation. That is, every facet of the (k − 1)-skeleton of the (n − 1)-dimensional simplex on V is given an orientation. In this dissertation we bound the number of compatible k-simplices, that is we bound the number of k-simplices such that its (k − 1)-faces with the already-specified orientation form an oriented boundary. We prove lower and upper bounds for all k ≥ 3. For k = 3 these bounds agree when the number of vertices n is q or q + 1 where q is a prime power congruent to 3 modulo 4. We also prove some lower bounds for values k > 3 and analyze the asymptotic behavior.

In 2005, Alon, et al. proved that tournaments arising from majority voting scenarios have minimum dominating sets that are bounded by a constant that depends only on the notion of what is meant by a majority. Moreover, they proved that when a majority means that Candidate A beats Candidate B when Candidate A is ranked above Candidate B by at least two out of three voters, the tournament used to model this voting scenario has a minimum dominating set of size at most three. This result gives 2-majority tournaments some significance among all tournaments and motivates us to investigate when a given tournament can be considered a 2-majority tournament. In this thesis, we prove, among other things, that the presence of an upset path in a tournament allows us to conclude the tournament is realizable as a 2-majority tournament.