Math Overflow Recent Questions


Hopcroft-Karp Algorithm

Thu, 07/12/2018 - 01:46

I'm studying Hopcroft-Karp algorithm in bipartite graph.

I can understand the theorems about the algorithm, but I want to find a more specific example.

Can I find a bipartite graph that iterates an algorithm more than three times?

I tried to find it, but most of graphs ended in two iterations. (1 BFS + 1 DFS)

In arbitrary cyclic polygon $\sum_{i<j} A_iA_j^\alpha \ge \sum_{i<j} B_iB_j^\alpha $

Wed, 07/11/2018 - 23:39

I am looking for a proof of the inequality as follows:

Let $A_1A_2....A_n$ be the regular polygon incribed a circle $(O)$. Let $B_1B_2....B_n$ be a polygon incribed the circle $(O)$. I conjecture that:

$$\sum_{i<j} A_iA_j^\alpha \ge \sum_{i<j} B_iB_j^\alpha $$

Where $ 1 \leq \alpha \leq 2$.

  • The case $ \alpha = 1 $ was proved in our paper in here

  • The case $ \alpha = 2 $ was proved in here


  • $n=3$, let $ABC$ be a triangle with sidelength $a, b, c$ then we have the inequality as follows:

$$a^\alpha + b^\alpha+ c^\alpha \leq 3\times 3^{\frac{\alpha}{2}}R^\alpha$$ Where $ 1 \leq \alpha \leq 2$, $R$ is circumradius.

See also:

Floer cohomology from mapping spaces of $\infty$ categories

Wed, 07/11/2018 - 23:03

There's a meta-observation (of Urs Schreiber, who attributes it to Ken Brown and Lurie) that 'cohomology theories come from mapping spaces of infinity categories. This is described in detail at the nlab page on cohomology

I would like to understand if there's any non-contrived way that Floer-theoretic invariants fit into this picture.

I'm far from an expert. I'm aware of a number of works elucidating homotopy-theoretic aspects of Floer theory: for example the construction of Cohen-Jones-Segal, and the infinity category of Lagrangian cobordisms defined by Nadler-Tanaka. Do any of these constructions provide an answer to the question above?

Approximating a ray with an integer lattice point

Wed, 07/11/2018 - 22:56

Take $X$ uniform on the unit sphere in $\mathbb{R}^n.$ For $r>0$, take $S_r=\{x\in \mathbb{Z}^n: \sum_i x_i^2 \leq r\}.$

  • With $\|\cdot \|$ the 2-norm, what is the distribution of

\begin{align} \underset{x \in S_r}{\min} \ \|X-x/\|x\|\| \end{align}

  • How can this optimization be performed efficiently?

One idea for performing the optimization is by rounding onto the lattice along the ray $\alpha X$, varying $\alpha$ at each iteration to alter the fewest component's rounding possible. Then choosing the best value once $\alpha$ is small enough that $\alpha X$ rounds to zero. I believe this runs in no more than $O(n^2r).$

An inequality in counting formula

Wed, 07/11/2018 - 22:35

While counting I came across the following inequality:

$(x-1)^{n-1}(x+1) > \frac{1}{2}x^n$ when $x>n$.

In fact, I have both $x$ and $n$ integers and $\geq 3$.

For $n=3$ this is equivalent to proving: $x^2+x-1 < x^3/2$ which is true for $x > 3$.

I can easily verify this for $n=4,5$. However, I have not been able to prove this in general. Any help in this would be much appreciated.

The dual relationships between strictly singular operators and strictly cosingular operators

Wed, 07/11/2018 - 21:42

Recall that an operator $T:X\rightarrow Y$ between Banach spaces is called strictly singular if if it is not an isomorphism when restricted to any infinite-dimensional closed subspace of $X$. An operator $T:X\rightarrow Y$ is said to be strictly cosingular provided that for no infinite-dimensional Banach space $Z$ there exist surjective operators $R:X\rightarrow Z$ and $S:Y\rightarrow Z$ such that $R=ST$. It is elementary that an operator $T$ is strictly cosingular (strictly singular) whenever its adjoint $T^{*}$ is strictly singular (strictly cosingular, respectively). My question is the converse to this basic fact. More precisely, for an operator $T:X\rightarrow Y$,

Question 1. Under what conditions on $X$, the adjoint $T^{*}$ is strictly cosingular whenever $T$ is strictly singular?

Question 2. Under what conditions on $Y$, the adjoint $T^{*}$ is strictly singular whenever $T$ is strictly cosingular?

CW Product via Whitehead map

Wed, 07/11/2018 - 18:31

CW-complexes are defined via characteristic maps rather than from attaching maps, so via maps from $\mathbb D^n$ rather than from $\mathbb S^{n-1}$, because we have the propriety that $\mathbb D^n\times\mathbb D^m=\mathbb D^{m+n}$. I want to define products in a synthetic way, only manipulating objetcs up to homotopy so I need to use the spheres. So basically if $X$ and $Y$ are CW-complexes and $Z$ is the product, to attach one new cell to $Z_{p-1}$ means attaching a product of cells $\mathbb S^{n-1}\to X_{n-1}$ and $\mathbb S^{m-1}\to Y_{m-1}$, where $n+m=p$, and this should give a function $\mathbb S^{n+m-1}\to Z_{p-1}$. We actually already have such a map when the CW-complexes $X$ and $Y$ are the spheres $\mathbb S^{n}$ and $\mathbb S^{m}$, which is the Whitehead map. Indeed we have then $Z_{n+m-1}=\mathbb S^{n}\vee\mathbb S^{m}$ and this implies that the function is of type $\mathbb S^{n+m-1}\to \mathbb S^{n}\vee\mathbb S^{m}$. Now I want this bit to be generalizable to every product of finite CW-complex (it can have just a finite number of cells if nedded).

We want some function $\mathbb S^{n+m-1}\to Z_{p-1}$ and we would like to do the same thing as in the construction of the map $\mathbb S^{n+m-1}\to \mathbb S^{n}\vee\mathbb S^{m}$, so look a the pushout $\mathbb S^{n-1}\leftarrow \mathbb S^{n-1}\times\mathbb S^{m-1}\to \mathbb S^{m-1}$ but then the attaching maps of the cells are not trivial like they were for products of sphere. This looks very closely like the Whitehead product but I guess there is some non trivial things to consider at this point and I feel like I can't find the good way to tackle the problem.

I would like to know if some work about this had already be done, I'd be very glad that you have some synthetic reference about this problem.

Thank you very much

Insights from disproofs after counterexamples have been given

Wed, 07/11/2018 - 17:57

Some conjectures are disproved by a single counter-example and garner little or no further interest or study, such as (to my knowledge) Euler's conjecture in number theory that at least $n$ $n^{th}$ powers are required to sum to an $n^{th}$ power, for $n>2$ (disproved by counter-example by L. J. Lander and T. R. Parkin in 1966). But other conjectures retain interest, even after being disproved by counter-example, and lead to analytic disproofs and insights.


What are some conjectures, first known to be false through counter-example, but whose subsequent analytic disproofs shed novel insights into the problem? More generally, what are the properties of known false conjectures that nevertheless garner significant interest and efforts of mathematicians to produce analytic disproofs?

Expected time of distinguishability of a series of Poisson processes bounded by each other

Wed, 07/11/2018 - 14:45

Consider a system of $n$ "bounded" Poisson processes over the integers, $X_1, \ldots X_n$, all incrementing at rate $\lambda$. Initially all the processes begin at $0$. The process $X_i$ is inactive until $X_{i+1} - X_i > 1$, at which point it begins incrementing itself at rate $\lambda$. Whenever $X_{i+1} - X_i \leq 1$, the process $X_i$ stops, waiting for $X_{i+1}$ to increment itself, before becoming active again. ($X_n$ is always active.)

We can see that eventually every $X_i$ will have a unique value. My question is regarding the expected time $E[\mathcal{T}]$ of the first time this event occurs: what is the first time all processes have a unique value?

A simple bound seems to be $E[\mathcal{T}] = O(n^2)$. However, my simulations indicate that this takes linear time in $n$. I'd love to see an analysis that shows something along the lines of $E[\mathcal{T}] = O(n)$, or any other asymptotic analysis for this system.

Is there an efficient way to represent all non-simple cycles of a digraph up to the number of vertices?

Wed, 07/11/2018 - 11:21

Given two digraphs $G$ and $H$, I want a method for creating a bijection between all non-simple cycles of for all $n \le |V(G)|$. That means, given $C_G(n)$ and $C_H(n)$ being the sets of all non-simple cycles of length $n$ in $G$ and $H$ respectively, there is a bijection between these two sets. Here, non-simple cycles refers to a closed walk on the graph where we are allowing repeated vertices and edges.

First, it is known that tr$(A^n)$ where $A$ is the adjacency matrix of a graph gives the number of non-simple cycles of length $n$. So, in polynomial time, it is possible to determine whether such a bijection can exist between graphs $G$ and $H$. The question is how to find this bijection without simply enumerating all the possible cycles and pairing them off one by one which is at least an exponential algorithm.

My first thought was to use a cycle basis. However, when considering non-simple cycles, there isn't a unique vector representation in $\mathbb{Q}^{|E(G)|}$ since edges can repeat.

Are there any other representations of the cycles in a graph besides a cycle basis that could reduce the number of cycles to be considered to a polynomial amount?

Why should we study derivations of algebras?

Wed, 07/11/2018 - 08:05

Some authors have written that derivation of an algebra is an important tools for studying its structure. Could you give me a specific example of how a derivation gives insight into an algebra's structure? More generally: Why should we study derivations of algebras? What is the advantage of knowing that an algebra has a non-trivial derivation?

planar shapes of numbers respect to an optimal circle dartboard [on hold]

Wed, 07/11/2018 - 07:02

First this question came to my mind when I was contemplating on the numbers 1-20 arranged interestingly around a regular dartboard, then I proposed it on mathexchange here about 15 days ago and after some tuning by helps of @Ross Millikian ,it finished in this way:

QUESTION: Can we divide a circle with radius of $\sqrt{3}\sigma$ on a plain into 3 optimal pieces with equal areas assigned by $1,2,3$ as score ,which an ambitious dart player with density probability function of $f(r;\sigma )={\frac {r}{\sigma > ^{2}}}e^{-r^{2}/(2\sigma ^{2})}$[(Rayleigh distribution)][2]as probability of dart hitting in distance of $r$ from his aim point, achieves least score from the designed dartboard plane in his throw (guaranty getting minimum equal score from each point on board he may aim to shoot)?

Are the shapes unique?what are they look like?

Note1: if dart goes out of the board player will get $0$ score. $\sigma$ is standard deviation in Rayleigh distribution and dart hits in circle of radius $\sigma$ around player's aim point by probability of about $0.39$.

Note2: At first I proposed a generalized form of this problem stating to find $n$ connected regions in a plain which totally shape a connected closed board without any hole, assigned by $n$ natural numbers as score and the goal was to find optimal shape of each number ,But I found this simpler state of the problem as hard as enough to contemplate.

---Another Generalization can be considered: setting a desired predefined score probability function over the dartboard plane domain and the challenge is to design a dartboard which give us that predefined function as score probability in each point, like to design a deceiving dartboard which the score probability be least for points of region assigned by score $3$ and be highest for points of region assigned by score $1$. for easing the problem I have considered a constant function with minimum value which still finding its minimum value is challenging.

Eckmann-Hilton argument / Grothendieck

Wed, 07/11/2018 - 02:26

In terse terms, the “Eckmann-Hilton argument” says that a monoid in the category of monoids is commutative. It is essentially used, for example, to prove that homotopy groups of topological groups are commutative — more generally, that homotopy groups of H-spaces are commutative, in particuler, higher homotopy groups are commutative.

This argument takes its name from its appearance in a 1962 Eckmann-Hilton paper (Group-like structures in general categories, I. Multiplications and comultiplications, Mathematische Annalen, June 1962, Volume 145, Issue 3, pp 227–255) but stems, it seems, from previous work from the same authors (Homotopy and duality, 1959).

It also appears explicitly in algebraic geometry, in Grothendieck's 1961 SGA 1 seminar Revêtements étales et groupe fondamental, devoted to the theory of the fundamental group of schemes. Namely, in Exposé XI (Examples and complements), Section 2 (Abelian varieties), Grothendieck writes (bottom of page 287 of the Springer-Verlag edition) : “On the other hand, since the functor $X\mapsto \pi_1(X)$ from pointed schemes $X$ to groups commutes with produtct, it transforms a group in the first category to a group in the category of groups, i.e., a commutative group.”

Does anybody know whether the two groups of people were aware the one of the other? Was this categorical argument already clear at that time ?

Random $\beta$-transformation and its limit theorem

Tue, 07/10/2018 - 23:20

given probability space $ (\Omega, T, \mu), \mu$ is ergodic and $ T $ is invertible ( can regard $T$ as two sides shift)

define random $\beta$-transformations: random variable $\beta:\Omega \to (1,\infty)$. random $\beta$-transformations $ f_{\omega}: S^1\to S^1: x\to \beta_{\omega}\cdot x \mod(1) $.( it is in fact random Lasota Yorke maps)

let $ f_{\omega}^n=f_{T^{n-1}\omega} \circ f_{T^{n-2}\omega}\circ \circ \circ f_{T^{1}\omega}\circ f_{\omega}$, $ \phi \in BV[0,1]$.

consider the limit behavior of $ \frac{\sum_{i \le n} \phi \circ f_{\omega}^i}{n^{1/2}}$, can we prove it converges(in distribution) to Gaussian distribution a.s. $ \omega$ ( it is called quenched Central Limit Theorem)?

if $ \inf_{\omega}{\beta_{\omega}} >1$, then it is uniformly hyberbolic, the quenched Central Limit Theorem has been understood very well. what about the case $ \inf_{\omega}{\beta_{\omega}}=1$?

Many Thanks!

Gluing locally defined continous functions over complex domain

Mon, 07/09/2018 - 22:06

This is a cross-post to the question I asked at MSE over almost a month ago.

Suppose $n, l, m \in \mathbb N$ and $n \ge l > m$. Let $T: \mathbb C \to \mathcal M(n \times l; \mathbb C)$ be continuous and $T(\lambda)$ has constant rank $m$ for every $\lambda \in \mathbb C$. Suppose for every $\lambda \in \mathbb C$, there is an open neighborhood $U(\lambda)$ of $\lambda$ and a locally defined continuous function $h_{\lambda}: U(\lambda) \to \mathcal M(n \times m; \mathbb C)$ where the image $h_{\lambda}(\beta)$ is a basis for $T(\beta)$ for every point $\beta \in U(\lambda)$. Could we construct a globally continuous function $\phi: \mathbb C \to \mathcal M(n \times m; \mathbb C)$ by gluing together these locally defined $h_{\lambda}$'s, such that the image $\phi(x)$, of every point $x \in \mathbb C$, is a basis for $T(x)$?

What I have in mind: Suppose we have two continuous families of $g_1: \mathbb C \supseteq U_1 \to \mathcal M(n \times m; \mathbb C)$ and $g_2 : \mathbb C \supseteq U_2 \to \mathcal M(n \times m; \mathbb C)$ where $U_1$ and $U_2$ are two open disks in $\mathbb C$ with $U_1 \cap U_2 \neq \emptyset$. Then $(g_1^1(x), \dots, g_1^m(x))$ is a basis for $T(x)$ for all $x \in U_1$ and $(g_2^1(y), \dots, g_2^m(y))$ is a basis for $T(y)$ for all $y \in U_2$ where $g_i^j: x \mapsto \mathbf c_j( g_i(x))$ where $\mathbf c_j(\cdot)$ denotes the operation of taking the $j^{th}$ column of a matrix. Now for every $y \in U_2 \cap U_1$, ${g}_1 (y) = g_2(y) S(y)$ for some $S(y) \in GL_m(\mathbb C)$. It follows $S(y) = (g_2^T(y) g_2(y))^{-1} g_2^T(y) g_1(y)$. By Cramer's rule, $S(y)$ is continuous with respect to $y$. That is we have a well defined continuous function on $U_1 \cap U_2$, $S \colon U_1 \cap U_2 \to GL_m(\mathbb C)$. Since $U_1 \cap U_2$ is simply connected, there is a continuous retract $r :\mathbb C \to U_1 \cap U_2$. It follows $S \circ r : \mathbb C \to GL_m(\mathbb C)$ is well defined and continuous with $S \circ r|_{U_1 \cap U_2} = S$. So we can define $g$ by \begin{align*} g(x) = \begin{cases} g_1(x), & \text{ if } x \in U_1 \setminus U_2 \\ g_2(x)(S\circ r)(x) , & \text{ if } x \in U_2. \end{cases} \end{align*} This function is clearly continuous by construction and satisfies the prescribed condition.

I am not sure whether above argument is completely correct. Even if it was correct, my problem to proceed is: after we glue some collection of maps, the domain $U$ would become not so "regular". I am not sure the intersection of $U$ and an open disk would still be simple connected.

On institute all over world reference

Mon, 07/09/2018 - 03:03

Can anybody give reference what are the best institutes all over the world for doing von Neumann algebras and where the groups are strong, and also the procedure for applying Ph.D?

The problem about the eigenvalues of Nonnegative Matrices in form of upper triangle

Mon, 07/09/2018 - 02:42

A matrix $G=\left[ \begin{array}{cc} A & B \\ C & 0 \\ \end{array} \right]$, where $A$ is a Metzler matrix, $B$ and $C$ is a non-negative matrices, namely the matrix $G$ is a a Metzler matrix as above special form.

My question is: does the statement hold?:

1.There exists at least a positive eigenvalue for the special matrix, namely $G \not=$ Hurwitz.

Adjoint orbits of a finite group of type $G_2$ [reference request]

Mon, 07/09/2018 - 02:20

Let $q=p^\alpha$ be a prime power and $k=\mathbb{F}_q$. Let $G\subseteq \mathrm{GL}_N(k)$ be a simple finite group of Lie type, with root system of type $G_2$, and let $\mathfrak{g}\subseteq \mathfrak{gl}_N(k)$ be (the $k$-points of) its Lie-algebra.

Is anybody aware of an accessible reference where I could find a classification of the orbits for the adjoint action of $G$ on $\mathfrak{g}$, including orbit sizes?

Other exceptional groups over $k$ are also of interest to me, so if such a reference for them also exists I'd be happy to hear about it.

Thank you!

Strongly finite projections in $*$-rings

Mon, 07/09/2018 - 01:24

Let $A$ be a $*$-ring. Let us have some points:

i) We recall that a projection $p$ is a self-adjoint idempotent that is $p=p^*=p^2$.

ii) On the set of projections, we write $p\leq q$ if $pq=p$.

iii) A projection $p$ is called strongly finite if there exist at most finitely many projections $q_1,\cdots,q_n$ with $q_j\leq p$.

iv) For a given $x\in A$, we put $l(x)$ to be the smallest projection with $l(x)x=x$.

Q. Assume that $e$ is an strongly finite projection. Let $p$ be a projection. Is $l(ep)$ an strongly finite projection?

Remark. In this discussion, we assumed $l(x)$ exists for every element $x\in A$. For example $A$ may be assumed a Baer *-ring.

Asphericity of hypersurface complement in ${\mathbb C}^n$

Mon, 07/09/2018 - 00:32

How does one check that the following space is aspherical? $X_n=\{(x_1,x_2,\ldots , x_n)\in {(\mathbb C^*)}^n\ |\ x_i\neq x_j\ and\ x_ix_j\neq 1\ for\ i\neq j\}$.

One way I can think of is to give a map to $Y_{n-1}=\{(y_1,y_2,\ldots , y_{n-1})\in {(\mathbb C^*)}^{n-1}\ |\ y_i\neq y_j\ for\ i\neq j\}$ which is a locally trivial fibration. After replacing $\mathbb C$ by $\mathbb R$ and for $n=2$, I drew a picture and it seems a suitable map should be $(x_1,x_2,\ldots , x_n)\mapsto (\frac{x_i-x_n}{2},\ldots , \frac{x_{n-1}-x_n}{2})$.

But then how does one check that this map is a locally trivial fibration? $Y_n$ is aspherical by taking projection and applying long exact homotopy sequence and induction. Using a result of Fadell-Neuwirth the projections in the case of $Y_n$ are locally trivial fibrations.