132 research outputs found
Computational advances in Rado numbers
No full textIn this dissertation, we present new methods in the computation of Rado numbers. These methods are applied to several families of equations. The Rado number of an equation is a Ramsey-theoretic quantity associated to the equation. For any particular equation E, the Rado number R_r(E) is the smallest N such that any r-coloring chi:{1,2,...,N} -> {1,2,...,r} must induce a monochromatic solution to E. We will lay out the history of this field and provide some structure as context for new results. Then we will discuss the new methods and computational tools that provide the foundation of the thesis. The 2-color Rado numbers R_2(2x+2y+kz = 3w) and R_2(kx+(k+1)y = (k+2)z) are computed for small values of the parameter k. The 2-color off-diagonal Rado numbers R_2(x + ay = z; x + by = z) are provided for 1 = (3^r - 1)(c+1)/2 for c >= 0. We also compute the precise values for r = 4 and -20 = 3 variables. We provide the 2-color Rado numbers for 1/x + 1/y = 1/z and a few other equations involving reciprocals. We also construct a coloring proving R_2(x^2 + y^2 = z^2) > 6500. (It is not known whether this Rado number is finite.) We compute the 2- and 3-color Rado numbers for other sums-of-squares equations, sum_{i=1}^a x_i^2) = sum_{i=1}^b y_i^2, and we prove a universal upper bound for a <= b <= ca for a constant c between 1 and 2 (different values of c give different upper bounds). We follow this with Rado numbers for other assorted families of quadratic equations. We also present quantitative analogues of Hindman's theorem, which guarantees monochromatic solutions to systems like {x+y+z = w; x*y*z = v}. We conclude by suggesting a number of conjectures, extensions, and generalizations of these results for future work.Ph.D.Includes bibliographical referencesby Kellen John Myer
On Erdős-Ko-Rado for random hypergraphs
No full textOn Erdős-Ko-Rado for Random Hypergraphs o by Arran Hamm Dissertation Director: Jeff Kahn Denote by Hk (n, p) the random k-graph in which each k-subset of {1, . . . , n} is present with probability p, independent of other choices. This dissertation addresses the question: for which p0 will Hk (n, p) satisfy the “Erd˝s-Ko-Rado property” provided that o p > p0 ? This question was first studied by Balogh, Bohman, and Mubayi where they dealt mainly with k 0). Our first main result gives the desired p0 when k 0 such that if n = 2k + 1 and p > 1 − ε, then Hk (n, p) has the EKR property a.s. iiPh.D.Includes bibliographical referencesby Arran Ham
Element-Distinct Solution For Rado\u27s Theorem
No full textIn this paper, we present a simplified proof of Rado\u27s Theorem and demonstrate that when an integer matrix satisfies the column condition and has an element-distinct solution on , then under any finite coloring of , the equation has a monochromatic element-distinct solution. This gives a positive answer to a problem of Di Nasso in 2016.The main conclusions presented in this paper have been proven previously by others, and the original author has contacted me. I believe the paper should be withdraw
Erdős-Ko-Rado theorems for set partitions with certain block size
No full textIn this paper, we prove Erdős-Ko-Rado type results for (a) family of set partitions where the size of each block is a multiple of k; and (b) family of set partitions with minimum block size k.The author Kok Bin Wong was supported by the University of Malaya Research Grant GPF025B-2018
Erdos--Ko--Rado Theorems: New Generalizations, Stability Analysis and Chvatal's Conjecture
No full textabstract: The primary focus of this dissertation lies in extremal combinatorics, in particular intersection theorems in finite set theory. A seminal result in the area is the theorem of Erdos, Ko and Rado which finds the upper bound on the size of an intersecting family of subsets of an n-element set and characterizes the structure of families which attain this upper bound. A major portion of this dissertation focuses on a recent generalization of the Erdos--Ko--Rado theorem which considers intersecting families of independent sets in graphs. An intersection theorem is proved for a large class of graphs, namely chordal graphs which satisfy an additional condition and similar problems are considered for trees, bipartite graphs and other special classes. A similar extension is also formulated for cross-intersecting families and results are proved for chordal graphs and cycles. A well-known generalization of the EKR theorem for k-wise intersecting families due to Frankl is also considered. A stability version of Frankl's theorem is proved, which provides additional structural information about k-wise intersecting families which have size close to the maximum upper bound. A graph-theoretic generalization of Frankl's theorem is also formulated and proved for perfect matching graphs. Finally, a long-standing conjecture of Chvatal regarding structure of maximum intersecting families in hereditary systems is considered. An intersection theorem is proved for hereditary families which have rank 3 using a powerful tool of Erdos and Rado which is called the Sunflower Lemma.Dissertation/ThesisPh.D. Mathematics 201
Informacijska revolucija v izobraževanju
Get PDFThe information technology revolutionary changes our everyday life. There is nothing as it was once and also education is changing and should change. Actual question, we are discussing about in this article, is what knowledge and skills are essential and should be developed during education in youth to qualify pupils for active cooperation and having the authority to decide in the coming world future society.Informacijska tehnologija revolucionarno spreminja naš vsakdan. Nič ni več tako, kot je bilo nekoč, in tudi izobraževanje se spreminja in se mora spreminjati. Aktualno vprašanje, o katerem razpravljamo v članku, je, kakšno znanje in kakšne spretnosti naj učenci razvijajo z izobraževanjem v mladosti ter na kakšen način, da bodo kot odrasli lahko aktivno sodelovali in odločali v družbi, ki prihaja
Towards a general theory of Erdős-Ko-Rado combinatorics
Get PDF2014 Summer.Includes bibliographical references.In 1961, Erdős, Ko, and Rado proved that for a universe of size n ≥ 2k a family of k-subsets whose members pairwise intersect cannot be larger than n-1/k-1. This fundamental result of extremal combinatorics is now known as the EKR theorem for intersecting set families. Since then, there has been a proliferation of similar EKR theorems in extremal combinatorics that characterize families of more sophisticated objects that are largest with respect to a given intersection property. This line of research has given rise to many interesting combinatorial and algebraic techniques, the latter being the focus of this thesis. Algebraic methods for EKR results are attractive since they could potentially give rise to a unified theory of EKR combinatorics, but the state-of-the-art has been shown only to apply to sets, vector spaces, and permutation families. These categories lie on opposite ends of the stability spectrum since the stabilizers of sets and vector spaces are large as possible whereas the stabilizer of a permutation is small as possible. In this thesis, we investigate a category that lies somewhere in between, namely, the perfect matchings of the complete graph. In particular, we show that an algebraic method of Godsil's can be lifted to the more general algebraic framework of Gelfand pairs, giving the first algebraic proof of the EKR theorem for intersecting families of perfect matchings as a consequence. There is strong evidence to suggest that this framework can be used to approach the open problem of characterizing the maximum t-intersecting families of perfect matchings, whose combinatorial proof remains illusive. We conclude with obstacles and open directions for extending this framework to encompass a broader spectrum of categories
Borel sets of Rado graphs and Ramsey\u27s Theorem
Get PDFThe well-known Galvin-Prikry Theorem states that Borel subsets of the Baire space are Ramsey: Given any Borel subset , where is endowed with the metric topology, each infinite subset contains an infinite subset such that is either contained in or disjoint from . Kechris, Pestov, and Todorcevic point out in their seminal 2005 paper the dearth of similar results for homogeneous structures. Such results are a necessary step to the larger goal of finding a correspondence between structures with infinite dimensional Ramsey properties and topological dynamics, extending their correspondence between the Ramsey property and extreme amenability. In this article, we prove an analogue of the Galvin-Prikry theorem for the Rado graph. Any such infinite dimensional Ramsey theorem is subject to constraints following from the 2006 work of Laflamme, Sauer, and Vuksanovic. The proof uses techniques developed for the author\u27s work on the Ramsey theory of the Henson graphs as well as some new methods for fusion sequences, used to bypass the lack of a certain amalgamation property enjoyed by the Baire space.Glitch in proof of Theorem 5.4 fixed, applying methods from arXiv:2203.00169. To appear in the European Journal of Combinatorics special issue for the Prague 2016 Ramsey Theory DocCours
Harmony and discord within the English ‘counter-culture’, 1965-1975, with particular reference to the ‘rock operas’ Hair, Godspell, Tommy and Jesus Christ Superstar
No full textPhDThis thesis considers the discrete, historically-specific theatrical and musical sub-genre of ‘Rock Opera’ as a lens through which to examine the cultural, political and social changes that are widely assumed to have characterised ‘The Sixties’ in Britain. The musical and dramatic texts, creation and production of Hair (1967), Tommy (1969), Godspell (1971), Jesus Christ Superstar (1970) and other neglected ‘Rock Operas’ of the period are analysed. Their great popularity with ‘mainstream’ audiences is considered and contrasted with the overwhelmingly negative and often internally contradictory reaction towards them from the English ‘counter-culture’. This examination offers new insights into both the ‘counter-culture’ and the ‘mainstream’ against which it claimed to define and differentiate itself.
The four ‘Rock Operas’, two of which are based upon Christian scriptures, are considered as narratives of spiritual quest. The relationship between the often controversial quests for re-defined forms of faith and the apparently precipitous ‘secularization’ and ‘de-Christianization’ of British society during the 1960s and 1970s is considered.
The thesis therefore analyses the ‘Rock Operas’ as significant, enlightening prisms through which to view many of the profound societal debates – over ‘faith’ and ‘belief’ in the widest senses, sexuality, the Vietnam war, generational conflict, drugs and ‘spiritual enlightenment’, and race – which were, to some considerable extent, elevated onto the national, political agenda by the activities of the broadly-defined ‘counter-culture’. It considers subsequent representations of the ‘counter-culture’ as the root of a contested but enduring popular legacy of ‘The Sixties' as a period of profound cultural change
Radon testing in private school buildings / by Marybeth Sullivan, senior legislative attorney
No full text1 online resource (2 pages)"December 14, 2020."Discusses whether Connecticut or any other state requires private schools to test their buildings for rado
- …
