Georgia Institute of Technology College of Sciences

The crossing number of a graph is the minimum number of crossings it can be drawn in a plane. Let $\kappa(n, m)$ be the minimum crossing number of graphs with $n$ vertices and (at least) $m$ edges. Erd\H{o}s and Guy conjectured and Pach, Spencer and T\'oth proved that for any $m = m(n)$ satisfying $n \ll m \ll n^2$, the quatity $\ds\lim_{n \to \infty} \frac{\kappa(n,m) n^2}{m^3}$ exists and is positive. The $k$-planar crossing number of a graph is the minimum crossing number obtained when we partition the edges of the graph into $k$ subgraphs and draw them in $k$ planes. Using designs and a probabilistic algorithm, the guaranteed factor of improvement $\alpha_k$ between the $k$-planar and regular crossing number is $\frac{1}{k^2} (1 + o(1))$, while if we restrict our attention to biplanar graphs, this constant is $\beta_k = \frac{1}{k^2}$ exactly. The lower bound proofs require the existence of a midrange crossing constant. Motivated by this, we show that the midrange crossing constant exists for all graph classes (including bipartite graphs) that satisfy certain mild conditions. The regular midrange crossing constant was shown to be is at most $\frac{8}{9\pi^2}$; we present a probabilistic construction that also shows this bound.
 

In 1946, Dennis Gabor claimed that any Lebesgue square-integrable function can be written as an infinite linear combination of time and frequency shifts of the standard Gaussian.  Since then, decomposition methods for larger classes of functions or distributions in terms of various elementary building blocks have lead to an impressive body of work in harmonic analysis. For example, Gabor analysis, which originated from Gabor's claim, is concerned with both the theory and the applications of the approximation properties of sets of time and frequency shifts of a given function. It re-emerged with the advent of wavelets at the end of the last century and is now at the intersection of many fields of mathematics, applied mathematics, engineering, and science. In this talk, I will introduce the fundamentals of the theory highlighting some applications and open problems.

Erdős, Pach, Pollack and Tuza conjectured that for fixed integers $r$, $\delta \ge 2$, for any connected graph $G$ with minimum degree $\delta$ and order $n$:

(i) If $G$ is $K_{2r}$-free and $\delta$ is a multiple of $(r-1)(3r+2)$, then, as $n$ tends to infinity, the diameter of $G$ is at most $\frac{2(r-1)(3r+2)}{(2r^2-1)} \cdot \frac{n}{\delta} + O(1)$.

(ii) If $G$ is $K_{2r+1}$-free and $\delta$ is a multiple of $3r-1$, then, as $n$ tends to infinity, the diameter of $G$ is at most $\frac{3r-1}{r} \cdot \frac{n}{\delta} + O(1)$.

They created examples that show that the above conjecture, if true, is tight.

No more progress has been reported on this conjecture, except that for $r=2$ in (ii), under a stronger hypothesis ($4$-colorable instead of $K_5$-free), Czabarka, Dankelman and Székely showed that for every connected $4$-colorable graph $G$ of order $n$ and minimum degree $\delta \ge 1$, the diameter of $G$ is at most $\frac{5n}{2\delta} - 1$.

For every $r>1$ and $\delta \ge 2(r-1)$, we create $K_{2r}$-free graphs with minimum degree $\delta$ and diameter $\frac{(6r-5)n}{(2r-1)\delta+2r-3}+O(1)$, which are counterexamples to the conjecture for every $r>1$ and $\delta > 2(r-1)(3r+2)(2r-3)$. We also prove positive results under a stronger hypothesis, $k$-colorability, instead of being $K_{k+1}$-free. We show that the diameter of connected $k$-colorable graphs with minimum degree at least $\delta$ and order $n$ is at most $\left(3-\frac{1}{k-1}\right)\frac{n}{\delta}+O(1)$, while for $k=3$, it is at most $\frac{57n}{23\delta}+O(1)$.

This is joint work with Inne Singgih and László A. Székely.

In 1665, Huygens observed that two pendulum clocks hanging from the same board became synchronized in antiphase after hundreds of swings. On the other hand, modern experiments with metronomes placed on a movable platform show that they tend to synchronize in phase, not antiphase. Here, using a simple model of coupled clocks and metronomes, we calculate the regimes where antiphase and in-phase synchronization are stable. Unusual features of our approach include its treatment of the escapement mechanism, a small-angle approximation up to cubic order, and a three-time scale asymptotic analysis.