Tue, 19 Jan 2016
14:30
L6

Excluding Holes

Paul Seymour
(Princeton)
Abstract

A "hole" in a graph is an induced subgraph which is a cycle of length > 3. The perfect graph theorem says that if a graph has no odd holes and no odd antiholes (the complement of a hole), then its chromatic number equals its clique number; but unrestricted graphs can have clique number two and arbitrarily large chromatic number. There is a nice question half-way between them - for which classes of graphs is it true that a bound on clique number implies some (larger) bound on chromatic number? Call this being "chi-bounded".

Gyarfas proposed several conjectures of this form in 1985, and recently there has been significant progress on them. For instance, he conjectured

  • graphs with no odd hole are chi-bounded (this is true);
  • graphs with no hole of length >100 are chi-bounded (this is true);
  • graphs with no odd hole of length >100 are chi-bounded; this is still open but true for triangle-free graphs.

We survey this and several related results. This is joint with Alex Scott and partly with Maria Chudnovsky.

Tue, 21 May 2013

14:30 - 15:30
L3

Criticality for multicommodity flows

Paul Seymour
(Princeton)
Abstract

The ``k-commodity flow problem'' is: we are given k pairs of vertices of a graph, and we ask whether there are k flows in the graph, where the ith flow is between the ith pair of vertices, and has total value one, and for each edge, the sum of the absolute values of the flows along it is at most one. We may also require the flows to be 1/2-integral, or indeed 1/p-integral for some fixed p.

If the problem is feasible (that is, the desired flows exist) then it is still feasible after contracting any edge, so let us say a flow problem is ``critical'' if it is infeasible, but becomes feasible when we contract any edge. In many special cases, all critical instances have only two vertices, but if we ask for integral flows (that is, p = 1, essentially the edge-disjoint paths problem), then there arbitrarily large critical instances, even with k = 2. But it turns out that p = 1 is the only bad case; if p>1 then all critical instances have bounded size (depending on k, but independent of p), and the same is true if there is no integrality requirement at all.

The proof gives rise to a very simple algorithm for the k edge-disjoint paths problem in 4-edge-connected graphs.

Thu, 02 May 2013

16:00 - 17:00
L3

Elliptic curves with rank one

Chris Skinner
(Princeton)
Abstract

I will discuss some p-adic (and mod p) criteria ensuring that an elliptic curve over the rationals has algebraic and analytic rank one, as well as some applications.

Thu, 20 Sep 2012

10:15 - 11:15
OCCAM Common Room (RI2.28)

Transport through composite membranes: Support properties, film morphology and their impact on flux, rejection and fouling

Guy Ramon
(Princeton)
Abstract

Composite membranes comprised of an ultra-thin coating film formed over a porous support membrane are the basis for state-of-the-art reverse osmosis (RO) and nanofiltration (NF) membranes, offering the possibility to independently optimize the support membrane and the coating film. However, limited information exists on transport through such composite membrane structures. Numerical calculations have been carried out in order to probe the impacts of the support membrane skin-layer pore size and porosity, support membrane bulk micro-porosity, and coating film thickness and morphology (i.e. surface roughness) on solvent and solute transport through composite membranes. Results suggest that the flux and rejection of a composite membrane may be fine-tuned, by adjusting support membrane skin layer porosity and pore size, independent of the properties of the coating film. Further, the water flux over the membrane surface is unevenly distributed, creating local ‘hot spots’ of high flux that may govern initial stages of membrane fouling and scaling. The analysis provides important insight on how the non-trivial interaction of support properties and film roughness may result in widely varying transport properties of the composite structure. In particular, the simulations reveal inherent trade-offs between flux, rejection and fouling propensity (the latter due to ‘hot spots’), which are purely consequences of geometrical factors, irrespective of materials chemistry.

Fri, 08 Jun 2012
15:00
Gibson 1st Floor SR

One-Loop Renormalization and the S-matrix

David McGady
(Princeton)
Abstract

Abstract: In this talk, I will discuss the proportionality between tree amplitudes and the ultraviolet divergences in their one-loop corrections in Yang-Mills and (N < 4) Super Yang-Mills theories in four-dimensions. From the point of view of local perturbative quantum field theory, i.e. Feynman diagrams, this proportionality is straightforward: ultraviolet divergences at loop-level are absorbed into coefficients of local operators/interaction vertices in the original tree-amplitude. Ultraviolet divergences in loop amplitudes are also calculable through on-shell methods. These methods ensure manifest gauge-invariance, even at loop-level (no ghosts), at the expense of manifest locality. From an on-shell perspective, the proportionality between the ultraviolet divergences the tree amplitudes is thus not guaranteed. I describe systematic structures which ensure proportionality, and their possible connections to other recent developments in the field.

Wed, 07 Mar 2012

10:15 - 11:15
OCCAM Common Room (RI2.28)

The graph realization problem and eigenvector synchronization

Mihai Cucuringu
(Princeton)
Abstract

The graph realization problem has received a great deal of attention in recent years, due to its importance in applications such as wireless sensor networks and structural biology. We introduce the ASAP algorithm, for the graph realization problem in R^d, given a sparse and noisy set of distance measurements associated to the edges of a globally rigid graph. ASAP is a divide and conquer, non-incremental and non-iterative algorithm, which integrates local distance information into a global structure determination. Our approach starts with identifying, for every node, a subgraph of its 1-hop neighborhood graph, which can be accurately embedded in its own coordinate system. In the noise-free case, the computed coordinates of the sensors in each patch must agree with their global positioning up to some unknown rigid motion, that is, up to translation, rotation and possibly reflection. In other words, to every patch there corresponds an element of the Euclidean group Euc(3) of rigid transformations in R^3, and the goal is to estimate the group elements that will properly align all the patches in a globally consistent way. The reflections and rotations are estimated using a recently developed eigenvector synchronization algorithm, while the translations are estimated by solving an overdetermined linear system. Furthermore, the algorithm successfully incorporates information specific to the molecule problem in structural biology, in particular information on known substructures and their orientation. In addition, we also propose SP-ASAP, a faster version of ASAP, which uses a spectral partitioning algorithm as a preprocessing step for dividing the initial graph into smaller subgraphs. Our extensive numerical simulations show that ASAP and SP-ASAP are very robust to high levels of noise in the measured distances and to sparse connectivity in the measurement graph, and compare favorably to similar state-of-the art localization algorithms. Time permitting, we briefly discuss the analogy between the graph realization and the low-rank matrix completion problems, as well as an application of synchronization over Z_2 and its variations to bipartite multislice networks.

Subscribe to Princeton