Georgia Institute of Technology College of Sciences

A graph is (t+1)-critical if it is not t-colorable, but every proper subgraph is. In this thesis, we study the structure of critical graphs on higher surfaces. One major result in this area is Carsten Thomassen's proof that there are finitely many 6-critical graphs on a fixed surface. This proof involves a structural theorem about a precolored cycle C of length q. In general terms, he proves that a coloring \phi of C can be extended inside the cycle, or there exists a subgraph H with at most 5^{q^3} vertices such that \phi cannot be extended to a 5-coloring of H. In Chapter 2, we provide an alternative proof that reduces the number of vertices in H to be cubic in q. In Chapter 3, we find the nine 6-critical graphs among all graphs embeddable on the Klein bottle. Finally, in Chapter 4, we prove a result concerning critical graphs related to an analogue of Steinberg's conjecture for higher surfaces. We show that if G is a 4-critical graph embedded on surface \Sigma, with Euler genus g and has no cycles of length four through ten, then |V(G)| \leq 2442g + 37.

A construction is given for which the Hausdorff measure and dimension of an arbitrary abstract compact metric space (X, d) can be encoded in a spectral triple. By introducing the concept of resolving sequence of open covers, conditions are given under which the topology, metric, and Hausdorff measure can be recovered from a spectral triple dependent on such a sequence. The construction holds for arbitrary compact metric spaces, generalizing previous results for fractals, as well as the original setting of manifolds, and also holds when Hausdorff and box dimensions differ—in particular, it does not depend on any self-similarity or regularity conditions on the space or an embedding in an ambient space. The only restriction on the space is that it have positive s-dimensional Hausdorff measure, where s is the Hausdorff dimension of the space, assumed to be finite.

We improve the lower bound for the L_\infty norm of the discrepancy function. This result makes a partial step towards resolving the Discrepancy Conjecture. Being a theorem in the theory of irregularities of distributions, it also relates to corresponding results in approximation theory (namely, the Kolmogorov entropy of spaces of functions with bounded mixed derivatives) and in probability theory (namely, Small Ball Inequality - small deviation inequality for the Brownian sheet). We also provide sharp bounds for the exponential Orlicz norm and the BMO norm of the discrepancy function in two dimensions. In the second part of the thesis we prove that any sufficiently smooth one-dimensional Calderon-Zygmund convolution operator can be recovered through averaging of Haar shift operators. This allows to generalize the estimates, which had been previously known for Haar shift operators, to Calderon-Zygmund operators. As a result, the A_2 conjecture is settled for this particular type of Calederon-Zygmund operators.

This thesis addresses four topics in the area of applied harmonic analysis. First, we show that the affine densities of separable wavelet frames affect the frame properties. In particular, we describe a new relationship between the affine densities, frame bounds and weighted admissibility constants of the mother wavelets of pairs of separable wavelet frames. This result is also extended to wavelet frame sequences. Second, we consider affine pseudodifferential operators, generalizations of pseudodifferential operators that model wideband wireless communication channels. We find two classes of Banach spaces, characterized by wavelet and ridgelet transforms, so that inclusion of the kernel and symbol in appropriate spaces ensures the operator if Schatten p-class. Third, we examine the Schatten class properties of pseudodifferential operators. Using Gabor frame techniques, we show that if the kernel of a pseudodifferential operator lies in a particular mixed modulation space, then the operator is Schatten p-class. This result improves existing theorems and is sharp in the sense that larger mixed modulation spaces yield operators that are not Schatten class. The implications of this result for the Kohn-Nirenberg symbol of a pseudodifferential operator are also described. Lastly, Fourier integral operators are analyzed with Gabor frame techniques. We show that, given a certain smoothness in the phase function of a Fourier integral operator, the inclusion of the symbol in appropriate mixed modulation spaces is sufficient to guarantee that the operator is Schatten p-class.