Counterexamples to the List Square Coloring Conjecture

The square G² of a graph G is the graph defined on such that two vertices u and v are adjacent in G² if the distance between u and v in G is at most 2. Let and be the chromatic number and the list chromatic number of a graph H, respectively. A graph H is called chromatic‐choosable if . It is an interesting problem to find graphs that are chromatic‐choosable. Kostochka and Woodall (Choosability conjectures and multicircuits, Discrete Math., 240 (2001), 123–143) conjectured that for every graph G, which is called List Square Coloring Conjecture. In this article, we give infinitely many counter examples to the conjecture. Moreover, we show that the value can be arbitrarily large.     

Examples and Counterexamples for the Perles Conjecture

   Abstract. The combinatorial structure of a d -dimensional simple convex polytope—as given, for example, by the set of the (d-1) -regular subgraphs of the facets—can be reconstructed from its abstract graph. However, no polynomial/ efficient algorithm is known for this task, although a polynomially checkable certificate for the correct reconstruction exists. A much stronger certificate would be given by the following characterization of the facet subgraphs, conjectured by Micha Perles: ``The facet subgraphs of a simple d-polytope are exactly all the (d-1) -regular, connected, induced, non-separating subgraphs .' We present non-trivial classes of examples for the validity of the Perles conjecture: in particular, it holds for the duals of cyclic polytopes, and for the duals of stacked polytopes. On the other hand, we observe that for any 4-dimensional counterexample, the boundary of the (simplicial) dual polytope

Counterexamples to the Connectivity Conjecture of the Mixed Cells

In [4] a conjecture concerning the connectivity of mixed cells of subdivisions for Minkowski sums of polytopes was formulated. This conjecture was, in fact, originally proposed by Pedersen [3]. It turns out that a positive confirmation of this conjecture can substantially speed up the algorithm for the ``dynamical lifting' developed in [4]. In the mean time, when the polyhedral method is used for solving polynomial systems by homotopy continuation methods [2], the positiveness of this conjecture also plays an important role in the efficiency of the algorithm. Very unfortunately, we found that this conjecture is inaccurate in general. In Section 1 a counterexample is presented for a general subdivision. In Section 2 another counterexample shows that even restricted to ``regular' subdivisions induced by liftings, this conjecture still fails to be true. Received September 18, 1996, and in revised form February 17, 1997.     

Counterexamples to the Strong d -Step Conjecture for d≥5

A Dantzig figure is a triple (P,x,y) in which P is a simple d -polytope with precisely 2d facets, x and y are vertices of P , and each facet is incident to x or y but not both. The famous d -step conjecture of linear programming is equivalent to the claim that always # ^d P(x,y) ≥ 1 , where # ^d P(x,y) denotes the number of paths that connect x to y by using precisely d edges of P . The recently formulated strong d -step conjecture makes a still stronger claim—namely, that always # ^d P(x,y) ≥ 2 ^d-1 . It is shown here that the strong d -step conjecture holds for d ≤ 4 , but fails for d ≥ 5 . Received December 27, 1995, and in revised form April 8, 1996.     

Gabor Frames for Model Sets

Journal of Fourier Analysis and Applications - We generalize three main concepts of Gabor analysis for lattices to the setting of model sets: fundamental identity of Gabor analysis, Janssen’s...     

Irregular Wavelet Frames and Gabor Frames

Given g∈L²(R ⁿ ), we consider irregular wavelet for the form\(\left\{ {\lambda ^{\frac{n}{2}} g\left( {\lambda _j x - kb} \right)} \right\}_{j\varepsilon zj\varepsilon z^n } ,where\;\lambda _j \) > 0 and b > 0. Sufficient conditions for the wavelet system to constitute a frame for L²(R ⁿ ) are given. For a class of functions g∈L²²(R ⁿ ) we prove that certain growth conditions on {λ _j } will frames, and that some other types of sequences exclude the frame property. We also give a sufficient condition for a Gabor system\(\left\{ {e^{zrib\left( {j,x} \right)} g\left( {x - \lambda _k } \right)} \right\}_{j\varepsilon z^n ,k\varepsilon z} \)to be a frame.     

Irregular Wavelet Frames and Gabor Frames

Given g { l^\fracn2 g( l_j x - kb ) }_jezjezⁿ ,where  l_j \left\{ {\lambda ^{\frac{n}{2}} g\left( {\lambda _j x - kb} \right)} \right\}_{j\varepsilon zj\varepsilon z^n } ,where\;\lambda _j > 0 and b > 0. Sufficient conditions for the wavelet system to constitute a frame for L ²(R ⁿ ) are given. For a class of functions g{ e^{zrib( j,x )} g( x - l_k ) }_{jezⁿ ,kez}\left\{ {e^{zrib\left( {j,x} \right)} g\left( {x - \lambda _k } \right)} \right\}_{j\varepsilon z^n ,k\varepsilon z} to be a frame.     

Counterexamples to Tischler's Strong Form of Smale's Mean Value Conjecture

Smale's mean value conjecture asserts that for every polynomial P of degree d satisfying P(0)=0,where K = (d–1)/d and the minimum is taken over all criticalpoints of P. A stronger conjecture due to Tischler assertsthat with . Tischler's conjecture is known to be true: (i) for local perturbations of the extremumP₀(z)=z^d – dz, and (ii) for all polynomials of degreed 4. In this paper, Tischler's conjecture is verified for alllocal perturbations of the extremum P₁(z)=(z – 1)^d –(–1)^d, but counterexamples to the conjecture are givenin each degree d 5. In addition, estimates for certain weightedL¹- and L²-averages of the quantities are established, which lead to the best currentlyknown value for K₁ in the case d=5. 2000 Mathematics SubjectClassification 30C15.     

Density of Gabor Frames

A Gabor system is a set of time-frequency shifts S(g, Λ) ={e^{2 π ibx}g(x − a)}_{(a, b) Λ} of a function g L²(R^d). We prove that if a finite union of Gabor systems _{k = 1}^rS(g_k, Λ_k) forms a frame for L²(R^d) then the lower and upper Beurling densities of Λ = _{k = 1}^r Λ_k satisfy D⁻(Λ) ≥ 1 and D ⁺ (Λ) < ∞. This extends recent work of Ramanathan and Steger. Additionally, we prove the conjecture that no collection _{k = 1}^r{g_k(x − a)}_{a Γk} of pure translates can form a frame for L²(R^d).     

Directional Frames for Image Recovery: Multi-scale Discrete Gabor Frames

Sparsity-driven image recovery methods assume that images of interest can be sparsely approximated under some suitable system. As discontinuities of 2D images often show geometrical regularities along image edges with different orientations, an effective sparsifying system should have high orientation selectivity. There have been enduring efforts on constructing discrete frames and tight frames for improving the orientation selectivity of tensor product real-valued wavelet bases/frames. In this paper, we studied the general theory of discrete Gabor frames for finite signals, and constructed a class of discrete 2D Gabor frames with optimal orientation selectivity for sparse image approximation. Besides high orientation selectivity, the proposed multi-scale discrete 2D Gabor frames also allow us to simultaneously exploit sparsity prior of cartoon image regions in spatial domain and the sparsity prior of textural image regions in local frequency domain. Using a composite sparse image model, we showed the advantages of the proposed discrete Gabor frames over the existing wavelet frames in several image recovery experiments.     

Counterexamples of the Conjecture on Roots of Ehrhart Polynomials

On roots of Ehrhart polynomials, Beck et al. conjecture that all roots α of the Ehrhart polynomial of an integral convex polytope of dimension d satisfy −d≤ℜ(α)≤d−1. In this paper, we provide counterexamples for this conjecture.     

Letter to the Editor: A New Criterion for Gabor Frames

We give a new criterion for the invertibility of the Gabor frame operator in the irrational case. It is sufficient to verify the invertibility of a single (infinite) matrix.     

On a necessary condition for B-spline Gabor frames

In a previous note Gröchenig et al. prove that if g is a continuous function with compact support such that the translates of g form a partition of unity, then g cannot generate a Gabor frame for integer values of the frequency shift parameter b greater than 1 (Gröchenig et al. in IEEE Trans Inform Theory 49:3318–3320, 2003). We give a simpler proof of this result which applies also to windows g which are neither continuous nor with compact support. Our proof is based on a necessary condition for Gabor frames due to Heil and Walnut.     

Hyperbolic Secants Yield Gabor Frames

We show that (g₂,a,b) is a Gabor frame when a>0, b>0, ab<1, and $\text{g}{}_2\text{(t)=(}\text{1}\text{2}\text{πγ)}{}^{\mathrm{1/2}}\text{(cosh}\text{πγt)}{}^{\mathrm{-1}}$ is a hyperbolic secant with scaling parameter γ>0. This is accomplished by expressing the Zak transform of g₂ in terms of the Zak transform of the Gaussian g₁(t)=(2γ)^1/4 exp (−πγt²), together with an appropriate use of the Ron–Shen criterion for being a Gabor frame. As a side result it follows that the windows, generating tight Gabor frames, that are canonically associated to g₂ and g₁ are the same at critical density a=b=1. Also, we display the “singular” dual function corresponding to the hyperbolic secant at critical density.     

The Mystery of Gabor Frames

This is a survey about the theory of Gabor frames. We review the structural results about Gabor frames over a lattice and then discuss the few known results about the fine structure of Gabor frames. We add a new result about the relation between properties of the window and properties of the frame set and conclude with a vision of how a more complete theory of the fine structure might look like.     

Gabor Frames over Irregular Lattices

We give necessary and sufficient conditions for gW(L ,¹) to generate a Gabor frame over certain irregular lattices.     

Restrictions On Smallest Counterexamples To The 5-Flow Conjecture

Using counting arguments, we show that every smallest counterexample to Tutte’s 5-flow Conjecture (that every bridgeless graph has a nowhere-zero 5-flow) has girth at least 9. * This work was supported by Science and Technology Assistance Agency under the contract No. APVT-51-027604 and partially by VEGA grant 2/4004/04. The author was also affiliated at the School of Mathematics, Georgia Institute of Technology, the Department of Mathematics, Vanderbilt University.     

History and Evolution of the Density Theorem for Gabor Frames

The Density Theorem for Gabor Frames is one of the fundamental results of time-frequency analysis. This expository survey attempts to reconstruct the long and very involved history of this theorem and to present its context and evolution, from the one-dimensional rectangular lattice setting, to arbitrary lattices in higher dimensions, to irregular Gabor frames, and most recently beyond the setting of Gabor frames to abstract localized frames. Related fundamental principles in Gabor analysis are also surveyed, including the Wexler-Raz biorthogonality relations, the Duality Principle, the Balian-Low Theorem, the Walnut and Janssen representations, and the Homogeneous Approximation Property. An extended bibliography is included.     

Approximation of the Inverse Frame Operator and Applications to Gabor Frames

A frame allows every element in a Hilbert space to be written as a linear combination of the frame elements, with coefficients called frame coefficients. Calculation of the frame coefficients requires inversion of an operator S on . We show how the inverse of S can be approximated as close as we like using finite-dimensional linear algebra. In contrast with previous methods, our approximation can be used for any frame. Various consequences for approximation of the frame coefficients or approximation of the solution to a moment problem are discussed. We also apply the results to Gabor frames and frames consisting of translates of a single function.     

Characterization and Computation of Canonical Tight Windows for Gabor Frames

Let (\gnm)_{n,m ? \Zst}(\gnm)_{n,m\in\Zst} be a Gabor frame for \LtR\LtR for given window gg. We show that the window \ho = \SQI g\ho=\SQI g that generates the canonically associated tight Gabor frame minimizes ||g-h||\|g-h\| among all windows hh generating a normalized tight Gabor frame. We present and prove versions of this result in the time domain, the frequency domain, the time-frequency domain, and the Zak transform domain, where in each domain the canonical \ho\ho is expressed using functional calculus for Gabor frame operators. Furthermore, we derive a Wiener--Levy type theorem for rationally oversampled Gabor frames. Finally, a Newton-type method for a fast numerical calculation of \ho\ho is presented. We analyze the convergence behavior of this method and demonstrate the efficiency of the proposed algorithm by some numerical examples.