Explore the vast range of titles available.

For a graph G , let τ ( G ) be the maximum number of colors such that there exists an edge-coloring of G with no two color classes being isomorphic. We investigate the behavior of τ ( G ) when G = G ( n , p ) is the classical Erdős-Rényi random graph.

The Turan number for a graph H is the least possible number of edges on an n-vertex graph with no copy of H as a subgraph. For graphs G and H, the anti-Ramsey number, denoted ar(G, H), is the minimum number of colors d such that for any edge coloring with d colors there exists a rainbow copy of H. The concept of anti-Ramsey theory was first introduced by Erdos, Simonovits, and Sos in 1973 as a dual problem to traditional Ramsey theory. This thesis investigates Turan theory and anti-Ramsey theory for specific graph families, including cliques in multipartite graphs and matchings in hypergraphs. In Chapter 2, the anti-Ramsey number for disjoint cliques in complete, balanced multipartite graphs is given for certain sizes of cliques and multipartite graphs. In particular, the value ar(Kr×n, nKr) is given for all integers n, r ≥ 3 and ar(Kn,n,n, 3Kr) is given for all integers n, r ≥ 3. Chapter 3 generalizes Turan and anti-Ramsey theory to the context of hypergraphs. The Turan number for 3-matchings in complete 3-uniform hypergraphs is determined. Next, two proofs of the value for the anti-Ramsey number for 4-matchings in complete hypergraphs are presented. One relies on the Turan number for 3-matchings, and the other utilizes a method called progressive induction. Chapter 4 features additional work related to combinatorics more generally.

Universal cycles, such as De Bruijn cycles, are cyclic sequences of symbols that represent every combinatorial object from some family exactly once as a consecutive subsequence. Graph universal cycles are a graph analogue of universal cycles introduced in 2010. We introduce graph universal partial cycles, a more compact representation of graph classes, which use \"do not know\" edges. We show how to construct graph universal partial cycles for labeled graphs, threshold graphs, and permutation graphs. For threshold graphs and permutation graphs, we demonstrate that the graph universal cycles and graph universal partial cycles are closely related to universal cycles and compressed universal cycles, respectively. Using the same connection, for permutation graphs, we define and prove the existence of an \\(s\\)-overlap form of graph universal cycles. We also prove the existence of a generalized form of graph universal cycles for unlabeled graphs.

Kitaev, Potapov, and Vajnovszki [On shortening u-cycles and u-words for permutations, Discrete Appl. Math, 2019] described how to shorten universal words for permutations, to length \\(n!+n-1-i(n-1)\\) for any \\(i \\in [(n-2)!]\\), by introducing incomparable elements. They conjectured that it is also possible to use incomparable elements to shorten universal cycles for permutations to length \\(n!-i(n-1)\\) for any \\(i \\in [(n-2)!]\\). In this note we prove their conjecture. The proof is constructive, and, on the way, we also show a new method for constructing universal cycles for permutations.

Let \\(F\\) be a graph and \\(\\mathcal{H}\\) be a hypergraph, both embedded on the same vertex set. We say \\(\\mathcal{H}\\) is a Berge-\\(F\\) if there exists a bijection \\(\\phi:E(F)\\to E(\\mathcal{H})\\) such that \\(e\\subseteq \\phi(e)\\) for all \\(e\\in E(F)\\). We say \\(\\mathcal{H}\\) is Berge-\\(F\\)-saturated if \\(\\mathcal{H}\\) does not contain any Berge-\\(F\\), but adding any missing edge to \\(\\mathcal{H}\\) creates a copy of a Berge-\\(F\\). The saturation number \\(\\mathrm{sat}_k(n,\\text{Berge-}F)\\) is the least number of edges in a Berge-\\(F\\)-saturated \\(k\\)-uniform hypergraph on \\(n\\) vertices. We show \\[ \\mathrm{sat}_k(n,\\text{Berge-}K_\\ell)\\sim \\frac{\\ell-2}{k-1}n, \\] for all \\(k,\\ell\\geq 3\\). Furthermore, we provide some sufficient conditions to imply that \\(\\mathrm{sat}_k(n,\\text{Berge-}F)=O(n)\\) for general graphs \\(F\\).

Given a graph \\(G\\), an exact \\(r\\)-coloring of \\(G\\) is a surjective function \\(c:V(G) \\to [1,\\dots,r]\\). An arithmetic progression in \\(G\\) of length \\(j\\) with common difference \\(d\\) is a set of vertices \\(\\{v_1,\\dots, v_j\\}\\) such that \\(dist(v_i,v_{i+1}) = d\\) for \\(1\\le i < j\\). An arithmetic progression is rainbow if all of the vertices are colored distinctly. The fewest number of colors that guarantees a rainbow arithmetic progression of length three is called the anti-van der Waerden number of \\(G\\) and is denoted \\(aw(G,3)\\). It is known that \\(3 \\le aw(G\\square H,3) \\le 4\\). Here we determine exact values \\(aw(T\\square T',3)\\) for some trees \\(T\\) and \\(T'\\), determine \\(aw(G\\square T,3)\\) for some trees \\(T\\), and determine \\(aw(G\\square H,3)\\) for some graphs \\(G\\) and \\(H\\).

For a graph \\(G\\), let \\(\\tau(G)\\) be the maximum number of colors such that there exists an edge-coloring of \\(G\\) with no two color classes being isomorphic. We investigate the behavior of \\(\\tau(G)\\) when \\(G=G(n, p)\\) is the classical Erdős-Rényi random graph.

This paper considers the \\((n,k)\\)-Bernoulli--Laplace model in the case when there are two urns, the total number of red and white balls is the same, and the number of selections \\(k\\) at each step is on the same asymptotic order as the number of balls \\(n\\) in each urn. Our main focus is on the large-time behavior of the corresponding Markov chain tracking the number of red balls in a given urn. Under reasonable assumptions on the asymptotic behavior of the ratio \\(k/n\\) as \\(n\\rightarrow \\infty\\), cutoff in the total variation distance is established. A cutoff window is also provided. These results, in particular, partially resolve an open problem posed by Eskenazis and Nestoridi.

In this paper arithmetic progressions on the integers and the integers modulo n are extended to graphs. This allows for the definition of the anti-van der Waerden number of a graph. Much of the focus of this paper is on 3-term arithmetic progressions for which general bounds are obtained based on the radius and diameter of a graph. The general bounds are improved for trees and Cartesian products and exact values are determined for some classes of graphs. Larger k-term arithmetic progressions are considered and a connection between the Ramsey number of paths and the anti-van der Waerden number of graphs is established.