**1**

vote

**0**answers

14 views

### Properties of Optimal k-Tour Spanners

Let the edge set of a Optimal k-Tour Spanner of a graph $G$ be equal to the edges of $G$ that lie on at least one optimal tour through exactly $3<k<n$ distinct vertices of $G$.
I would like ...

**10**

votes

**3**answers

452 views

### Self-Similar Graphs

Many fractals can be generated using and infinite sequence of graphs. For example, Sierpinski's Gasket could be generated by the following sequence of graphs.
Many definitions of fractal dimensions ...

**5**

votes

**2**answers

352 views

### What is the permutation group generated by those three given morphisms of the affine space $\mathbb{F}_q^3$?

Let $\mathbb{A}^3 = \mathbb{F}_q^3$. Consider the following three functions $\mathbb{A}^3\to\mathbb{A}^3$:
\begin{eqnarray*}
h: (x, y, z) &\mapsto& (x, y, xy - z) \\
u: (x, y, z) ...

**18**

votes

**1**answer

410 views

### Rearrangements that never change the value of a sum

I posted this question on math.stackexchange.com and so far the only answer posted (also mentioned in the comments under the question) shows that one of my rash initial guesses about the bottom-line ...

**0**

votes

**0**answers

57 views

### Is there a general theory for the structure of the (semi)group generated by morphisms of an affine space $F_p^3$?

Consider an affine space $\mathbb{F}_p^3$, and assume we have a handful of morphisms $f_i : \mathbb{F}_p^3 \rightarrow \mathbb{F}_p^3$ given by $$f_i(x, y, z) =(P_i(x, y, z), Q_i(x, y, z), R_i(x, y, ...

**2**

votes

**0**answers

27 views

### s-arc transitivity and the Moore bound

Given a vertex $x$ of a graph, call the subgraph induced by all vertices of distance $\le n$ from $x$ the $n$-neighbourhood of $x$, denoted $N_n(x)$.
Let $G$ be a regular graph of diameter $n+1$. For ...

**3**

votes

**0**answers

61 views

### Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras

A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given ...

**13**

votes

**2**answers

976 views

### Is there a $q$-L'Hospital's Rule?

Let $\binom{n}{j}_q$ be a $q$-binomial coefficient and $(x;q)_n = (1-x)(1-qx)\cdots(1-q^{n-1}x).$
Consider the sum $$f(n,m,r,k)= \sum\limits_{j = 0}^{2n} {( - 1)}^{ j}q^{mj^2+rj}
...

**5**

votes

**1**answer

300 views

### Terminology in combinatorics

I met the following two combinatorial concepts during a study outside of combinatorics. I am wondering if there are common terminologies in combinatorics.
A finite graph $G$ has the following ...

**5**

votes

**2**answers

229 views

### Does the ring generated by the odd power sum symmetric functions have a name?

Let $\Lambda$ be the ring of symmetric functions and recall the power sum symmetric function $p_i = \sum x_1^i + x_2^i + \dots$ generate this ring. Let $\tilde\Lambda$ be the ring generated by the odd ...

**7**

votes

**0**answers

195 views

### Pattern Avoidance in Poset Permutations

I am not sure if it is appropriate to use MathOverflow to publicize a conjecture, but I think this is an interesting question and I have no real ideas of how to solve it.
A permutation on a ...

**5**

votes

**1**answer

84 views

### Matroids similar to the cycle matroid

Let $G=(V,E)$ be a graph (loops and multiple edges are permitted). Three following systems of dependent sets in $E$ define matroids:
1) Set $A\subset E$ is dependent if $A$ contains cycle. This is a ...

**9**

votes

**1**answer

355 views

### Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns)

The parameters of the problem are $m$ numbers which are integers (these numbers are denoted $b_i$), $n$ urns and in each urn, we can place $C$ numbers. We assume $nC \geq m$ so that the problem is ...

**-2**

votes

**1**answer

93 views

### Recursion, Common Term, Combinatorics [closed]

May we find the common term for recursive sequence? if yes that how to find the common term of recursive sequence such: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 ...
in a ...

**2**

votes

**0**answers

62 views

### A specific class of $(0,1)$-matrices

Let $T_n$ be the class of $(0,1)$-matrices of order n with no row sum equal to a column sum. Is there any name or research about this kind of matrix?
For any $A\in T_n$, let $S_A$ be the sum of all ...

**5**

votes

**1**answer

97 views

### Asymptotics of a Bivariate Generating Function

I have the following generating function,
$$G(x,y)=\sum_{n,k \geq 0}a(n,k)x^ny^k = \frac{(y^2-y)x+1}{(y-y^3)x^2-(y+1)x+1}$$
and I am interested in obtaining an asymptotic for the sequence $a(n,k)$ ...

**1**

vote

**2**answers

138 views

### How do powers affect asymptotics in generating functions?

Let $a_n$ be a sequence of non-negative real numbers, and $A(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$ its exponential generating function. Also, suppose $B(x) = \sum_{n=0}^{\infty} b_n ...

**0**

votes

**1**answer

128 views

### Decomposition of a regular graph and connected subgraphs

I have asked almost same question earlier. I have been told that my question was poorly written, so I am trying to write it more clearly in this post. Also, this time I would be a little different in ...

**1**

vote

**0**answers

149 views

### Probability of correlated residues

Given $N,c\in\Bbb N$, where $c\ll(\log N)^{1/b}$ for any $b>1$ is fixed, what is the probability that given $A_1,A_2,A_3\in\Bbb N$ with ...

**4**

votes

**1**answer

144 views

### Number of bases of a matroid

I would like to know the minimum number of bases of a matroid of rank $k$ and $n$ elements, knowing that each singleton is independent. At least for small ranks.

**4**

votes

**0**answers

118 views

### How many different sums of parts of a vector

I hope this question isn't too basic for MO. I also asked it on math.se previously. This mathematical puzzle was given to me by a friend a while ago and I can't work out how to solve it. Does anyone ...

**0**

votes

**0**answers

70 views

### Showing that a sequence of random variables with increasing expected value converges to a Poisson random variable

Consider a sequence $\{X_n\}_{n \geq 1}$ of nonnegative, integer-valued random variables. For any random variable $Y$ and $k \geq 1$, let $(Y)_k = Y(Y-1)(Y-2)\dots(Y-k+1)$ be the $k^\mathrm{th}$ ...

**14**

votes

**0**answers

254 views

### An algebraic strengthening of the Saturation Conjecture

The Saturation Conjecture (proved by Knutson-Tao) asserts that
$c_{n\mu,n\nu}^{n\lambda}\neq 0\Rightarrow c_{\mu,\nu}^{\lambda} \neq
0$, where $c$ denotes a Littlewood-Richardson coefficient and $n$ ...

**18**

votes

**0**answers

241 views

### Minimal number of intersections in a convex $n$-gon?

For a convex polygon $P$, draw all the diagonals of $P$ and consider the intersection points made by those diagonals. Let $f(n)$ be the minimal number of such intersections where $P$ ranges over all ...

**2**

votes

**1**answer

130 views

### Is the top interval of a finite distributive lattice an hypercube lattice?

Let $(L,\wedge,\vee)$ be a finite distributive lattice. Let $M$ be the (unique) maximum element. An element $a \in L$ is called maximal if $a \le a' < M$ implies $a = a'$. Let $b = ...

**1**

vote

**0**answers

24 views

### What is the minimum number of filled cells in a partial Latin rectangle with autotopism group $\cong C_2$ and autoparatopism group $\cong S_3$?

Definitions: a partial Latin rectangle is an $r \times s$ matrix containing symbols from $[n] \cup \{\cdot\}$ such that each row and each column contains at most one copy of any symbol in $[n]$. The ...

**3**

votes

**0**answers

93 views

### A question on the behavior of intersections of certain block design

Let $[d]$ be a universe and $S_1, \dots, S_m$ be an $(\ell, a)$-design over $[d]$ which means that:
$\forall i \in [m], S_i \subseteq [d], |S_i|=\ell$.
$\forall i \neq j \in [m]$, $|S_i \cap S_j| ...

**0**

votes

**0**answers

71 views

### A constrained minimum edge coloring

Is minimum number of colors needed to color edges of complete graph $K_n$ so that every even simple cycle contains at least one color assigned to odd number of edges at most $\beta n$ where ...

**6**

votes

**1**answer

132 views

### Writing the quotient of solutions of linear ODEs as the solution of a nonlinear ODE

Let $A(x)$ and $B(x)$ be solutions to homogeneous linear ODEs with polynomial coefficients, i.e., $A(x)$ satisfies
$$p_KA^{(K)} + p_{K-1}A^{(K-1)} + \cdots + p_1A' + p_0A=0$$
and $B(x)$ satisfies
...

**1**

vote

**1**answer

315 views

### Analytic Number Theory without Pigeonhole Principle [closed]

I don't know if this is an appropriate question for this website, but I will try my luck.
I am an undergraduate student, and recently I became interested in analytic number theory. When I started ...

**1**

vote

**0**answers

103 views

### Efficiently counting all paths of length n in a graph with vertex visitation contraints [closed]

I have a graph G with two classes of vertices. The first class represents no resource limitation entities and can be visited an unlimited number of times in any path traversal. The second class of ...

**1**

vote

**0**answers

172 views

### system with solutions $\{x-a:0\leqslant a\leqslant z-1\}$ [closed]

What must be $F$ there where $0=F(1,x,0)=F(x-0,x,z)=F(x-1,x,z)=F(x-2,x,z)=F(x-3,x,z)=$ $\dots$ $=f(x-z-1,x,z)=0$?
Define $F$ in the domain where a continuous function exists that behaves so for ...

**2**

votes

**1**answer

100 views

### Inducing representations from the stabilizer of a partition

For each positive integer $i$, let $A_i$ be a fixed representation of the symmetric group $S_i$. I won't tell you exactly what $A_i$ is, but let's say that I have a very explicit description of its ...

**6**

votes

**2**answers

658 views

### Incidence geometry and matrices

Supposing I have a $0/1$ or $\pm1$ matrix $A$ of size $m\times n$, is there a minimum $d$ (that works for every $m\times n$ $A$) such that there exists $m$ lines $r_1,\dots,r_m$, $n$ lines ...

**1**

vote

**0**answers

367 views

### Possibility of Disconnected Subgraphs of a $k$ Connected $r$ regular Graph under a given condition

Context: Given a adjacency matrix A of a $r$-regular graph $G$ (not complete graph $K_{r+1}$) . $G$ is $k$ connected.
The matrix A can be divided into 4 sub-matrices based on adjacency of vertex $x ...

**7**

votes

**1**answer

607 views

### Counting subspaces

We are given the finite vector space $V = V(n,p) = \mathbb{F}_p^n$ and two fixed subspaces $W_1, W_2 \subseteq V$ of dimensions $m_1$, $m_2$ respectively. Suppose
that the dimension of $W_1 \cap W_2$ ...

**8**

votes

**2**answers

232 views

### Dividing the edges and diagonals of a polygon among disjoint sub-polygons

Let $P$ be a convex $n$-gon ($n$ is odd and $n \geq 5$).
Determine the smallest $m$ such that all edges and diagonals of $P$ can be covered by the edges
of $m$ convex sub-polygons of $P$ which ...

**12**

votes

**2**answers

449 views

### Number of nonzero terms in polynomial expansion (lower bounds)

Let $f(x) = a_1x^{z_1} + a_2x^{z_2} + \cdots + a_kx^{z_k}$ be a polynomial with coefficients $(a_1, \ldots, a_k) \in \mathbb{F}_q^*$ and $z_i$ are distinct positive integers. If I need to compute the ...

**1**

vote

**0**answers

161 views

### Nimbers and Surreal Numbers [closed]

I have been researching Combinatorial Game Theory. One common theme is the assignment of values to games in order to classify the game as a win for a specific player. One such way is class of surreal ...

**5**

votes

**1**answer

153 views

### Modification of matching

Suppose i have an $n \times n$ random bipartite graph and suppose that i repeat the following process $n$ times. At the start (stage 1) each edge is selected independently with probability $p(n)$, and ...

**2**

votes

**1**answer

78 views

### Images of interval edge coloring

I found out the definition of interval edge colorings, concept put by Kamalian in various papers but could not find a graph depicting an example. Where can I find pictures of explicit examples of ...

**8**

votes

**1**answer

213 views

### Smallest strongly regular graph whose automorphism group is not vertex transitive?

I'm looking for a small strongly regular graph whose automorphism group is not vertex-transitive.
This answer to a different question shows that the Chang graphs on 28 vertices are such graphs. Is ...

**2**

votes

**1**answer

103 views

### Enumerator Polynomials for Linear Anytime Codes

Let $C = \{c \in \mathbb{F}^n_2 : Hc=0\}$ be a binary linear code where $H \in \mathbb{F}^{k \times n}_2$ is a block lower-triangular matrix of full rank called the parity-check matrix of $C$. Clearly ...

**3**

votes

**3**answers

110 views

### Are there references for the properties of words formed in finite groups using L-systems? (In particular, the algae L-system.)

Let $G$ be a (finite) group, and $a, b \in G$ be any two elements. Consider the sequence defined by
\begin{eqnarray*}
s_0 &=& a, \\
s_1 &=& b, \text{and} \\
s_{n+2} &=& s_{n+1} ...

**9**

votes

**1**answer

339 views

### Generalized geometries

Let $S$ be a non-empty set. A geometry of type $n$ for $n\geq 1$
on $S$ (consisting of at least $n$ elements) is a set ${\mathfrak P}\subseteq
{\mathcal P}(S)$ such that
all members of $\mathfrak ...

**8**

votes

**0**answers

88 views

### types of generating functions (ordinary, exponential, ???) closed under substitution

A nice feature of ordinary and exponential generating functions is that they are closed under substitution: if $F(z)$ and $G(z)$ both have integer coefficients, then $F(G(z))$ also has integer ...

**4**

votes

**1**answer

184 views

### Is the simplicial set $(\Delta_3/\partial \Delta_3)^{\Delta_1}$ finite?

A simplicial set is called finite if it has only a finite number of non degenerate simplicies (or equivalently, if its number of $n$-simplicies grows polynomially with $n$). In an answer to a ...

**3**

votes

**1**answer

143 views

### Counting triple-free sequences

The Thue-Morse sequence is a triple-free element $(a_i)\in\{0,1\}^\mathbb{N}$ which can be constructed by iterating the transformations $0\to 01$ and $1\to 10$ starting from $0$.
The beginning of the ...

**5**

votes

**0**answers

179 views

### Paths in Pascal's triangle; or balanced $0-1$ initial segments

Here is a problem arising (via a tortuous path) from trying to determine the spectrum of Vershik's adic map on Pascal's triangle (a moderately well-known question: is the spectrum trivial, that is, is ...

**-2**

votes

**1**answer

107 views

### Two graph structures on $\text{Hom}(G,H)$

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq [V]^2 := \{\{a,b\}: a\neq b \in V\}$. A graph homomorphism between graphs $G, H$ is a map $f:V(G)\to V(H)$ such that $\{v, ...