A Hamilton cycle in a graph is a cycle that passes through every vertex of the graph. A graph is called Hamiltonian if it contains such a cycle. The problem of determining if a graph is Hamiltonian has been studied extensively, and there are many known sufficient conditions for Hamiltonicity. A large portion of these conditions relate the degrees of vertices of the graph to the number of vertices in the entire graph, and thus they can only apply to a limited set of graphs with high edge density. In a series of papers, Asratian and Khachatryan developed local analogues of some of these criteria. These results do not suffer from the same drawbacks as their global counterparts, and apply to wider classes of graphs. In this thesis we study this approach of creating local conditions for Hamiltonicity, and use it to develop local analogues of some classic results. We also study how local criteria can influence other global properties of graphs. Finally, we will see how these local conditions can allow us to extend theorems on Hamiltonicity to infinite graphs.

No description available.

These papers are all related to the problem of avoiding and completing an edge precoloring of a graph. In more detail, given a graph G and a partial proper edge precoloring φ of G and a list assignment L for every non-colored edge of G, can we extend the precoloring to a proper edge coloring avoiding any list assignment? In the first paper, G is a d-dimensional hypercube graph Qd, a partial proper edge precoloring φ and every list assignment L must satisfy certain sparsity conditions. The second paper still deals with d-dimensional hypercube graph Qd, but the list assignment L for every edge of Qd is an empty set and φ must be a partial proper edge precoloring of at most (d - 1) edges. For the third paper, G can be seen as a complete 3-uniform 3-partite hypergraph, every list assignment L must satisfy certain sparsity conditions but we do not have a partial proper edge precoloring φ on edges of G.

This thesis is composed of two papers both in algebraic combinatorics and Coxeter groups. In Paper I, we concentrate on smoothness of Schubert varieties indexed by involutions from finite simply laced types. We show that if a Schubert variety indexed by an involution of a finite and simply laced Coxeter group is smooth, then that involution must be the longest element of a parabolic subgroup. Given a Coxeter system (W, S), we introduce in Paper II the boolean complex of involutions of W as an analogue of the boolean complex of W studied by Ragnarsson and Tenner. By using discrete Morse Theory, we compute the homotopy type for a large class of W, including all finite Coxeter groups. In all cases, the homotopy type is that of a wedge of spheres of dimension |S| − 1. In addition, we provide a recurrence formula for the number of spheres in the wedge.

When given a Bayesian network, a common use of it is calculating conditional probabilities. This is known as inference. In order to be able to infer effectively, the structure of the Bayesian network is required to have low treewidth. Therefore, the problem of learning the structure of Bayesian networks with bounded treewidth is studied in this thesis. This is solved by reducing the problem to a mixed integer linear problem using several formulation for the structure of the Bayesian network as well as for bounding the treewidth of the structure. Solving the problem in this way gives an algorithm known as an anytime algorithm which can be aborted during the run and return a solution as well as an upper bound for the value of the best possible solution. Tests show that several of these formulations are of practical use as implementations of them prove solutions to be optimal or nearly optimal for several data sets.

In this licentiate thesis we study relations among invariants of lattice polytopes, with particular focus on bounds for the volume.In the first paper we give an upper bound on the volume vol(P^*) of a polytope P^* dual to a d-dimensional lattice polytope P with exactly one interiorlattice point, in each dimension d. This bound, expressed in terms of the Sylvester sequence, is sharp, and is achieved by the dual to a particular reflexive simplex. Our result implies a sharp upper bound on the volume of a d-dimensional reflexive polytope. In the second paper we classify the three-dimensional lattice polytopes with two lattice points in their strict interior. Up to unimodular equivalence thereare 22,673,449 such polytopes. This classification allows us to verify, for this case only, the sharp conjectural upper bound for the volume of a lattice polytope with interior points, and provides strong evidence for more general new inequalities on the coefficients of the h^*-polynomial in dimension three.

Given a set of k colors and a graph G with a subset S of precolored edges (a partial k-edge coloring of G), we consider the problem of determining whether G has a proper edge coloring of G with the same k colors (an extension of the partial coloring) where the colors of edges in S are not changed. If such a coloring exists, then the partial k-coloring is called extendable. Some scheduling problems as well as some combinatorial problems can be reformulated as partial edge coloring extension problems for corresponding graphs. Partial edge coloring extension problems seem to have been first considered in connection with the problem of completing partial Latin squares. In 1960 Evans stated his conjecture that any partial Latin square of size n with at most n – 1 non-empty cells can be completed to a Latin square of size n. In terms of edge colorings this is equivalent to the statement that any proper partial n-edge coloring of the balanced complete bipartite graph Kn,n with at most n – 1 precolored edges is extendable. This classical conjecture was proved by Smetaniuk (1981), and also independently by Andersen and Hilton (1983). Moreover, Andersen and Hilton completely characterized which partial Latin squares of size n with n non-empty cells that cannot be completed to a Latin square of size n. In addition, Andersen (1985) characterized partial Latin squares of size n with n+1 non-empty cells that are completable to Latin squares of size n. More recently, the problem of extending a partial edge coloring where the precolored edges form a matching has been considered by Edwards et al. (2018). Casselgren, Markstrom and Pham (2020) studied questions on extending partial edge colorings of the n-dimensional hypercubes Qn. In particular, they obtained an analogue of the positive solution to Evans' conjecture on completing partial Latin squares by proving that every proper partial edge coloring of at most n – 1 edges of Qn can be extended to a proper n-edge coloring of Qn. They also characterized which partial edge colorings of Qn with precisely n precolored edges are extendable to proper n-edge colorings of Qn. In this thesis we study similar partial edge coloring extension problems for trees. Let T be a tree with maximum degree Δ(T). First, we characterize which partial edge colorings with at most Δ(T) precolored edges in T that are extendable to proper Δ(T)-edge colorings, thereby proving an analogue of the aforementioned result by Andersen and Hilton for Latin squares. Then, we prove an analogue for trees of the result of Andersen by characterizing exactly which precolorings of at most Δ(T) + 1 precolored edges in a tree T that are extendable to Δ(T)-edge colorings of T. We also prove sharp conditions on when it is possible to extend a precolored matching or a collection of connected precolored subgraphs of a tree T to a Δ(T)-edge coloring of T. Finally, we consider the problem of avoiding a given (not necessarily proper) partial edge coloring. / <p>Funding agency: International Science Program (ISP)</p>

No description available.

Denna uppsats fokuserar på konfigurationer bestående av linjer och punkter, samt cirklar och punkter, som har tillämpningar inom områden som till exempel datarättningsmetoder. Vi presenterar klassiska exempel på dessa konfigurationer, såsom Miguels konfiguration och projektiva plan. Vidare undersöker vi de tre serier av cirkelkonfigurationer som presenterades av Gévay och Pisanski år 2012. Dessa serier är baserade på V-konstruktioner av olika enhetsgrafer, polyedrar och Knesergrafer, vilka beskriver relationer mellan mängder. Det mesta av teorin kommer ifrån [11] och [6]. Alla bilder har jag skapat själv, de som ser mer symmetriska ut är gjorda med hjälp av chapGPT. / This essay focuses on configurations consisting of lines and points, as well as circles and points, which have applications in areas such as data correction methods. We present classical examples of these configurations, such as Miguel’s configuration and projective planes. Furthermore, we investigate the three series of circle configurations introduced by Gévay and Pisanski in 2012. These series are based on V-constructions of various unit graphs, polyhedra, and Kneser graphs, which describe relationships between sets. The majority of the theory is derived from [11] and [6]. All images have been created by myself, and those that appear more symmetric were generated using chapGPT.

We study the representations of the symmetric group $S_n$ found by acting on labeled graphs and trees with $n$ vertices. Our main results provide combinatorial interpretations that give the number of times the irreducible representations associated with the integer partitions $(n)$ and $(1^n)$ appear in the representations. We describe a new sign reversing involution with fixed points that provide a combinatorial interpretation for the number of times the irreducible associated with the integer partition $(n-1, 1)$ appears in the representations.