Vertex Set Partitions Preserving Conservativeness

Let G be an undirected graph and ={X₁, …, X_n} be a partition of V(G). Denote by G/ the graph which has vertex set {X₁, …, X_n}, edge set E, and is obtained from G by identifying vertices in each class X_i of the partition . Given a conservative graph (G, w), we study vertex set partitions preserving conservativeness, i.e., those for which (G/ , w) is also a conservative graph. We characterize the conservative graphs (G/ , w), where is a terminal partition of V(G) (a partition preserving conservativeness which is not a refinement of any other partition of this kind). We prove that many conservative graphs admit terminal partitions with some additional properties. The results obtained are then used in new unified short proofs for a co-NP characterization of Seymour graphs by A. A. Ageev, A. V. Kostochka, and Z. Szigeti (1997, J. Graph Theory34, 357–364), a theorem of E. Korach and M. Penn (1992, Math. Programming55, 183–191), a theorem of E. Korach (1994, J. Combin. Theory Ser. B62, 1–10), and a theorem of A. V. Kostochka (1994, in “Discrete Analysis and Operations Research. Mathematics and its Applications (A. D. Korshunov, Ed.), Vol. 355, pp. 109–123, Kluwer Academic, Dordrecht).     

De Bruijn digraphs and affine transformations

Let be the additive group of 1×n row vectors over . For an n×n matrix T over  and , the affine transformation F_T,ω of sends x to xT+ω. Let α be the cyclic group generated by a vector . The affine transformation coset pseudo-digraph has the set of cosets of α in as vertices and there are c arcs from x+α to y+α if and only if the number of zx+α such that F_T,ω(z)y+α is c. We prove that the following statements are equivalent: (a)  is isomorphic to the d-nary (n−1)-dimensional De Bruijn digraph; (b) α is a cyclic vector for T; (c)  is primitive. This strengthens a result conjectured by C.M. Fiduccia and E.M. Jacobson [Universal multistage networks via linear permutations, in: Proceedings of the 1991 ACM/IEEE Conference on Supercomputing, ACM Press, New York, 1991, pp. 380–389]. Under the further assumption that T is invertible we show that each component of is a conjunction of a cycle and a De Bruijn digraph, namely a generalized wrapped butterfly. Finally, we discuss the affine TCP digraph representations for a class of digraphs introduced by D. Coudert, A. Ferreira and S. Perennes [Isomorphisms of the De Bruijn digraph and free-space optical networks, Networks 40 (2002) 155–164].     

The Tutte–Potts connection in the presence of an external magnetic field

The classical relationship between the Tutte polynomial of graph theory and the Potts model of statistical mechanics has resulted in valuable interactions between the disciplines. Unfortunately, it does not include the external magnetic fields that appear in most Potts model applications. Here we define the V-polynomial, which lifts the classical relationship between the Tutte polynomial and the zero field Potts model to encompass external magnetic fields. The V-polynomial generalizes Noble and Welshʼs W-polynomial, which extends the Tutte polynomial by incorporating vertex weights and adapting contraction to accommodate them. We prove that the variable field Potts model partition function (with its many specializations) is an evaluation of the V-polynomial, and hence a polynomial with deletion–contraction reduction and Fortuin–Kasteleyn type representation. This unifies an important segment of Potts model theory and brings previously successful combinatorial machinery, including complexity results, to bear on a wider range of statistical mechanics models.     

Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians

The Pfaffian method enumerating perfect matchings of plane graphs was discovered by Kasteleyn. We use this method to enumerate perfect matchings in a type of graphs with reflective symmetry which is different from the symmetric graphs considered in [J. Combin. Theory Ser. A 77 (1997) 67, MATCH—Commun. Math. Comput. Chem. 48 (2003) 117]. Here are some of our results: (1) If G is a reflective symmetric plane graph without vertices on the symmetry axis, then the number of perfect matchings of G can be expressed by a determinant of order |G|/2, where |G| denotes the number of vertices of G. (2) If G contains no subgraph which is, after the contraction of at most one cycle of odd length, an even subdivision of K_2,3, then the number of perfect matchings of G×K₂ can be expressed by a determinant of order |G|. (3) Let G be a bipartite graph without cycles of length 4s, s{1,2,…}. Then the number of perfect matchings of G×K₂ equals ∏(1+θ²)^m_θ, where the product ranges over all non-negative eigenvalues θ of G and m_θ is the multiplicity of eigenvalue θ. Particularly, if T is a tree then the number of perfect matchings of T×K₂ equals ∏(1+θ²)^m_θ, where the product ranges over all non-negative eigenvalues θ of T and m_θ is the multiplicity of eigenvalue θ.     

The structure of Gibbs states and phase coexistence for non-symmetric continuum Widom Rowlinson models

Summary We prove the existence of phase transitions in non-symmetric r-component continuum Widom-Rowlinson models. Our results are based on an extension of the Pirogov-Sinai theory of phase transitions in general lattice spin systems to continuum systems. This generalizes Ruelle's extension of the Peierls argument for lattices to symmetric continuum Widom-Rowlinson models. The Pirogov-Sinai picture of the low temperature phase diagram for spin systems goes over into a phase-diagram of the Widom-Rowlinson model at large fugacities z=(z₀,..., z _r–1). There is in z-space a point where the system has r-pure phases, lines with r–1 phases, two dimensional surfaces with r–2 phases, etc.Supported in part by the National Science Foundation Grant DMR 81-14726-01     

Ramified partition algebras

For each natural number n, poset T, and |T|–tuple of scalars Q, we introduce the ramified partition algebra P _n ^(T) (Q), which is a physically motivated and natural generalization of the partition algebra [24, 25] (the partition algebra coincides with case |T|=1). For fixed n and T these algebras, like the partition algebra, have a basis independent of Q. We investigate their representation theory in case ${{T=\underline{{2}}:=({1,2},\leq)}}$. We show that ${{P_n^{(\underline{{2}})$ (Q) is quasi–hereditary over field k when Q ₁ Q ₂ is invertible in k and k is such that certain finite group algebras over k are semisimple (e.g. when k is algebraically closed, characteristic zero). Under these conditions we determine an index set for simple modules of ${{P_n^{(\underline{{2}})$ (Q), and construct standard modules with this index set. We show that there are unboundedly many choices of Q such that ${{P_n^{(\underline{{2}})$ (Q) is not semisimple for sufficiently large n, but that it is generically semisimple for all n. We construct tensor space representations of certain non–semisimple specializations of ${{P_n^{(\underline{{2}})$ (Q), and show how to use these to build clock model transfer matrices [24] in arbitrary physical dimensions. Sadly Ahmed died before this work was completed. His memory lives on.     

On Potts Model Clustering,Kernel K-Means and Density Estimation

Many clustering methods, such as K -means, kernel K -means, and MNcut clustering, follow the same recipe: (i) choose a measure of similarity between observations; (ii) define a figure of merit assigning a large value to partitions of the data that put similar observations in the same cluster; and (iii) optimize this figure of merit over partitions. Potts model clustering represents an interesting variation on this recipe. Blatt, Wiseman, and Domany defined a new figure of merit for partitions that is formally similar to the Hamiltonian of the Potts model for ferromagnetism, extensively studied in statistical physics. For each temperature T, the Hamiltonian defines a distribution assigning a probability to each possible configuration of the physical system or, in the language of clustering, to each partition. Instead of searching for a single partition optimizing the Hamiltonian, they sampled a large number of partitions from this distribution for a range of temperatures. They proposed a heuristic for choosing an appropriate temperature and from the sample of partitions associated with this chosen temperature, they then derived what we call a consensus clustering: two observations are put in the same consensus cluster if they belong to the same cluster in the majority of the random partitions. In a sense, the consensus clustering is an “average” of plausible configurations, and we would expect it to be more stable (over different samples)than the configuration optimizing the Hamiltonian.

The goal of this article is to contribute to the understanding of Potts model clustering and to propose extensions and improvements: (1) We show that the Hamiltonian used in Potts model clustering is closely related to the kernel K -means and MNCutcriteria. (2) We propose a modification of the Hamiltonian penalizing unequal clustersizes and show that it can be interpreted as a weighted version of the kernel K -meanscriterion. (3) We introduce a new version of the Wolff algorithm to simulate configurations from the distribution defined by the penalized Hamiltonian, leading to penalized Potts model clustering. (4) We note a link between kernel based clustering methods and nonparametric density estimation and exploit it to automatically determine locally adaptive kernel bandwidths. (5) We propose a new simple rule for selecting a good temperature T.

As an illustration we apply Potts model clustering to gene expression data and compare our results to those obtained by model based clustering and a nonparametric dendrogram sharpening method.     

Strong consistency properties of nonparametric estimators for randomly censored data,I: The product-limit estimator

In reliability and survival-time studies one frequently encounters the followingrandom censorship model:X ₁,Y ₁,X ₂,Y ₂, is an independent sequence of nonnegative rv's, theX _n' s having common distributionF and theY _n' s having common distributionG, Z _n =min{X _n ,Y _n },T _n =I[X _n <-Y _n ]; ifX _n represents the (potential) time to death of then-th individual in the sample andY _n is his (potential) censoring time thenZ _n represents the actual observation time andT _n represents the type of observation (T _n =O is a censoring,T _n =1 is a death). One way to estimateF from the observationsZ ₁.T ₁,Z ₂,T ₂, (and without recourse to theX _n' s) is by means of theproduct limit estimator (Kaplan andMeier [6]). It is shown that a.s., uniformly on [0,T] ifH(T ^–)<1 wherel–H=(l–F) (l–G), uniformly onR if whereT _F =sup {x:F(x)<1}; rates of convergence are also established. These results are used in Part II of this study to establish strong consistency of some density and failure rate estimators based on .The third author's research was partly supported by National Research Council of Canada     

The diffusive phase of a model of self-interacting walks

Summary We consider simple random walk onZ ^d perturbed by a factor exp[T ^–P J _T], whereT is the length of the walk and . Forp=1 and dimensionsd2, we prove that this walk behaves diffusively for all – < <₀, with ₀ > 0. Ford>2 the diffusion constant is equal to 1, but ford=2 it is renormalized. Ford=1 andp=3/2, we prove diffusion for all real (positive or negative). Ford>2 the scaling limit is Brownian motion, but ford2 it is the Edwards model (with the wrong sign of the coupling when >0) which governs the limiting behaviour; the latter arises since for ,T ^–p J _T is the discrete self-intersection local time. This establishes existence of a diffusive phase for this model. Existence of a collapsed phase for a very closely related model has been proven in work of Bolthausen and Schmock.     

Resonant States in High-Temperature Superconductors with Impurities

A microscopic theory of resonant states for the Zn-doped CuO₂ plane in the superconducting phase is formulated in the effective t–J model. In the model derived from the original p–d model, Zn impurities are considered as vacancies for the d states at Cu sites. In the superconducting phase, in addition to the local static perturbation induced by the vacancy, a dynamical perturbation appears that results in a frequency-dependent perturbation matrix. Using the T-matrix formalism for the Green's functions in terms of the Hubbard operators, we calculate the local density of electronic states with d, p, and s symmetries.     

Compact causal data interpolation

Consider a Hilbert space equipped with a time-structure, i.e., a resolution E of the identity on defined on subsets of some linearly ordered set Λ. For which x and y in is it possible to find a causal (time respecting) compact operator T, so that Tx = y? When T is required to be a Hilbert-Schmidt operator and (Λ, E) is sufficiently regular, this question is answered in terms of the “time-densities” of x and y. The condition is that the integral ∝_gLμ_x({s t})⁻¹ dμ_y(t) should be finite, where μ_x and μ_y are the measures on Λ given by μ_x(Ω) = ¦|E(Ω)x¦|² and μ_y(Ω) = ¦|E(Ω)y¦|². Further a solution is given for the related problem of minimizing the sum of ¦|Tx − y¦|² and the squared Hilbert-Schmidt norm ¦|R¦|₂² of T.     

Commutators for Approximation Spaces and Marcinkiewicz-Type Multipliers

It is proved that, under some conditions, weaker than those of the Marcinkiewicz multiplier theorem, the multiplier operator T_μ(∑_k c_ke^ikt)=∑_k μ_kc_ke^ikt satisfies on the Besov space B^σ, q_p the commutator theorem[T, T_μ]_{B^σ, qp, B^σ, qp}c T, where T=max(T_{B^σ0, q0p, B^σ0, q0p}, T_{B^σ1, q1p, B^σ1, q1p} and σ₀>σ>σ₁>0.     

Note

In this note, a structural result for maximal K_r-free graphs is proven, which provides a simple proof of the Andrásfai–Erd$ \delta > {\left( {1 - \frac{1} {{r - \frac{4} {3}}}} \right)}n $ \delta > {\left( {1 - \frac{1} {{r - \frac{4} {3}}}} \right)}n is (r–1)-colourable.     

Bivariate Tensor-Product B-Splines in a Partly Linear Model

In some applications, the mean or median response is linearly related to some variables but the relation to additional variables are not easily parameterized. Partly linear models arise naturally in such circumstances. Suppose that a random sample {(T_i, X_i, Y_i),i=1, 2, …, n} is modeled byY_i=X^T_iβ₀+g₀(T_i)+error_i, whereY_iis a real-valued response,X_iR^pandT_iranges over a unit square, andg₀is an unknown function with a certain degree of smoothness. We make use of bivariate tensor-product B-splines as an approximation of the functiong₀and consider M-type regression splines by minimization of ∑ⁿ_i=1 ρ(Y_i−X^T_iβ−g_n(T_i)) for some convex functionρ. Mean, median and quantile regressions are included in this class. We show under appropriate conditions that the parameter estimate ofβachieves its information bound asymptotically and the function estimate ofg₀attains the optimal rate of convergence in mean squared error. Our asymptotic results generalize directly to higher dimensions (for the variableT) provided that the functiong₀is sufficiently smooth. Such smoothness conditions have often been assumed in the literature, but they impose practical limitations for the application of multivariate tensor product splines in function estimation. We also discuss the implementation of B-spline approximations based on commonly used knot selection criteria together with a simulation study of both mean and median regressions of partly linear models.     

Idempotent lattices, Renner monoids and cross section lattices of the special orthogonal algebraic monoids

Let MSO_n (n is even) be the special orthogonal algebraic monoid, T a maximal torus of the unit group, and the Zariski closure of T in the whole matrix monoid M_n. In this paper we explicitly determine the idempotent lattice , the Renner monoid , and the cross section lattice Λ of MSO_n in terms of the Weyl group and the concept of admissible sets (see Definition 3.1). It turns out that there is a one-to-one relationship between and the admissible subsets, and that is a submonoid of  , the Renner monoid M_n. Also Λ is a sublattice of Λ_n, the cross section lattice of M_n.     

The Rivest–Vuillemin Conjecture on Monotone Boolean Functions Is True for Ten Variables

A Boolean function f(x₁, …, x_n) is elusive if every decision tree evaluating f must examine all n variables in the worst case. Rivest and Vuillemin conjectured that every nontrivial monotone weakly symmetric Boolean function is elusive. In this note, we show that this conjecture is true for n=10.     

Metric structures in : dimension, snowflakes, and average distortion

We study the metric properties of finite subsets of L₁. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weighted graphs, including the Sparsest Cut Problem, one of the most compelling open problems in the field of approximation algorithms. Additionally, many open questions in geometric non-linear functional analysis involve the properties of finite subsets of L₁.We present some new observations concerning the relation of L₁ to dimension, topology, and Euclidean distortion. We show that every n-point subset of L₁ embeds into L₂ with average distortion , yielding the first evidence that the conjectured worst-case bound of is valid. We also address the issue of dimension reduction in L_p for p(1,2). We resolve a question left open by M. Charikar and A. Sahai [Dimension reduction in the ℓ₁ norm, in: Proceedings of the 43rd Annual IEEE Conference on Foundations of Computer Science, ACM, 2002, pp. 251–260] concerning the impossibility of dimension reduction with a linear map in the above cases, and we show that a natural variant of the recent example of Brinkman and Charikar [On the impossibility of dimension reduction in ℓ₁, in: Proceedings of the 44th Annual IEEE Conference on Foundations of Computer Science, ACM, 2003, pp. 514–523], cannot be used to prove a lower bound for the non-linear case. This is accomplished by exhibiting constant-distortion embeddings of snowflaked planar metrics into Euclidean space.     

A method of estimation of the frequency selectivity of a cochlear model from the amplitude-versus-coordinate characteristic

The factor which is analogous to the tuning qualityQ _N but is related to the frequency scale of higher-order harmonic functions of the characteristic vibrations of cochlear cross-sections is introduced. It is proved that can approximateQ _N if the frequency selectivity is large (Q _n 1) and the energy of the liquid in the vicinity of the peak of the amplitude function is small compared with the kinetic energy of the elastic partition.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova, Vol. 179, pp. 139–146, 1989.     

On the solution of singular linear systems of algebraic equations by semiiterative methods

Summary For a square matrixT ^n,n , where (I–T) is possibly singular, we investigate the solution of the linear fixed point problemx=T x+c by applying semiiterative methods (SIM's) to the basic iterationx ₀ ⁿ ,x _k T c _k–1+c(k1). Such problems arise if one splits the coefficient matrix of a linear systemA x=b of algebraic equations according toA=M–N (M nonsingular) which leads tox=M ^–1 N x+M ^–1 bT x+c. Even ifx=T x+c is consistent there are cases where the basic iteration fails to converge, namely ifT possesses eigenvalues 1 with ||1, or if =1 is an eigenvalue ofT with nonlinear elementary divisors. In these cases — and also ifx=T x+c is incompatible — we derive necessary and sufficient conditions implying that a SIM tends to a vector which can be described in terms of the Drazin inverse of (I–T). We further give conditions under which is a solution or a least squares solution of (I–T)x=c.Research supported in part by the Alexander von Humboldt-Stiftung