Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA List of Problems on the Reverse Mathematics of Ramsey Theory on the Rado Graph and on Infinite, Finitely Branching Trees
108
0
0.0
(
0
)
Authors
Natasha Dobrinen
Ask ChatGPT about the research
No Arabic abstract
This list presents problems in the Reverse Mathematics of infinitary Ramsey theory which I find interesting but do not personally have the techniques to solve. The intent is to enlist the help of those working in Reverse Mathematics to take on such problems, and the myriad of related questions one can infer from them. A short bit of background and starting references are provided.
rate research
Read More
This article discusses some recent trends in Ramsey theory on infinite structures. Trees and their Ramsey theory have been vital to these investigations. The main ideas behind the authors recent method of trees with coding nodes are presented, showing how they can be useful both for coding structures with forbidden configurations as well as those with none. Using forcing as a tool for finite searches has allowed the development of Ramsey theory on such trees, leading to solutions for finite big Ramsey degrees of Henson graphs as well as infinite dimensional Ramsey theory of copies of the Rado graph. Possible future directions for applications of these methods are discussed.
This paper is aimed to investigate some computational aspects of different isoperimetric problems on weighted trees. In this regard, we consider different connectivity parameters called {it minimum normalized cuts}/{it isoperimteric numbers} defined through taking minimum of the maximum or the mean of the normalized outgoing flows from a set of subdomains of vertices, where these subdomains constitute a {it partition}/{it subpartition}. Following the main result of [A. Daneshgar, {it et. al.}, {it On the isoperimetric spectrum of graphs and its approximations}, JCTB, (2010)], it is known that the isoperimetric number and the minimum normalized cut both can be described as ${0,1}$-optimization programs, where the latter one does {it not} admit a relaxation to the reals. We show that the decision problem for the case of taking $k$-partitions and the maximum (called the max normalized cut problem {rm NCP}$^M$) as well as the other two decision problems for the mean version (referred to as {rm IPP}$^m$ and {rm NCP}$^m$) are $NP$-complete problems. On the other hand, we show that the decision problem for the case of taking $k$-subpartitions and the maximum (called the max isoperimetric problem {rm IPP}$^M$) can be solved in {it linear time} for any weighted tree and any $k geq 2$. Based on this fact, we provide polynomial time $O(k)$-approximation algorithms for all differe
Using the tools of reverse mathematics in second-order arithmetic, as developed by Friedman, Simpson, and others, we determine the axioms necessary to develop various topics in commutative ring theory. Our main contributions to the field are as follows. We look at fundamental results concerning primary ideals and the radical of an ideal, concepts previously unstudied in reverse mathematics. Then we turn to a fine-grained analysis of four different definitions of Noetherian in the weak base system $mathsf{RCA}_0 + mathsf{I}Sigma_2$. Finally, we begin a systematic study of various types of integral domains: PIDs, UFDs and Bezout and GCD domains.
The Jordan decomposition theorem states that every function $f colon [0,1] to mathbb{R}$ of bounded variation can be written as the difference of two non-decreasing functions. Combining this fact with a result of Lebesgue, every function of bounded variation is differentiable almost everywhere in the sense of Lebesgue measure. We analyze the strength of these theorems in the setting of reverse mathematics. Over $mathsf{RCA}_0$, a stronger version of Jordans result where all functions are continuous is equivalent to $mathsf{ACA}_0$, while the version stated is equivalent to $mathsf{WKL}_0$. The result that every function on $[0,1]$ of bounded variation is almost everywhere differentiable is equivalent to $mathsf{WWKL}_0$. To state this equivalence in a meaningful way, we develop a theory of Martin-Lof randomness over $mathsf{RCA}_0$.
Consider a uniformly sampled random $d$-regular graph on $n$ vertices. If $d$ is fixed and $n$ goes to $infty$ then we can relate typical (large probability) properties of such random graph to a family of invariant random processes (called typical processes) on the infinite $d$-regular tree $T_d$. This correspondence between ergodic theory on $T_d$ and random regular graphs is already proven to be fruitful in both directions. This paper continues the investigation of typical processes with a special emphasis on entropy. We study a natural notion of micro-state entropy for invariant processes on $T_d$. It serves as a quantitative refinement of the notion of typicality and is tightly connected to the asymptotic free energy in statistical physics. Using entropy inequalities, we provide new sufficient conditions for typicality for edge Markov processes. We also extend these notions and results to processes on unimodular Galton-Watson random trees.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
