**1**

vote

**1**answer

158 views

### How is this combinatorial structure called?

Here is a "colourful" description of what I would like to count. Suppose you have one of those tables you see in a casino. I think they are for roulette, with $m$ squares, each of them with a number ...

**5**

votes

**1**answer

211 views

### “strongly mixing” action on dimers?

In Local Statistics of Lattice Dimers we study a nice familiar object, domino tilings in the plane extending out to infinity.
His paper is going to discuss the frequency of various "motifs" in ...

**8**

votes

**1**answer

157 views

### Spectral lower bounds on the diameter of a graph

There is such a bound, due to Mohar and McKay, using the second-smallest eigenvalue of the Laplacian $\lambda_{2}$:
$$Diam \geq \lceil \frac{4}{n\lambda_{2}} \rceil.$$
This bound is very elegant but ...

**0**

votes

**0**answers

78 views

### Resources about integral maximization problem

I am looking at the following problem. Given an interval I, and a function f over that interval, find sub-intervals for which:
The sum of the length of the sub-intervals is < k;
The sub-intervals ...

**3**

votes

**1**answer

177 views

### Why complete symmetric polynomials and elementary symmetric polynomials are dual to each other?

Here the definition of complete symmetric polynomial $h_{k}$ and elementary symmetric polynomial $e_{k}$ are:
$$
e_{k}=\sum_{1\le i_1<\cdots <i_k\le n}x_{i_1}\cdots x_{i_k}, h_{k}=\sum_{1\le ...

**0**

votes

**1**answer

101 views

### Name search for special Linear Integer Programm

I am looking for a name for the following question in literature!
(and if you know it, then it would be great)
I couldn't find it and due to wide audience here, presumably you know more. Thank you
...

**4**

votes

**3**answers

279 views

### Counting chains of inclusions

Let $g(n,k)$ be the number of chains
$$ A_k \subset A_{k-1} \subset\dots\subset A_1 \subset A_0 $$
of $k$ proper subset inclusions, where $A_k\neq\emptyset$ and $A_0$ is a standard $n$-element set. ...

**2**

votes

**1**answer

162 views

### Combinatorial sum (Author and generalization?)

In a book I have met one interesting equation (without reference):
$$\frac{m!}{n!}\sum_{i=0}^n(-1)^i{n\choose{i}}{x+m+n-i\choose{m}}=\begin{cases}
x+n+1,\, if \,m=n+1
\\
1,\, if \,m=n
\\
...

**2**

votes

**0**answers

48 views

### Generalized separating systems

We call a set system $\mathcal{A}$ of subsets of the $n$ element universe $U$ a separating system if for any pair of elements $x,y \in U$ there is at least one set $A \in \mathcal{A}$ such that either ...

**7**

votes

**1**answer

458 views

### How to determine if there exists a non-zero vector in the kernel

If you are given a $0$-$1$ circulant matrix with $n$ rows and $n$ columns, is there an efficient way of determining if there exists a non-zero $\{-1,0,1\}$-vector in its kernel?
Could this problem ...

**0**

votes

**0**answers

89 views

### topological space of Wang Tile

When trying to reprove a theorem in Wang tile:
An established proof in Wang Tile which I doubt
, a few notions are provided which I would like to seek for more information:
For a given set of blocks ...

**3**

votes

**3**answers

171 views

### Time-inhomogeneous Markov Chains

I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...

**5**

votes

**1**answer

145 views

### Can I weaken the minimum degree hypothesis in Nash-Williams' triangle decomposition conjecture?

In what follows, all graphs $G$ are $K_3$-divisible (all degrees even, number of edges a multiple of three) on $n$ vertices, where $n$ is not too small.
The famous Nash-Williams conjecture claims ...

**3**

votes

**3**answers

730 views

### An established proof in Wang Tile which I doubt

When I was reading the paper:
Wang, Hao. "Notes on a class of tiling problems." Fundamenta Mathematicae 82.4 (1975): 295-305.
from http://matwbn.icm.edu.pl/ksiazki/fm/fm82/fm82119.pdf
I could not ...

**4**

votes

**2**answers

217 views

### Equality-preserving embeddings of finite trees

For finite trees $T_{1}$ and $T_{2}$ labelled by elements of some infinite set $S$, (we may assume that $S=\mathbb{N}$ without loss of generality), we define an equality-preserving embedding $f$ to be ...

**8**

votes

**5**answers

975 views

### Are all almost regular graphs obvious?

Let the maximum and minimum degress of a graph be denoted (as usual) by $\Delta$ and $\delta$ respectively.
A graph is almost regular if $\Delta-\delta=1$.
Now, here is a simple way to generate ...

**4**

votes

**1**answer

203 views

### Circulant matrix with integer entries and determinant 1 or -1

CONJECTURE
Let $A= (c_0,c_1,\ldots,c_n)$ be a circulant matrix, i.e if $(c_0,c_1,\ldots,c_n)$ is the first column of $A$ then the $i$th column of $A$ is obtained by applying the permutation ...

**1**

vote

**0**answers

189 views

### Enumerating certain types of permutation polynomials

Given a prime power $q$, I would like to enumerate (preferably up to isomorphism*) all the permutation polynomials $f(x)$ on $K = GF(q^3)$ satisfying the following conditions:
$f(ax) = af(x)$ for ...

**3**

votes

**1**answer

98 views

### Results where complexity bounds implies finite number of test cases

We have all been there, when a formula works for the first 30 parameters,
but it is not sufficient for a proof. My question is where one can actually just check a finite number of cases, to conclude ...

**2**

votes

**3**answers

166 views

### branching schubert calculus

Let $X=Gr(r,V), Y=Gr(r+1,W)$ where $V,W$ are complex vector spaces with $\dim V > r$ and $\dim W > \dim V$. Let $\phi:X\rightarrow Y$ be some embedding of varieties. This induces a morphism on ...

**10**

votes

**1**answer

642 views

### Two to the power of a triangular number: bijections

The numbers $2^{n(n+1)/2}$ come up in various enumerative contexts. In addition to the trivial example (bit-strings of length $n(n+1)/2$) and the old example of domino tilings of Aztec diamonds ...

**5**

votes

**0**answers

93 views

### Monotone embedding of complete binary tree in hypercube

Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...

**7**

votes

**0**answers

170 views

### A strong sum-product “for translates” in finite fields

In the course of some recent research, I've sketched out a proof of the following result. My basis question is: is the result interesting?
Proposition There exists an absolute constant $c$ such ...

**1**

vote

**0**answers

128 views

### Placing numbers $1,2,\ldots,n^2$ in a square so that numbers of any two adjacent unit subcube are coprime

It is proved HERE that there is a natural number $N$ such that for any $n > N$ it is possible to place numbers $1,2,\cdots, n^2$ is an $n\times n$ square such that the numbers in any two adjacent ...

**1**

vote

**0**answers

54 views

### Building set of n-bit numbers that have m bits are set and any two numbers in this set have distance 1

I want to build numbers set(one of possible) that meet following criteria
We are given n-bit numbers.
Select subset(X) of them that have exactly m bits set to 1.
Then I need to build subset(Y) of ...

**5**

votes

**0**answers

144 views

### Are the roots of chromatic polynomials plus a fixed constant dense in $\mathbb{C}$?

Alan Sokal proved that chromatic roots are dense in the whole complex plane. I.e., if $P(G;z)$ denotes the chromatic polynomial of a finite simple graph $G$ evaluated at $z \in \mathbb{C}$, then ...

**2**

votes

**3**answers

153 views

### Examples of graph properties characterized by forbidden (not necessarily induced) subgraphs

A graph property is hereditary if it is closed under taking induced subgraphs (equivalently, if it is closed under removing vertices). A graph property is monotone if it is closed under taking ...

**4**

votes

**1**answer

216 views

### Examples of specializations of elementary symmetric polynomials

Let $\mathcal{S}_{x}=\{x_{1,},x_{2},\ldots x_{n}\}$ be a set of $n$
indeterminates. The $h^{th}$elementary symmetric polynomial is the
sum of all monomials with $h$ factors
\begin{eqnarray*}
...

**7**

votes

**1**answer

172 views

### Status of Barany's conjecture?

One of Barany's most intriguing conjectures is about the $f$-vectors of convex polytopes. It asks:
Let $P$ be a convex $d$-polytope. Is it always true that $f_k \geq \min(f_0, f_{d-1})$?
A ...

**4**

votes

**3**answers

569 views

### Analogy between Integers and Permutations

I am reading Andrew Granville's Anatomy of Integers and Permutations where it is argued the factorization of a permutation into disjoint cycles is analogous to the factorization of a number into prime ...

**1**

vote

**1**answer

97 views

### Constructive ideas behind “covering” a set with subsets of fixed size

The question is the following: how many subsets of size $5$ from a set $A$ of size $16$ do we need so that any subset of size 2 of $A$ is also a subset of one of the selected subsets of size $5$?
How ...

**1**

vote

**0**answers

62 views

### labeling vertices in a graph to minimize distance between adjacent vertices

We have a regular graph $G$ of degree $m$ on $n$ vertices and we label each of its vertices with the number $1$ through $n$. What can we say about the maximum difference between the numbers of two ...

**6**

votes

**1**answer

274 views

### Is there a name for infinite words containing every finite words?

Apparently, the closest thing I've found would be normal number http://mathworld.wolfram.com/NormalNumber.html
But requiring that every finite words occurs is weaker than this property. So I'm ...

**4**

votes

**3**answers

329 views

### Combinatorial counting with symmetry

Let $A$ be a set of objects where $|A|=n$. We want to count all the possible ways that we can arrange these objects into $n$ bags with exactly $n$ objects in each. We can reuse any object, however, no ...

**6**

votes

**3**answers

670 views

### Combinatorial identity involving the square of $\binom{2n}{n}$

Is there any closed formula for
$$
\sum_{k=0}^n\frac{\binom{2k}{k}^2}{2^{4k}}
$$
?
This sum of is made out of the square of terms $a_{k}:=\frac{\binom{2k}{k}}{2^{2k}}$
I have been trying to verify ...

**6**

votes

**1**answer

347 views

### Paths in groups

Given a finite group $G$, write $K(G)$ for the complete digraph on the elements of $G$. Label the edge from $g$ to $h$ by element $g^{-1}h$.
Question: For what groups does there exist a Hamiltonian ...

**1**

vote

**1**answer

120 views

### Sequences that represent different drawing of chords?

In combinatorics there are there are special kind of sequences, in which their terms represent the number of different ways that we can draw chords with some properties.
Actually my question is ...

**2**

votes

**1**answer

89 views

### Integrally closed polytopes from 01-matrices

Let $A$ be a matrix with entries either 0 or 1, where each column contains at least one 1, to remove trivial degenerations.
Let $P$ be the convex hull of all integer vectors $x$ that satisfy $Ax \leq ...

**7**

votes

**0**answers

221 views

### diameter as a Morse function

Consider the space $X_1$ of closed subsets not containing a pair of antipodal points of the unit circle. Here we have a kind of degenerate Morse function, defined by the diameter of the pointset. ...

**5**

votes

**1**answer

280 views

### A result from Peter McMullen's thesis

The classical definition of regular polytopes is recursive. It says that a polytope is regular if its facets and vertex figures (both smaller-dimensional polytopes) are regular.
The modern definition ...

**16**

votes

**0**answers

146 views

### A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph?
I'd like to avoid exhaustive ...

**0**

votes

**0**answers

85 views

### Estimating when does a certain binomial sum exceed an upper bound

Given a fixed integer $n > 0$ and $0 \le m \le n$ let us define the numbers
$$f_{n,m} = \sum_{i=\lfloor m/2 \rfloor}^m {n-2i \choose n - m -i}{i+1 \choose m - i +1}.$$
For example $f_{n,0} = ...

**1**

vote

**1**answer

106 views

### Formula for the Ordinal Number of k-Sets of Positive Integers

Background of my question is, that I would like to store flags indicating the relation between a pairs of non-adjacent edges of a graph (that relation could for example be, whether the edges cross, ...

**0**

votes

**0**answers

115 views

### Non existence (or existence) of a set that is equidistributed modulo $q$ for every $q$

I have been thinking about some set that is equidistributed modulo $q$,
uniformly in $q$ in some sense. I was starting to think this particular condition, which I describe below, is too strong and ...

**0**

votes

**1**answer

75 views

### Generalized Helly theorem for $t$-intersecting families

Given a family $\mathcal{F}$ of sets over ground set $X$, let $\tau(\mathcal{F})$ be the transversal number (aka blocking number), that is the cardinality of the smallest set of points $E \subseteq X$ ...

**4**

votes

**3**answers

225 views

### Number of binary vectors of a given Hamming weight in a subspace of the Hypercube

Let $n$ be a natural number.
Let $U \subseteq \mathbb{F}_2^n$ be a linear subspace of dimension $k$.
What is the maximum number of vectors in $U$ of Hamming weight $\ell$?
The case I am specifically ...

**1**

vote

**0**answers

68 views

### Inverse of matrix of generalised harmonic numbers

For $s=0,1,\dots$ and $n=1,2,\dots$, denote $r_{n,s}=\sum_{k=1}^n k^s$. It is well-known that $r_{n,s}$ are polynomials in $n$ with leading term $\frac{1}{s+1}n^{s+1}$. Let $R_{n,s}$ be the ...

**4**

votes

**0**answers

87 views

### A question on hyperplanes in partial linear spaces and hypergraphs

A partial linear space (or a linear hypergraph) is a point line geometry $(P,L,I)$ where for every pair of points there is at most one line incident with both of them. A hyperplane in a partial linear ...

**6**

votes

**5**answers

564 views

### What makes a set random?

There are many results in number theory, where the existence
of some $B \subseteq \mathbb{N}$ with certain properties is proved by
a probabilistic argument employing "random sets". One such example
...

**3**

votes

**0**answers

67 views

### Orthogonal basis for the multilinear polynomials with zero “trace”

We say that a multilinear polynomial $P(x_1,\ldots,x_n)$ in $n$ commuting variables over $\mathbb{R}$ has zero trace if
$$ \frac{d}{dt} P(t,\ldots,t) = 0. $$
Equivalently,
$$ \left(\sum_{i=1}^n ...