**2**

votes

**1**answer

79 views

### Existence of neighborhood inclusion for 4-chordal graphs

Let $N(v)$ be the (open) neighbourhood set of a vertex $v$, and let $N[v]$ be the closed neighbourhood set of $v$.
A graph $G$ is called 4-chordal if $G$ has no induced cycle with five or more ...

**2**

votes

**3**answers

513 views

### a colouring / matching problem

While trying to find a bijection which preserves various combinatorial statistics, I was led to the problem below. Very much to my surprise, a closely related question, Coloring summands of given ...

**9**

votes

**0**answers

119 views

### Computing exact or asymptotics for number of strings over an alphabet of size $n$ that have no non-trivial substrings that appear more than once

I ran across a seemingly relatively simple combinatorics problem that appears open. For an alphabet of size $n$, let $A(n)$ be the number of strings over the alphabet that have no substring of length ...

**0**

votes

**1**answer

58 views

### Monotonicity of the gap of permutated sequence

Let $a$ be an arbitrary sequence and denote by $\mbox{gap}_k(a) = a_{(k)} - a_{(k+1)}$, where $a_{(k)}$ is the $k$th largest component of $a$. Of course, $k+1$ should be no larger than the length of ...

**1**

vote

**2**answers

139 views

### Non-DS circulant graphs

Let $p$ be a prime number greater than or equal to 11. Are there any cospectral non-isomorphic graphs with circulant graphs on $p$ vertices.
Which circulant graphs over prime number of vertices ...

**2**

votes

**1**answer

131 views

### Vanishing homology of simplicial complexes with few facets

Let $K$ be a simplicial complex with $n$ vertices and $n-t$ facets, where $t \geq 3$.
Is it true that the $(n-3-j)$th reduced homology (with coefficients in a field) of $K$ vanishes for $0 \leq j ...

**5**

votes

**2**answers

281 views

### Random Vornoi Diagrams (particular measures)

This is my second question about Random Voronoi diagrams, in my first question was given some excellent advice but i was not clear in explaining what i was looking for.
I'm interested to know ...

**8**

votes

**2**answers

625 views

### Random Voronoi Diagrams

I'm interested in what research has already been done with regards to the statistics of random voronoi diagrams. I have had a look on google scholar and results are a little inconclusive. I'm ...

**2**

votes

**1**answer

195 views

### On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections

Let $n$, $t \in \mathbb N$ two natural numbers such that $0<t<n$, and let $A$ be a set of $n$ elements.
We call a quasi-partition or q-p of $A$ a subset $W \subset \mathcal P(A)$ such that we ...

**13**

votes

**2**answers

297 views

### Flag complexes that are shellable but not vertex decomposable

As the title suggests, I was wondering if anyone can point me to any examples in the literature to flag complexes that are shellable but not vertex decomposable.
It is well-known that if a ...

**6**

votes

**1**answer

173 views

### Counting cyclic binary sequences of length $n$ where ones appear in blocks of length at least $k$

How many binary cyclic sequences of length $n$ exist, where ones only appear in blocks of length at least $k$? We do not consider sequences that result from each other by a cyclic shift equivalent.
...

**13**

votes

**1**answer

337 views

### A method for making a graph bipartite

Given any graph $G$, can we find a bipartite subgraph of $G$ with at least $e(G)/2$ edges ($e(G)$ is the number of edges in $G$) by sequentially deleting the edge belonging to the most number of odd ...

**1**

vote

**1**answer

83 views

### Number of points in an intersecting linear hypergraph

I first asked the question below at math.stackexchange.com ( http://math.stackexchange.com/questions/920442/number-of-points-in-an-intersecting-linear-hypergraph ) but somebody suggested I ask it in ...

**3**

votes

**0**answers

78 views

### More 3-connected cubic graphs with all 2-factors of same cycle type?

The setup is as in this question: Let $G$ be a 3-connected cubic graph. If all 2-factors of $G$ are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type, we'll say that $G$ is ...

**5**

votes

**1**answer

305 views

### Are there number-theoretic graphs that are far from being isomorphic

I say that two graphs $G_1=(V_1,E_1)$, $G_2 = (V_2,E_2)$
with the same number of vertices, edges,
are $\epsilon$-far from being isomorphic, if for any bijection between $V_1$ and $V_2$, the fraction ...

**-3**

votes

**1**answer

155 views

### How many sequences of length n satisfy these constraints? [closed]

I want to count the number of unique sequences of length n with the following constraints.
Each element of the sequence is an integer in $\lbrace 1,2,\dots,n\rbrace$.
Each two adjacent elements of ...

**0**

votes

**1**answer

91 views

### Comparing ideals in posets

Consider a partially ordered set $P$, and two upper sets $U_1$, $U_2$ in this poset.
What are some natural ways to measure how equal these two upper sets are?
This question arise naturally in the ...

**5**

votes

**0**answers

160 views

### (Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples

Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...

**12**

votes

**2**answers

479 views

### The sum of the carries when adding and multiplying two numbers in base p

Let $\sigma_p(m,n)$ (resp. $\pi_p(m,n)$) denote the sum of the carries when adding
(resp. multiplying) the numbers $m=\sum_{k\ge0}m_kp^k$ and $n=\sum_{k\ge0}n_kp^k$ using base-$p$ arithmetic where ...

**19**

votes

**1**answer

821 views

### Recognize this strange expression from linear algebra?

I've come across an odd-looking expression and oh how I wish I had a more elegant description of it. Maybe someone who enjoys symmetric bilinear forms in characteristic two will recognize it? Or ...

**4**

votes

**2**answers

102 views

### Which criteria guarantee an orthogonal circuit in $\mathbb R^3$ to be rigid?

For $n\ge4$, define an orthogonal circuit or O-circuit as a closed circuit of $n$ unit segments in $\mathbb R^3$ such that any two neighboring segments form a right angle. (Physically this could be ...

**3**

votes

**1**answer

121 views

### Uniformly permutation and the length of a size biased cycle

The cycle containing $1$ of a uniform permutation has length which is uniformly distributed. I was wondering if the converse is true:
Suppose $\sigma$ is a permutation on $\{1,\dots,n\}$ and let ...

**1**

vote

**0**answers

93 views

### reference on aperiodicity and cluster [closed]

From this image:
I believe there is a message relating those clusters drawn in picture and aperiodic tiling. Does anyone have some reference on this? Thank you :)

**0**

votes

**1**answer

80 views

### reference request for automata of this type [closed]

Consider the list of length $m$ $(1,0,\dots 0)$ we call this list $l_1$, we now define a sequence of lists recursively, where $l_1$ is the previous list, and if $l_n$ is the list $(a_1,a_2\dots a_n)$ ...

**6**

votes

**1**answer

166 views

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

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

**2**

votes

**0**answers

85 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 ...

**1**

vote

**2**answers

172 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) ...

**3**

votes

**1**answer

236 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

72 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

88 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 ...

**5**

votes

**1**answer

152 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, ...

**4**

votes

**2**answers

160 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 ...

**5**

votes

**0**answers

151 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 ...

**2**

votes

**2**answers

105 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 ...

**2**

votes

**0**answers

47 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

122 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 ...

**9**

votes

**2**answers

358 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

77 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 ...

**8**

votes

**2**answers

251 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$ ...

**1**

vote

**1**answer

63 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

122 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 ...

**6**

votes

**1**answer

259 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

208 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

157 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 ...

**5**

votes

**1**answer

167 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

264 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

210 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

182 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

239 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?

**5**

votes

**1**answer

188 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 ...