A note on Hadwiger’s conjecture for W5-free graphs with independence number two

The Hadwiger number of a graph $G$, denoted $h\left(G\right)$, is the largest integer $t$ such that $G$ contains $K_t$ as a minor. A famous conjecture due to Hadwiger in 1943 states that for every graph $G$, $h\left(G\right)\ge \chi \left(G\right)$, where $\chi \left(G\right)$ denotes the chromatic number of $G$. Let $\alpha \left(G\right)$ denote the independence number of $G$. A graph is $H$-free if it does not contain the graph $H$ as an induced subgraph. In 2003, Plummer, Stiebitz and Toft proved that $h\left(G\right)\ge \chi \left(G\right)$ for all $H$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $H$ is any graph on four vertices with $\alpha \left(H\right)\le 2$, $H=C_5$, or $H$ is a particular graph on seven vertices. In 2010, Kriesell subsequently generalized the statement to include all forbidden subgraphs $H$ on five vertices with $\alpha \left(H\right)\le 2$. In this note, we prove that $h\left(G\right)\ge \chi \left(G\right)$ for all $W_5$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $W_5$ denotes the wheel on six vertices.     

Nonlinear equivalence of Banach spaces based on Birkhoff-James orthogonality

A Banach space X is said to be isomorphic to another Y with respect to the structure of Birkhoff-James orthogonality, denoted by $X{～}_{BJ}Y$, if there exists a (possibly nonlinear) bijection between X and Y that preserves Birkhoff-James orthogonality in both directions. It is shown that $X?Y$ if either X or Y is finite dimensional and $X{～}_{BJ}Y$, and that ${?}_p{?}_{BJ}{?}_q$ if $1<p<q<\infty$. Moreover, if H is a Hilbert space with $\dim ?H\ge 3$ and $H{～}_{BJ}X$, then $H=X$. In the two-dimensional case, it turns out that ${?}_{p,q}^2{～}_{BJ}{?}_2^2$, which indicates that nonlinear Birkhoff-James orthogonality preservers between Banach spaces are not necessarily scalar multiples of isometric isomorphisms.     

Semi-classical analysis of piecewise quasi-polynomial functions and applications to geometric quantization

Motivated by applications to multiplicity formulas in index theory, we study a family of distributions $\Theta (m;k)$ associated to a piecewise quasi-polynomial function $m$. The family is indexed by an integer $k\in {\mathbb{Z}}_{>0}$, and admits an asymptotic expansion as $k\to \infty$, which generalizes the expansion obtained in the Euler–Maclaurin formula. When $m$ is the multiplicity function arising from the quantization of a symplectic manifold, the leading term of the asymptotic expansion is the Duistermaat–Heckman measure. Our main result is that $m$ is uniquely determined by a collection of such asymptotic expansions. We also show that the construction is compatible with pushforwards. As an application, we describe a simpler proof that formal quantization is functorial with respect to restrictions to a subgroup.     

Separable discrete functions: Recognition and sufficient conditions

A discrete function of $n$ variables is a mapping $g:X_1\times \dots \times X_n\to A$, where $X_1,\dots ,X_n$, and $A$ are arbitrary finite sets. Function $g$ is called separable if there exist $n$ functions $g_i:X_i\to A$ for $i=1,\dots ,n$, such that for every input $x_1,\dots ,x_n$ the function $g(x_1,\dots ,x_n)$ takes one of the values $g_1\left(x_1\right),\dots ,g_n\left(x_n\right)$. Given a discrete function $g$, it is an interesting problem to ask whether $g$ is separable or not. Although this seems to be a very basic problem concerning discrete functions, the complexity of recognition of separable discrete functions of $n$ variables is known only for $n=2$. In this paper we will show that a slightly more general recognition problem, when $g$ is not fully but only partially defined, is NP-complete for $n\ge 3$. We will then use this result to show that the recognition of fully defined separable discrete functions is NP-complete for $n\ge 4$.The general recognition problem contains the above mentioned special case for $n=2$. This case is well-studied in the context of game theory, where (separable) discrete functions of $n$ variables are referred to as (assignable) $n$-person game forms. There is a known sufficient condition for assignability (separability) of two-person game forms (discrete functions of two variables) called (weak) total tightness of a game form. This property can be tested in polynomial time, and can be easily generalized both to higher dimension and to partially defined functions. We will prove in this paper that weak total tightness implies separability for (partially defined) discrete functions of $n$ variables for any $n$, thus generalizing the above result known for $n=2$. Our proof is constructive. Using a graph-based discrete algorithm we show how for a given weakly totally tight (partially defined) discrete function $g$ of $n$ variables one can construct separating functions $g_1,\dots ,g_n$ in polynomial time with respect to the size of the input function.     

Reeb posets and tree approximations

A well known result in the analysis of finite metric spaces due to Gromov says that given any metric space $(X,d_X)$ there exists a tree metric $t_X$ on $X$ such that ${|d_X-t_X|}_{\infty }$ is bounded above by twice $\mathrm{hyp}\left(X\right)\cdot log\left(2\left|X\right|\right)$. Here $\mathrm{hyp}\left(X\right)$ is the hyperbolicity of $X$, a quantity that measures the treeness of 4-tuples of points in $X$. This bound is known to be asymptotically tight.We improve this bound by restricting ourselves to metric spaces arising from filtered posets. By doing so we are able to replace the cardinality appearing in Gromov’s bound by a certain poset theoretic invariant which can be much smaller thus significantly improving the approximation bound.The setting of metric spaces arising from posets is rich: For example, every finite metric graph can be induced from a filtered poset. Since every finite metric space can be isometrically embedded into a finite metric graph, our ideas are applicable to finite metric spaces as well.At the core of our results lies the adaptation of the Reeb graph and Reeb tree constructions and the concept of hyperbolicity to the setting of posets, which we use to formulate and prove a tree approximation result for any filtered poset.     

Asymptotic behavior and blow-up of solutions for infinitely degenerate semilinear parabolic equations with logarithmic nonlinearity

In this paper, we study the initial-boundary value problem for infinitely degenerate semilinear parabolic equations with logarithmic nonlinearity $u_t?{△}_{X}u=u\log ?|u|$, where $X=(X_1,X_2,?,X_m)$ is an infinitely degenerate system of vector fields, and ${△}_X:={\sum }_{j=1}^m{X}_j^2$ is an infinitely degenerate elliptic operator. Using potential well method, we first prove the invariance of some sets and vacuum isolating of solutions. Then, by the Galerkin method and the logarithmic Sobolev inequality, we obtain the global existence and blow-up at +∞ of solutions with low initial energy or critical initial energy, and we also discuss the asymptotic behavior of the solutions.     

Characterizations of graphs G having all [1,k]-factors in kG

Let $k\ge 1$ be an integer and $G$ be a graph. Let $kG$ denote the graph obtained from $G$ by replacing each edge of $G$ with $k$ parallel edges. We say that $G$ has all $[1,k]$-factors or all fractional $[1,k]$-factors if $G$ has an $h$-factor or a fractional $h$-factor for every function $h:V\left(G\right)\to \{1,2,\dots ,k\}$ with $h\left(V\left(G\right)\right)$ even. In this note, we come up with simple characterizations of a graph $G$ such that $kG$ has all $[1,k]$-factors or all fractional $[1,k]$-factors. These characterizations are extensions of Tutte’s 1-Factor Theorem and Tutte’s Fractional 1-Factor Theorem.     

Monochromatic subgraphs in randomly colored graphons

Let $T(H,G_n)$ be the number of monochromatic copies of a fixed connected graph $H$ in a uniformly random coloring of the vertices of the graph $G_n$. In this paper we give a complete characterization of the limiting distribution of $T(H,G_n)$, when ${\left\{G_n\right\}}_{n\ge 1}$ is a converging sequence of dense graphs. When the number of colors grows to infinity, depending on whether the expected value remains bounded, $T(H,G_n)$ either converges to a finite linear combination of independent Poisson variables or a normal distribution. On the other hand, when the number of colors is fixed, $T(H,G_n)$ converges to a (possibly infinite) linear combination of independent centered chi-squared random variables. This generalizes the classical birthday problem, which involves understanding the asymptotics of $T(K_s,K_n)$, the number of monochromatic $s$-cliques in a complete graph $K_n$ ($s$-matching birthdays among a group of $n$ friends), to general monochromatic subgraphs in a network.     

On the critical points of the flight return time function of perturbed closed orbits

We deal here with planar analytic systems $\dot{x}=X(x,\epsilon )$ which are small perturbations of a period annulus. For each transversal section Σ to the unperturbed orbits we denote by $T^{\mathrm{\Sigma }}(q,\epsilon )$ the time needed by a perturbed orbit that starts from $q\in \mathrm{\Sigma }$ to return to Σ. We call this the flight return time function. We say that the closed orbit Γ of $\dot{x}=X(x,0)$ is a continuable critical orbit in a family of the form $\dot{x}=X(x,\epsilon )$ if, for any $q\in \mathrm{\Gamma }$ and any Σ that passes through q, there exists $q^{\epsilon }\in \mathrm{\Sigma }$ a critical point of $T^{\mathrm{\Sigma }}(?,\epsilon )$ such that $q^{\epsilon }\to q$ as $\epsilon \to 0$. In this work we study this new problem of continuability.In particular we prove that a simple critical periodic orbit of $\dot{x}=X(x,0)$ is a continuable critical orbit in any family of the form $\dot{x}=X(x,\epsilon )$. We also give sufficient conditions for the existence of a continuable critical orbit of an isochronous center $\dot{x}=X(x,0)$.     

Equitable 2-partitions of the Hamming graphs with the second eigenvalue

The eigenvalues of the Hamming graph $H(n,q)$ are known to be ${\lambda }_i(n,q)=(q-1)n-qi$, $0\le i\le n$. The characterization of equitable 2-partitions of the Hamming graphs $H(n,q)$ with eigenvalue ${\lambda }_1(n,q)$ was obtained by Meyerowitz (2003). We study the equitable 2-partitions of $H(n,q)$ with eigenvalue ${\lambda }_2(n,q)$. We show that these partitions are reduced to equitable 2-partitions of $H(3,q)$ with eigenvalue ${\lambda }_2(3,q)$ with the exception of two constructions.