# Tagged Questions

**0**

votes

**0**answers

13 views

### Coloring summands of given n-partition with given weights of colors

Let $\lambda$ and $\sigma$ be n-partitions $\lambda_1+\lambda_2+\cdots+\lambda_l=n$ and $\sigma_1+\sigma_2+\cdots+\sigma_s=n$
Then let $M_{\lambda \sigma}$ be the number of ways to colour blocks of ...

**2**

votes

**0**answers

44 views

### second smallest eigenvalue Laplacian - submodular set function

Let $G$ be a connected unweighted undirected graph. In addition, let $\lambda_2(L(G))$ be the second smallest eigenvalue of the Laplacian matrix of graph $G$. Is $\lambda_2(L(G))$ a submodular set ...

**0**

votes

**0**answers

99 views

### Applications of infinite permutations [on hold]

I was looking at approximation in the forlmula of Products of necklaces:
$n \to \infty$ we have $\prod_{p=1}^n N(p,a) \approx \frac {a^n} {n!}$ $\prod_{p=1}^n \frac {1-a^p} {1-a}$. (The number of ...

**1**

vote

**2**answers

133 views

### Cubic Cayley (undirected) graphs

The generators of a cubic Cayley graph always include at least one involution, since 3 is odd. There are then two possibilties for the other two generators: either (A) they are also (distinct) ...

**2**

votes

**1**answer

182 views

### Dynamics in the integers - Floor function

Let $\alpha$ be an irrational with $0<\alpha<1$. Consider the function given by \begin{align*}
f: &\mathbb{N}\longrightarrow \mathbb{N}\\ &x\longmapsto [ \alpha\cdot x]\end{align*} where ...

**2**

votes

**0**answers

40 views

### Multi-dimensional permanent of structured tensor

I am facing the multidimensional permanent
\begin{equation} \text{perm}(W) = \sum_{\sigma, \rho \in S_n} \prod_{j=1}^n W_{j, \sigma_j, \rho_j } \end{equation}
of a 3-tensor $W_{j,k,l}$ of ...

**1**

vote

**1**answer

63 views

### dual (p,q)-property

If the set system $(X,S)$ has the $(p,q)$-property does its dual system also have the property? (Possibly, for different $p$ and $q$.)
Explicitly, I am asking about the equivalence of the following ...

**4**

votes

**1**answer

94 views

### Maximum sets of lattice points such that only a few points collinear

Consider all the integer points $\in [0,n]\times[0,n]$, I want to find the maximum subset $S$ of which such that there are at most $n^\varepsilon(0<\varepsilon<1)$ points in $S$ collinear.
So, ...

**2**

votes

**1**answer

69 views

### Minimum number of transitive paths in tournament

Let $T$ be a tournament with $n$ vertices (i.e., between every pair of vertices there exists an edge in exactly one direction.) For any $k$, the vertices $A_1,A_2,...,A_k$ form a transitive path if ...

**4**

votes

**0**answers

108 views

### Operator connected with Hermite polynomials

For $n \geq 1$, define the following operator $M_n$ on the ring of all polynomials with real coefficients.
$$M_n P(x) = nP(x)^2 - x \int_0^x (P'(t))^2 \, \mathrm{d}t$$
Monomials $x^k$ are mapped to $n ...

**1**

vote

**2**answers

46 views

### Largest eigenvalue adjacency matrix-link deletion

Let G be a connected undirected graph and G\e be a graph obtained by removing a random link e from the graph G. Let $\lambda_1(A(G))$ be the largest eigenvalue of the adjacency matrix of graph G. Is ...

**1**

vote

**0**answers

40 views

### Minimal density hitting set for k-length arithmetic progressions

This is problem which came up in the process of designing a game. Thus, I don't know any previous work relevant to the problem.
Fix a small set $D$ of a natural numbers. For example, $D=\{1,2,3\}$. ...

**1**

vote

**0**answers

78 views

### Kempe chain color swaps in a partially colored map

Crossposted from math.stackexchange.com:
http://math.stackexchange.com/questions/904932/kempe-chain-color-swaps-in-a-partially-colored-map
Question: In this partially Tait's colored map, using ...

**7**

votes

**2**answers

290 views

### Is there a hyperplane avoiding two independent sets?

Let $V$ be a vector space over a field with $5$ elements, $A,B \subseteq V$ independent subsets. Must there be a subspace of $V$ of codimension 1 disjoint from $A \cup B$?

**2**

votes

**1**answer

61 views

### When does a hypergraph represent maximal independent sets?

Let $G = (V,E)$ be a simple graph. Then, we can view the set of maximal independent sets (or the set of maximal cliques) as a hypergraph $H = (V, E')$. This is quite a useful device when connecting ...

**6**

votes

**2**answers

210 views

### How do I find coefficients of a product expansion

Any power series $f(t) = 1 + t \mathbb{Z}[[t]]$ can be uniquely expanded in the following two ways:
$$1 + \sum_{i=1}^\infty f_i t^i =
\prod_{i=1}^\infty (1-t^i)^{-n_i}$$
Here, the $f_i$ and $n_i$ ...

**2**

votes

**1**answer

45 views

### A possible minimal aperiodic set of corner Wang Tile

From one of my previous question Aperiodic set of corner Wang Tile (although it is put on hold), I realize there is a systematic way to construct aperiodic corner type of Wang tile from edge type ...

**5**

votes

**1**answer

92 views

### Aperiodic set of corner Wang Tile [closed]

There is quite some reference on aperiodicity of the edge-type of Wang Tile. But I could not yet find aperiodic corner type of Wang Tiles... Could someone provide me some instances (better with ...

**5**

votes

**1**answer

238 views

### A variation on Bulgarian solitare

It appears that a variation on Bulgarian solitare has a fixed point regardless
of the starting $n$.
For example, let $n=69$, and consider this partition:
$$
(8,8,7,7,5,5,5,5,5,4,3,3,2,2)
$$
In ...

**7**

votes

**1**answer

173 views

### A conjecture about strongly regular graphs

Let $G \neq K_{v}$ be a $(v,k,\lambda,\mu)$ strongly regular graph. After perusing through Brouwer's tables of parameters I have formed the conjecture $$\lambda-\mu \leq \frac{k}{2}.$$
So far I have ...

**0**

votes

**2**answers

110 views

### Terminology for beads/necklace/bracelet problem [closed]

I'm new to mathoverflow but hopefully anyone here can point me in the right direction.
The problem is as follows, imagine you have 4 beads, lets give them numbers 1,2,3,4. Now I want the unique ...

**0**

votes

**0**answers

79 views

### How many possibilities would you have in an android lock pattern, always using all 9 moves? [migrated]

We are doing some research and wanted to know how many possibilities you would have if you would use all 9 dots/options in an (android) swipe lock pattern.
What would the formula be to get to this ...

**3**

votes

**0**answers

81 views

### Full-rank factorization of the graph Laplacian

Is there a combinatorially meaningful full-rank factorization of the Laplacian matrix of a graph?
The usual factorization $L=BB^{T}$, where $B$ is an oriented incidence matrix, is full-rank if and ...

**9**

votes

**2**answers

239 views

### Faster formula to compute sum over partitions

Let $f$ be a function from the positive integers to the real numbers (or some ring...). Let
$$(\star) \quad F(n) = \sum_{n_1 \leq \cdots \leq n_j\atop n_1 + \cdots + n_j = n} f(n_1) \cdots f(n_j), $$
...

**1**

vote

**2**answers

190 views

### Set of distinct real numbers such that all combination of sums are distinct

Let $\Lambda :=\{\lambda_1, \dots, \lambda_n\}$ be a set of $n$ distinct real numbers.
For a given $p \in \mathbb N$, consider further the set
$$I_p := \{ \{i_1, i_2, \dots, i_p\} : i_j \in \{1, ...

**8**

votes

**1**answer

155 views

### Looking for history on a theorem of clique intersections

I have a short paper I'm working on where I prove:
Theorem: Every graph on (2t-1) vertices with no (t+1)-clique has a vertex that is contained in every t-clique.
By "t-clique", I mean a complete ...

**1**

vote

**2**answers

223 views

### Embed one Coxeter System into another

What is a good reference that explains all the braid relations and diagrams for Coxeter systems concisely?
In particular, how do I embed $H_3$ inside $D_6$, or $H_4$ inside $E_8$? Any hints?

**6**

votes

**1**answer

155 views

### Duration and critical groups order in sandpile models and chip firing games

The famous chip firing game (which is closely related to sandpile models) goes like this:
Place chips at the vertices of a graph. REPEATEDLY: If a vertex $v$ of
degree $d_{v}$ has at least ...

**4**

votes

**2**answers

153 views

### Simplicial complices on unlabelled vertices

My question is about (abstract) simplicial complices.
In particular, how many are they if I consider $n$ unlabelled vertices?
For example, if $n=4$, the two complices
$$
\{\varnothing, \{1\}, \{2\}, ...

**5**

votes

**2**answers

228 views

### Matching number and chromatic number

If $G$ is a (finite) graph, denote with $\mu(G)$ the size of any maximum matching in $G$ (this number is also called the "matching number" of $G$).
For odd integers $n$ we have $n=\chi(K_n) = ...

**0**

votes

**1**answer

73 views

### Probability of k overlapping subsets in N trials

Ok, here is what I am attempting to find an answer to:
I draw M uniformly random subsets of size K from the set of numbers $\Omega=\{1, \dots, N\}$ (where uniformly random means that each unique ...

**1**

vote

**1**answer

132 views

### Is there a “Bipartite” Szemeredi-Trotter theorem?

One version of the Szemeredi-Trotter theorem states the following:
Given a set of $L$ lines in the plane, the number of points incident to at least $k$ lines is bounded above by a constant times $L/k ...

**0**

votes

**1**answer

40 views

### average number of cycles and closed walks length k in incomplete directed graph

I asked this question before, but formulation was poor. I've deleted previous question and reformulate it again.
Let graph $G=(N,p)$ is finite simple incomplete directed graph of size $N$ (multiple ...

**11**

votes

**1**answer

634 views

### Szemeredi's theorem in the Gaussian integers

Suppose that $S\subseteq\mathbb{Z}[i]$ has the following properties:
For convenience, let $A_n = \{z : z\in\mathbb{Z}[i], \text{Nm}(z)\le n\}$
$$\limsup_{n\rightarrow\infty} \frac{|S\cap ...

**9**

votes

**3**answers

707 views

### What exact number of domino tilings cannot be realizable?

Inspired by some other questions, (this and this),
I wonder what numbers $n$ there are that satisfy
$$p(n)=\text{there is no region that admits exactly } n \text{ domino tilings}.$$
If this is true, ...

**1**

vote

**0**answers

93 views

### Representation of Permutation group: What is the isormorphism between the equivalent descriptions, (1)using schur functions and (2)abstract tensors

I assume that the two ways of describing the representation of the permutation group using abstract tensors (perhaps more naive but widely used in physics) and schur functions are equivalent. If ...

**34**

votes

**1**answer

852 views

### Do runs of every length occur in this sequence?

This is a repost from user r.e.s's unsolved Math Stack Exchange question: Do runs of every length occur in this string? That question was derived from my original question on the subject: Does this ...

**6**

votes

**1**answer

237 views

### A parity counting problem for subsets over finite fields

Let ${\mathbb F}_p$ be the prime field of $p$ elements and $b$ be an element in ${\mathbb F}_p$.
For a subset $T\subseteq {\mathbb F}_p$, define
$$Bias(T)=|N_e( {\mathbb F}_p,b)-N_o( {\mathbb ...

**4**

votes

**3**answers

196 views

### Can anyone suggest a text on polyhedral theory?

Can anyone suggest a text on polyhedral theory? Particularly on increasing the number of faces under projections. 0,1 polytopes

**13**

votes

**1**answer

456 views

### When is $(q^k-1)/(q-1)$ a perfect square?

Let $q$ be a prime power and $k>1$ a positive integer. For what values of $k$ and $q$ is the number $(q^k-1)/(q-1)$ a perfect square, that is the square of another integer? Is the number of such ...

**6**

votes

**3**answers

766 views

### A stronger version of Van der Waerden's theorem?

Let $W$ be an infinite word over a finite alphabet $\{1,\dots,n\}$ and $k$ a positive integer. An easy application of Van der Waerden's theorem implies the existence of $k$ disjoint and consecutive ...

**2**

votes

**0**answers

47 views

### When polynomial GI implies polynomial (edge) colored GI?

(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).
There are several reductions using transformations/gadgets
of (edge) colored GI to GI. For edge ...

**2**

votes

**0**answers

46 views

### Looking for similar centrality measurement on graph

I'm working on a graph problem somehow related to centrality measurement. Given an undirected, unweighted tree $T$ and a vertex $v$, let $D_i(v)$ be the set of vertices in $T$ that are i hops from ...

**2**

votes

**3**answers

243 views

### Is the reduced plethysm (restricted to 2-columns in Young tableaux) of this Schur funtion known $\mathbb S_{3^1}(\mathbb S_{1^p})$?

I am working on a physical problem, where I need to compute the "reduced plethysm" that is all the irreducibles characterised by the Young tableaux of 2 columns or less. The plethysm problem I want to ...

**1**

vote

**1**answer

113 views

### A Zero-Multiplicity Problem Related to Foulkes' Conjecture

I'm a combinatorialist that is interested in estimating multiplicities of irreps of $1^{S_{kn}}_{S_k \wr S_n}$ (the action of symmetric group on uniform partitions). I'm aware of the difficulty (or ...

**0**

votes

**0**answers

45 views

### Calculating the longest Bracelet(s) Common to a Set of Bracelets

I would like to know, if the following problems has been studied before:
let $\{B_1, ..., B_n\}$ be a set of Bracelets with the same set $\{\beta_1, ..., \beta_k\}$ of beads,
what is the ...

**5**

votes

**2**answers

177 views

### Cubic graphs whose 2-factors all have the same cycle type

Let $G$ be a bridgeless cubic graph. I am interested in such graphs where all 2-factors are isomorphic (as graphs), i.e. have the same partition as cycle type. We'll say that this partition is ...

**6**

votes

**1**answer

267 views

### About an identity which gives immediate proof of the permanent lemma

Let $A$ be a $n \times n$ matrix over field $F$. Let $a_1, \cdots, a_n$ be the column vectors of $A$. For any subset $S \subseteq [n] = \{1, 2, \cdots, n\}$, let $a_S = \sum_{i \in S} a_i$. Alon's ...

**4**

votes

**0**answers

126 views

### Is there a geometric meaning of the Major index?

The actual question I want to ask is whether there is a geometric proof of this famous identity
$$\sum_{\sigma \in S_n} q^{\operatorname{inv} \sigma}=\sum_{\sigma\in ...

**0**

votes

**1**answer

287 views

### Basketball shots and stopping rule

Moved over from StackExchange.
You are taken to play a basketball game where you can shoot basketballs at n slots using a machine that is equally likely to shoot the balls into those n slots. You can ...