User fkenter - MathOverflow

Answer by fkenter for Is there a proper way to define a threshold vertex density for a random graph s.t. the graph is fully connected?

2013-04-12T10:03:54Z

The technical term is just that: "connectivity threshold" or "threshold for connectivity".

In general, the connectivity threshold and the giant component threshold are different. Take, for example, the percolation thresholds on the path $P_{n/2} + K_{n/2}$. In this case, the giant component threshold is $p = 1/n$ but the connectivity threshold is $p = 1$.

Distribution of Induced Subgraphs of Extremal Ramsey Graphs

2013-04-11T23:31:18Z

Choose $k$. Let $G = (V,E)$ be a graph on $n = R(k,k)-1$ vertices (that is, $G$ is an extremal example for $R(k,k)$, and $g : E \to {r, b}$ be an edge 2-coloring such that there is no monochromatic $k$ clique.

Define $\tau(i)$ to be the proportion of $K_k \subset G$ such that exactly $i$ of the edges are colored $r$.

Questions: Are there any (nontrivial) properties known about $\tau$? Most interestingly, does $\tau \to$ normal distribution as $k \to \infty$?

PrincipAl Eigenvector of a Random Matrix

2012-04-21T11:18:00Z

Let $A$ be a random matrix, let $\mathbf{x}$ be the singular vector associated with $\|A\|$. Let $\bar A$ be the entry wise expectation of $A$, and let $\mathbf{\bar x}$ be the singular vector associated with $\|\bar A\|$.

Given $\epsilon > 0$, what conditions are necessary to have:

$$P [ \|\mathbf{x} - \mathbf{\bar x}\| > \epsilon] < \epsilon ?$$

Answer by fkenter for Effect of different graph operations on spectrum of graph laplacian?

2011-09-29T23:47:25Z

I asked this question a long time ago, the best reference given to me is an interlacing theorem by Chen, et. al. which says that the eigenvalues of the (normalized) Laplacian of a graph $G-e$ are interlaced by the eigenvalues of the graph of $G$.

http://epubs.siam.org/sidma/resource/1/sjdmec/v18/i2/p353_s1

Field of Values and Eigenvalues

2011-05-09T17:39:59Z

Let $A$ be an $n \times n$ matrix. Define the field of values of $A$, denoted $W(A)$, as

$ W(A) := \{c \in \mathbb{C} : \exists x \in \mathbb{C}^n, \|x\|_2 = 1, x^H Ax = c \} $

The question is, suppose one knows the spectra and singular values of $A$, are there any nontrivial bounds for the distance between an eigenvalue $\lambda$ and the edge of the field of values $\partial W(A)$?

Unwritten Rule Of Writing Own Name

2011-03-30T23:41:10Z

In mathematics, there is an unwritten rule that one is not supposed to write his or her own name (using initials or "the author" if necessary) or attach his or her own name to something (e.g., to have something named after you, someone else should first call it that).

A few questions:

First, is this rule, in some form, in fact written down somewhere? If so, where?

Second, what circumstances, if any, is it appropriate to use your own name?

Lastly, does the rule extend to other people referring to the originator of an idea and the idea? For example, is it appropriate to say "X proved the X Theorem."? Or does this make it seem as though (to a small degree) that X broke the unwritten rule? While less explicit, would it be preferred to say "X proved his/her theorem regarding Y on Z."?

I apologize for the "soft" question, but the discussion and answers are certainly appreciated.

x-th moment method

2010-09-20T20:09:21Z

For a real-valued random variable, $X$, the first moment method, is simply

$P(X\ge\mathbb{E}[X])>0$

This can be extended to the second moment quite easily:

~~$P(X\ge\mathbb{E}[X]+\sqrt{Var[X]})>0$~~

$P(|X-\mathbb{E}[X]|\ge\sqrt{Var[X]})>0$

The question must be asked: How does one generalize this to higher (probably centralized) moments?

Edit: Good catch Mark! Let me rephrase the question in another way

Let $X$ be a real-valued random variable. Given only the first $n$ moments of $X$: $\mathbb{E}(X), \ldots, \mathbb{E}(X^n)$, what is the largest value for $|X-\mathbb{E}[X]|$ that can be guaranteed to have positive probability?

Measures for asymmetry of direct graphs?

2010-08-30T21:21:39Z

While, very objective, I was wondering what "measures for asymmetry" are used for directed graphs. That is, a quantity that, in some sense, indicates how asymmetric the graph is.

Comment by fkenter

2013-04-12T22:54:34Z

This site is not meant for homework help or casual questions. It is intended for research mathematics. The answer to your question lies, simply, with linearity of expectation.

Comment by fkenter

2013-04-12T10:15:38Z

Since a random coloring yields a decent construction for constructing Ramsey graphs (at least up to roughly at least $R(k,k)/4$ vertices),one might expect the distribution of colors to be "random" even for larger extremal examples. If this is the case, $\tau$ follows a binomial distribution; which for large enough $k$ (appropriately normalized) would limit towards a normal distribution in probability.

Comment by fkenter

2013-04-12T09:45:25Z

I will be honest, I do not understand your question. In particular, the meaning of "box", "input", "output", and "pair" are not clear. Perhaps you should explain your examples in more detail.

Comment by fkenter

2010-08-31T22:53:57Z

I guess to clarify the question: I am looking for a list of widely-used (probably numerical) directed-graph invariants that tend to increase whenever the number/proportion of unreciprocated arcs (i.e., an arc (u,v), where (v,u) is not an arc) increase. That is, '(a)symmetric' here refers to the (a)symmetry of arcs.