- You are here:
- GT Home
- Home
- News & Events
Series: Graph Theory Seminar
To
any finite real sequence, we can associate a permutation $\pi$, via:
$\pi(k)$ is the index of the $k$th smallest element of the sequence.
This association was introduced in a 1987 paper
of Alavi, Malde, Schwenk and Erd\H{o}s, where they used it to study the
possible patterns of rises and falls that can occur in the matching
sequence of a graph (the sequence whose $k$th term is the number of
matchings of size $k$), and in the independent set
sequence.
The
main result of their paper was that {\em every} permutation can arise
as the ``independent set permutation'' of some graph. They left open the
following extremal question: for each $n$, what is
the smallest order $m$ such that every permutation of $[n]$ can be
realized as the independent set permutation of some graph of order at
most $m$?
We
answer this question. We also improve Alavi et al.'s upper bound on the
number of permutations that can be realized as the matching permutation
of some graph. There are still many open questions
in this area.
This is joint work with T. Ball, K. Hyry and K. Weingartner, all at Notre Dame.
Series: Graph Theory Working Seminar
The well known Erdos-Hajnal Conjecture states that every graph has the Erdos-Hajnal (EH) property. That is, for every $H$, there exists a $c=c(H)>0$ such that every graph $G$ with no induced copy of $H$ has the property $hom(G):=max\{\alpha(G),\omega(G)\}\geq |V(G)|^{c}$. Let $H,J$ be subdivisions of caterpillar graphs. Liebenau, Pilipczuk, Seymour and Spirkl proved that the EH property holds if we forbid both $H$ and $\overline{J}.$ We will discuss the proof of this result.
Series: High Dimensional Seminar
We discuss the asymptotic value of the maximal perimeter of a convex set in an n-dimensional space with respect to certain classes of measures. Firstly, we derive a lower bound for this quantity for a large class of probability distributions; the lower bound depends on the moments only. This lower bound is sharp in the case of the Gaussian measure (as was shown by Nazarov in 2001), and, more generally, in the case of rotation invariant log-concave measures (as was shown by myself in 2014). We discuss another class of measures for which this bound is sharp. For isotropic log-concave measures, the value of the lower bound is at least n^{1/8}.
In addition, we show a uniform upper bound of Cn||f||^{1/n}_{\infty} for all log-concave measures in a special position, which is attained for the uniform distribution on the cube. We further estimate the maximal perimeter of isotropic log-concave measures by n^2.
Wednesday, April 17, 2019 - 14:00 ,
Location: Skiles 006 ,
Sudipta Kolay ,
Georgia Tech ,
Organizer: Sudipta Kolay
We will see some instances of swindles in mathematics, primarily focusing on some in geometric topology due to Barry Mazur.
Series: Research Horizons Seminar
I will briefly present our Stochastics Group and its main interests, and will continue with some of the problems I have worked on in recent years.
Series: Dissertation Defense
Optimal transport is a thoroughly studied field in mathematics and introduces the concept of Wasserstein distance, which has been widely used in various applications in computational mathematics, machine learning as well as many areas in engineering. Meanwhile, control theory and path planning is an active branch in mathematics and robotics, focusing on algorithms that calculates feasible or optimal paths for robotic systems. In this defense, we use the properties of the gradient flows in Wasserstein metric to design algorithms to handle different types of path planning and control problems as well as the K-means problems defined on graphs.
Series: PDE Seminar
I this talk I will summerize some of our contributions in the analysis of parabolic elliptic Keller-Segel system, a typical model in chemotaxis. For the case of linear diffusion, after introducing the critical mass in two dimension, I will show our result for blow-up conditions for higher dimension. The second part of the talk is concentrated in the critical exponent for Keller-Segel system with porus media type diffusion. In the end, motivated from the result on nonlocal Fisher-KPP equation, we show that the nonlocal reaction will also help in preventing the blow-up of the solutions.
Series: Algebra Seminar
Wachspress defined barycentric coordinates on polygons in 1975. Warren generalized his construction to higher dimensional polytopes in 1996. In contrast to the classical case of simplices, barycentric coordinates on other polytopes are not unique. So the coordinates defined by Warren are now commonly known as Wachspress coordinates. They are used in a variety of applications, such as geometric modeling.
We connect the constructions by Warren and Wachspress by proving the conjecture that there is a unique polynomial of minimal degree which vanishes on the non-faces of a simple polytope. This is the adjoint polynomial introduced by Warren. Our formulation is the natural generalization of Wachspress' original idea.
The algebraic geometry of the map defined by the Wachspress coordinates was studied in the case of polygons by Irving and Schenk in 2014. We extend their results to higher dimensional polytopes. In particular, we show that the image of this Wachspress map is the projection from the image of the adjoint. For three-dimensional polytopes, we show that their adjoints are adjoints of K3- or elliptic surfaces. This talk is based on joint works with Kristian Ranestad, Boris Shapiro and Bernd Sturmfels.
Series: Geometry Topology Seminar
The question of which high-dimensional knots are slice was entirely solved by Kervaire and Levine. Compared to this, the question of which knots are doubly slice in high-dimensions is still a largely open problem. Ruberman proved that in every dimension, some version of the Casson-Gordon invariants can be applied to obtain algebraically doubly slice knots that are not doubly slice. I will show how to use L^2 signatures to recover the result of Ruberman for (4k-3)-dimensional knots, and discuss how the derived series of the knot group might be used to organise the high-dimensional doubly slice problem.
Monday, April 15, 2019 - 13:55 ,
Location: Skiles 005 ,
Shuyang Ling ,
New York University ,
sling@cims.nyu.edu ,
Organizer: Wenjing Liao
Information retrieval from graphs plays an increasingly important role in data science and machine learning. This talk focuses on two such examples. The first one concerns the graph cuts problem: how to find the optimal k-way graph cuts given an adjacency matrix. We present a convex relaxation of ratio cut and normalized cut, which gives rise to a rigorous theoretical analysis of graph cuts. We derive deterministic bounds of finding the optimal graph cuts via a spectral proximity condition which naturally depends on the intra-cluster and inter-cluster connectivity. Moreover, our theory provides theoretic guarantees for spectral clustering and community detection under stochastic block model. The second example is about the landscape of a nonconvex cost function arising from group synchronization and matrix completion. This function also appears as the energy function of coupled oscillators on networks. We study how the landscape of this function is related to the underlying network topologies. We prove that the optimization landscape has no spurious local minima if the underlying network is a deterministic dense graph or an Erdos-Renyi random graph. The results find applications in signal processing and dynamical systems on networks.
Pages
Georgia Institute of Technology
North Avenue, Atlanta, GA 30332
Phone: 404-894-2000