Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExtra pearls in graph theory
92
0
0.0
(
0
)
Authors
Anton Petrunin
Ask ChatGPT about the research
No Arabic abstract
This is a supplement for Pearls in graph theory -- a textbook written by Nora Hartsfield and Gerhard Ringel. Probabilistic method, Deletion-contraction formulas, Matrix theorem, Graph-polynomials, Generating functions, Minimum spanning trees, Marriage theorem and its relatives, Toroidal graphs, Rado graph.
rate research
Read More
This book is based on Graph Theory courses taught by P.A. Petrosyan, V.V. Mkrtchyan and R.R. Kamalian at Yerevan State University.
In this note we study graphs $G_r$ with the property that every colouring of $E(G_r)$ with $r+1$ colours admits a copy of some graph $H$ using at most $r$ colours. For $1le rle e(H)$ such graphs occur naturally at intermediate steps in the synthesis of a $2$-colour Ramsey graph $G_1longrightarrow H$. (The corresponding notion of Ramsey-type numbers was introduced by Erdos, Hajnal and Rado in 1965 and subsequently studied by Erdos and Szemeredi in 1972). For $H=K_n$ we prove a result on building a $G_{r}$ from a $G_{r+1}$ and establish Ramsey-infiniteness. From the structural point of view, we characterise the class of the minimal $G_r$ in the case when $H$ is relaxed to be the graph property of containing a cycle; we then use it to progress towards a constructive description of that class by proving both a reduction and an extension theorem.
The study of intersection problems in Extremal Combinatorics dates back perhaps to 1938, when Paul ErdH{o}s, Chao Ko and Richard Rado proved the (first) `ErdH{o}s-Ko-Rado theorem on the maximum possible size of an intersecting family of $k$-element subsets of a finite set. Since then, a plethora of results of a similar flavour have been proved, for a range of different mathematical structures, using a wide variety of different methods. Structures studied in this context have included families of vector subspaces, families of graphs, subsets of finite groups with given group actions, and of course uniform hypergraphs with stronger or weaker intersection conditions imposed. The methods used have included purely combinatorial ones such as shifting/compressions, algebraic methods (including linear-algebraic, Fourier analytic and representation-theoretic), and more recently, analytic, probabilistic and regularity-type methods. As well as being natural problems in their own right, intersection problems have connections with many other parts of Combinatorics and with Theoretical Computer Science (and indeed with many other parts of Mathematics), both through the results themselves, and the methods used. In this survey paper, we discuss both old and new results (and both old and new methods), in the field of intersection problems. Many interesting open problems remain; we will discuss several. For expositional and pedagogical purposes, we also take this opportunity to give slightly streamlin
We survey the published work of Harry Kesten in probability theory, with emphasis on his contributions to random walks, branching processes, percolation, and related topics. A complete bibliography is included of his publications.
Our goal is to present the basic results on one-dimensional Gibbs and equilibrium states viewed as special invariant measures on symbolic dynamical systems, and then to describe without technicalities a sample of results they allowed to obtain for certain differentiable dynamical systems. We hope that this contribution will illustrate the symbiotic relationship between ergodic theory and statistical mechanics, and also information theory.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
