**7**

votes

**1**answer

613 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

233 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

462 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

177 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

155 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

85 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

221 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

104 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

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

**9**

votes

**0**answers

94 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

189 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

145 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

191 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

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

**15**

votes

**1**answer

939 views

### Prove that expression is integer

Numerical experiments suggest that
$\binom{2m}{m + k}\cdot\frac{3m - 1 - 2k^2}{2m - 1}$
is integer for all $-m \le k\le +m$. It means that expression evaluation could be implemented very efficiently, ...

**4**

votes

**1**answer

358 views

### Are there enough additive permutations?

I am hoping to learn enough about additive permutations to help with a number theory problem. These permutations also have connections to difference sets, orthomorphisms, transversals, and other ...

**4**

votes

**0**answers

52 views

### Existence of certain graph gadget related to coloring odd hole free graph

Wondering about the existence of graph gadget related to coloring
(or 3-coloring) odd hole free graphs.
Let $G$ be simple $k$-chromatic connected graph with two
vertices $u,v$.
Is it possible $G$ to ...

**4**

votes

**1**answer

126 views

### Set counting problem with a cap on the intersection between the set and a fixed partition

Fix sets $T_1,\ldots T_m$ as a $k$-partition of $[m\cdot k]=\{1,2,\ldots,m\cdot k\}$, so that $|T_i|=k$ and $|T_i\cap T_\ell|=0$.
1) For any $j\le k$, how many sets $C\subset [m\cdot k]$ are there ...

**1**

vote

**0**answers

151 views

### Complexity of reordering a matrix which consists independent sub matrices

Introduction:
Given a matrix A of a $k$ regular graph G. The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$.
$A_x$ is the symmetric matrix of the graph $(G-x)$, ...

**2**

votes

**0**answers

46 views

### Maximum cardinality general factor of a graph

Given a graph $G=(V,E)$ and a set of integers $B(v)$ associated to each vertex, a general factor of $G$ is a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph $(V, ...

**0**

votes

**0**answers

42 views

### Enumeration of simple graphs with given degree distribution/sequence [duplicate]

Is there any exact formula for asymptotic/exact enumeration of simple graphs with given degree sequence? I just found some results about it, but the formula is hold on for some conditions, for example ...

**1**

vote

**0**answers

113 views

### What are constructions for induced $C_5$-free graphs?

During a recent workshop, the question came up whether there are some constructions for graphs that are induced $C_5$-free, but they contain "everything else," so we don't want to forbid $C_5$'s, ...

**0**

votes

**2**answers

342 views

### Worst case difference in rank by column-row swapping

Given a matrix $m\in\{-1,+1\}^{n\times n}$. Consider $m^\sigma$ to be collection of all matrices obtained from $m$ by permuting rows and columns.
Consider $\mathscr{M}[m^\sigma]$ to be collection of ...

**6**

votes

**1**answer

106 views

### Counting equivalence relations with marked classes

The number of equivalence relations on a set of $n$ elements is the Bell number $B_n$.
If we wish to count the number of equivalence classes on a set of $n$ elements where one of the classes is ...

**4**

votes

**0**answers

89 views

### Prove or disprove a claim about covering a polytope by convex polytopes in a certain way

Here is the claim:
Given a polytope $K$ in a unit ball in $\mathbb{R}^d$, there exists a universal constant $C(d)>0$ depending only on $d$ and a countable collection of convex polytopes ...

**10**

votes

**6**answers

1k views

### Algorithms for calculating R(5,5) and R(6,6)

Calculating the Ramsey numbers R(5,5) and R(6,6) is a notoriously difficult problem. Indeed Erdős once said:
Suppose aliens invade the earth and threaten to obliterate it in a year's time unless ...

**2**

votes

**2**answers

222 views

### binomial/factorial identity mod p

In trying to determine the spectrum of a well-known ergodic transformation, I came up with the following useful (for me) result.
Let $p$ be a prime and $a$ a positive integer. Then for $M$ a positive ...

**3**

votes

**1**answer

86 views

### $P_3$-factors for 3-regular, 3-connected cubic graphs

Suppose that $G=(V,E)$ is a simple graph.
We know if $G$ is 3-regular, 3-connected and $|V|=4k$ for some $k\in \mathbb{N}$, then $G$ has a $P_4$-factor.
Question. Let $G=(V,E)$ be 3-regular, ...

**0**

votes

**0**answers

23 views

### Complexity of edge coloring graphs of sufficiently large maximum degree

I am interested in the complexity of edge coloring
graphs with $\Delta(G) > |V(G)|/3$.
This is closely related to the Overfull conjecture (OC).
Conjecture/Question: If a simple graph G with n ...

**2**

votes

**2**answers

181 views

### Simultaneous lcms

Suppose that we have some finite number of $k$-tuples then we define the lcm of two of these tuples to be the tuple of lcms of the co-ordinates. E.g. $[(9, 10), (5, 18)] = ([9, 5], [10, 18]) = (45, ...

**16**

votes

**0**answers

304 views

### Need explicit formula for certain “$q$-numbers” involving gcd's

The question is motivated by yet another possible approach to a combinatorial problem formulated previously in "Special" meanders. I'm not giving details of the connection as I believe the ...

**7**

votes

**2**answers

281 views

### When is a sequence the sum of two Beatty sequences?

In other words, given a sequence $(s_n)$, how can we tell if there exist irrationals $u>1$ and $v>1$ such that
$$s_n = \lfloor un\rfloor + \lfloor vn\rfloor$$
for every positive integer $n$?
...

**1**

vote

**1**answer

183 views

### Counting matrices of special types

How many symmetric and non-symmetric $n\times n$ matrices with $0/1$ entries are there such that every row is distinct and every column is distinct? (I am looking for a proof as well).
If only every ...

**5**

votes

**2**answers

270 views

### Four Dimensional Rook Domination

Let $\gamma(G)$ denote the domination number of a graph, and $G\,\square\,H$ denote the cartesian product of two graphs. Then $K_8\,\square\, K_8$ is the rook graph, whose vertices are the squares of ...

**3**

votes

**1**answer

190 views

### Largest symmetric matrix given rank

Let $\mathscr{M}[n,d]$ be collection of $n\times n$ symmetric matrices with real entries from $\{0,1\}$ such that every row/column is distinct with sum of every row/column being $d$.
What is minimum ...

**3**

votes

**1**answer

53 views

### Vanishing Restricted Isometric Constant

In compressed sensing, we are interested in the restricted isometry property. Suppose the design matrix is $n$ by $p$, consisting of $np$ iid $\mathcal{N}(0, 1/n)$ entries. Assume both $n$ and $p$ are ...

**3**

votes

**1**answer

159 views

### higher dimensional analogue of EGZ theorem

The EGZ theorem states that any multiset of $2n-1$ integers has a subset of size $n$ the sum of whose elements is a multiple of $n$.
Kemnitz-Reiher theorem is a 2-dimensional analogue of EGZ. Here is ...

**9**

votes

**0**answers

114 views

### Is there a nice formula for the “non-crossing substitution” of linear combinatorial species?

Background
A linear species is a functor
$$F : \mathrm{Lin} \to \mathrm{FinSet},$$
where $\mathrm{Lin}$ is the category of totally ordered sets and bijections and $\mathrm{FinSet}$ is the category ...

**4**

votes

**0**answers

149 views

### inequality in a shape of inclusion exclusion formula

I have two inequalities to show, both of which describe some probabilities. First I know how to handle, and it follows from applying arithmetic-harmonic mean inequality:
consider 9 numbers ...

**5**

votes

**0**answers

136 views

### Extrapolation between longest increasing and longest alternating subsequences

The question
When should we expect Tracy-Widom?
motivated me to post the following question, in which I have been
interested for a while. Let $f(n)$ be a function from the positive
integers to ...

**4**

votes

**0**answers

110 views

### Generalization of Sprague-Grundy Theorem

In my research on Combinatorial Game Theory, I used a certain theorem that is essentially a generalization of the Sprague-Grundy theorem. Because the result hinges too much on the work of others to be ...

**8**

votes

**3**answers

676 views

### Why does the bitxor function appear in Nim?

I am conducting research in Combinatorial Game Theory (CGT). Although I have done a considerable amount of reading, I do not completely understand why the bit-xor function also known as the nim-sum ...

**0**

votes

**0**answers

62 views

### Minimum rank of certain matrices

Let $\mathscr{M}[n]$ be collection of $n\times n$ matrices with real entries from $\{0,1\}$ such that every row is distinct and every column is distinct.
What is minimum real rank of matrices in ...

**5**

votes

**1**answer

151 views

### partition of a convex set into squares

Let $P$ denote the perimeter function. It's not hard to prove that for any rectangle $R$ in $\mathbb{R}^2$, $R$ can be partitioned into a countable collection of squares $\{Q_k\}_{k=1}^{\infty}$ such ...

**2**

votes

**1**answer

190 views

### Expected value (probability) maximization with binomial distribution

I need to solve an optimization problem that involves an expected value like
$$F(n,x) = \sum_{k=0}^n \binom{n}{k} p^k(1 - p)^{n - k} f(k,x).$$
Here $f(k,x)$ is actually a probability coming from a ...

**0**

votes

**0**answers

73 views

### Classic question on integer partitions (with distinct summands)

I guess that the following was solved sometime in the 18th century, but could not find a reference to it. I am interested in approximations to the following integer partition problem:
Denote $R(N,L)$ ...

**3**

votes

**1**answer

152 views

### Products of relative prime numbers with least sum

Let $P(n)$ be the set of subsets $P$ of $\mathbb{N}$ with the properties
All elements of $P$ are relative prime to each other.
The product of all $k \in P$ is greater or equal to $n$.
Now let ...

**10**

votes

**0**answers

247 views

### Reference request: a combinatoric result [closed]

When I tried to construct a counterexample in my research, I encountered the following result, which should be true.
Let $m=m(n)$ be a function that grows faster than $\sqrt n$, so $m(n) = ...

**0**

votes

**0**answers

87 views

### A sum on a minimums conjecture

Prove or disprove:
$$m(n,k,s)=\sum_{a_1=1}^n \sum_{a_2=1}^n \cdots \sum_{a_k=1}^n \min(a_1, a_2,\cdots, a_k)^s =$$
$$ \sum _{i=0}^{k-1} \frac{(-1)^i}{i!} F(n,i+s) \sum _{j=0}^{k-1} \frac{\partial ...