| 1. |
- Leander, Madeleine, 1986-
(author)
-
Combinatorics of stable polynomials and correlation inequalities
- 2016
-
Doctoral thesis (other academic/artistic)abstract
- This thesis contains five papers divided into two parts. In the first part, Papers I-IV, we study polynomials within the field of combinatorics. Here we study combinatorial properties as well as the zero distribution of the polynomials in question. The second part consists of Paper V, where we study correlating events in randomly oriented graphs.In Paper I we give a new combinatorial interpretation of the stationary distribution of the partially asymmetric exclusion process in terms of colored permutations and decorated alternative trees. We also find a connection between the corresponding multivariate partition functions and the multivariate Eulerian polynomials for r-colored permutations.In Paper II we study a multivariate refinement of P-Eulerian polynomials. We show that this refinement is stable (i.e., non-vanishing whenever the imaginary parts of its variables are all positive) for a large class of labeled posets.In Paper III we use the technique of compatible polynomials to prove that the local h-polynomial of the rth edgewise subdivision of the (n - 1)-dimensional simplex 2V has only real zeros. We generalize the result and study matrices with interlacing preserving properties.In Paper IV we introduce s-lecture hall partitions for labeled posets. We provide generating functions as well as establish a connection between statistics on wreath products and statistics on lecture hall partitions for posets.In Paper V we prove that the events {s → a} (that there exists a directed path from s to a) and {t → b} are positively correlated in a random tournament for distinct vertices a, s, b, t ∈ Kn. We also discuss the correlation between the same events in two random graphs with random orientation.
|
|
| 2. |
- Emtander, Eric, 1979-
(author)
-
Chordal and Complete Structures in Combinatorics and Commutative Algebra
- 2010
-
Doctoral thesis (other academic/artistic)abstract
- This thesis is divided into two parts. The first part is concerned with the commutative algebra of certain combinatorial structures arising from uniform hypergraphs. The main focus lies on two particular classes of hypergraphs called chordal hypergraphs and complete hypergraphs, respectively. Both these classes arise naturally as generalizations of the corresponding well known classes of simple graphs. The classes of chordal and complete hypergraphs are introduced and studied in Chapter 2 and Chapter 3 respectively. Chapter 4, that is the content of \cite{E5}, answers a question posed at the P.R.A.G.MAT.I.C. summer school held in Catania, Italy, in 2008. In Chapter 5 we study hypergraph analogues of line graphs and cycle graphs. Chapter 6 is concerned with a connectedness notion for hypergraphs and in Chapter 7 we study a weak version of shellability.The second part is concerned with affine monoids and their monoid rings. Chapter 8 provide a combinatorial study of a class of positive affine monoids that behaves in some sense like numerical monoids. Chapter 9 is devoted to the class of numerical monoids of maximal embedding dimension. A combinatorial description of the graded Betti numbers of the corresponding monoid rings in terms of the minimal generators of the monoids is provided. Chapter 10 is concerned with monomial subrings generated by edge sets of complete hypergraphs.
|
|
| 3. |
|
|
| 4. |
- Krüger, Oliver, 1988-
(author)
-
On linear graph invariants related to Ramsey and edge numbers : or how I learned to stop worrying and love the alien invasion
- 2019
-
Doctoral thesis (other academic/artistic)abstract
- In this thesis we study the Ramsey numbers, R(l,k), the edge numbers, e(l,k;n) and graphs that are related to these. The edge number e(l,k;n) may be defined as the least natural number m for which all graphs on n vertices and less than m edges either contains a complete subgraph of size l or an independent set of size k. The Ramsey number R(l,k) may then be defined as the least natural number n for which e(l,k;n) = ∞ .In Paper I, IV and V we study strict lower bounds for e(l,k;n). In Paper I we do this in the case where l = 3 by, in particular, showing e(G) ≥ (1/3)(17n(G) - 35α(G) - N(C4;G)) for all triangle-free graphs G, where N(C4;G) denotes the number of cycles of length 4 in G. In Paper IV we describe a general method for generating similar inequalities to the one above but for graphs that may contain triangles, but no complete subgraphs of size 4. We then show a selection of the inequalities we get from the computerised generation. In Paper V we study the inequality e(G) ≥ (1/2)(ceil((7l - 2)/2)n(G) - l floor((5l + 1)/2)α(G))for l ≥ 2, and examine the properties of graphs G without cliques of size l+1 such that G is minimal with respect to the above inequality not holding, and show for small l that no such graphs G can exist.In Paper II we study constructions of graphs G such that e(G) - e(3,k;n) is small when n ≤ 3.5(k-1). We employ a description of some of these graphs in terms of 'patterns' and a recursive procedure to construct them from the patterns. We also present the result of computer calculations where we actually have performed such constructions of Ramsey graphs and compare these lists to previously computed lists of Ramsey graphs.In Paper III we develop a method for computing, recursively, upper bounds for Ramsey numbers R(l,k). In particular the method uses bounds for the edge numbers e(l,k;n). In Paper III we have implemented this method as a computer program which we have used to improve several of the best known upper bounds for small Ramsey numbers R(l,k).
|
|
