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.

No description available.

No description available.

No description available.

This thesis consists of the following two articles. New properties of the Edelman–Greene bijection. Edelman and Greene constructed a correspondence between reduced words of the reverse permutation and standard Young tableaux. We prove that for any reduced word the shape of the region of the insertion tableau containing the smallest possible entries evolves exactly as the upper-left component of the permutation’s (Rothe) diagram. Properties of the Edelman–Greene bijection restricted to 132-avoiding and 2143-avoiding permutations are presented. We also consider the Edelman-Greene bijection applied to non-reduced words. On random shifted standard Young tableaux and 132-avoiding sorting networks. We study shifted standard Young tableaux (SYT). The limiting surface of uniformly random shifted SYT of staircase shape is determined, with the integers in the SYT as heights. This implies via properties of the Edelman–Greene bijection results about random 132-avoiding sorting networks, including limit shapes for trajectories and intermediate permutations. Moreover, the expected number of adjacencies in SYT is considered. It is shown that on average each row and each column of a shifted SYT of staircase shape contains precisely one adjacency. / <p>QC 20180926</p>

Here we investigate a variety of ways to represent polytopes and related objects. We define a class of posets, which includes all abstract polytopes, giving a unique representative among posets having a particular labeled flag graph and characterize the labeled flag graphs of abstract polytopes. We show that determining the realizability of an abstract polytope is equivalent to solving a low rank matrix completion problem. For any given polytope, we provide a new construction for the known result that there is a combinatorial polytope with a specified ridge that is always projectively equivalent to the given polytope, and we show how this makes a naturally arising subclass of intractable problems tractable. We give necessary and sufficient conditions for realizing a polytope's interval poset, which is the polytopal analog of a poset's Hasse diagram. We then provide a counter example to the general realizablity of a polytope's interval poset. / Mathematics

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.