# Questions tagged [co.combinatorics]

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

**-4**

votes

**1**answer

41 views

### Regular graph such that $2$ distinct vertices have same neighborhood set

If $G=(V,E)$ is a simple, undirected graph and $v\in V$, we set $N(v) = \{w\in V:\{v,w\}\in E\}$.
Is there an integer $k>1$ and a connected $k$-regular graph $G=(V,E)$ such that there are $v\neq ...

**-2**

votes

**0**answers

53 views

### Birthday Calendar Gaps [on hold]

I work at a company that posts a birthday calendar. I noticed that there was a string of four consecutive days with no birthdays. What is the probability of that happening?
Problem Statement
Given n ...

**0**

votes

**0**answers

113 views

### Total number of collisions

Given $n$ point masses on the real axis with their initial positions and velocities, determine the total number of collisions (from $t=0$ to $t=\infty$). Here I suppose that the collisions are elastic,...

**0**

votes

**0**answers

36 views

### Average distance between a random point and the closest of a set of random points

Create a set of n randomly placed points in a unit square. Then create another random point in the unit square. What is the average distance between this point and the closest of the n points?

**2**

votes

**2**answers

115 views

### Infima and suprema in the “transfer” function ordering

Let $X,Y$ be sets, $f, g:X\to Y$ be functions. We say $u:Y\to Y$ is a transfer function for $g$ to $f$ if $$f = u \circ g.$$ In that case we write $f \leq_t g$. Let $\mathrm{Fct}(X,Y)$ denote the ...

**3**

votes

**0**answers

118 views

### Combinatorics question

Let $A = (a_{ij})_{1\le i,j\le h}$ be an $h$-by-$h$ non-degenerate upper triangular matrix with entry $a_{11} = 1$. Let $\Phi = \{\alpha_1,\alpha_2,\ldots,\alpha_d\}\subseteq \{1,2,\ldots,h\}=I$ be an ...

**0**

votes

**0**answers

74 views

### How to prove the exact top degree of the polynomial coming from each Feynman diagram?

Let $W=x_0+x_1+x_2+\lambda_0 \ln(x_0)+\lambda_1\ln(x_1)+\lambda_2\ln(x_2)+(\frac{x_0x_1x_2}{q})^{\frac{1}{3}}$, where $\lambda_i=\xi^i\cdot\lambda$, $\xi$ is the 3-th root of unit. For each Feynman ...

**8**

votes

**0**answers

194 views

### Commuting matrix variety $[A,B]=0$ - can one geometrically explain divisibility of $F_ q$ point count by high powers of $q$?

$\DeclareMathOperator\Comm{Comm}\DeclareMathOperator\Id{Id}$Consider the variety $\Comm$ of commuting matrices $[A,B]=0$ over some field $K$. It is much studied, and interesting for various reasons.
...

**3**

votes

**0**answers

48 views

### Biggest Cartesian Product Included in a Real Plane Curve

Suppose an irreducible smooth $p \in \mathbb{R}[x_1,x_2]$ is given, and we would like to find finite sets $S_1 , S_2 \subset \mathbb{R}$ such that $p(S_1 \times S_2)=0$ and $|S_1 \times S_2|$ is as ...

**1**

vote

**1**answer

88 views

### Incidences between points and circles in the plane

Suppose we have $n$ points $P$ and $m$ circles $C$ in the plane. Let $I(P,C)=\{(p,c), p \in P, c \in C, p \in c\}.$ Then what do we know about
$\max_{m,n} |I(P,C)|$?
Any references?

**4**

votes

**2**answers

109 views

### Are cyclic codes bounded by a continuous function?

In coding theory, we know that if you take the function
\begin{equation}
\alpha_q(\delta) := \limsup_{n \rightarrow \infty} \ \max \{ R(C) \mid \delta(C) \ge \delta \mid C \subseteq \mathbb{F}_q^...

**-1**

votes

**1**answer

104 views

### Version of Hall's marriage theorem in arbitrary finite graphs [closed]

Let $G=(V,E)$ be a finite, simple, undirected graph such that $\bigcup E = V$ (that is, every vertex belongs to at least one edge).
For $v\in V$ we set $N(v) = \{w\in V:\{v,w\}\in E\}$, and for $S\...

**2**

votes

**0**answers

109 views

### Metrics on finite groups and generalizations of central limit theorems for balls volumes (à la Diaconis-Graham)

In wonderful lectures by P. Diaconis "Group representations in probability and statistics, Chapter 6. Metrics on Groups, and Their Statistical Use" metrics on permutation groups are considered and ...

**3**

votes

**0**answers

117 views

### Maximum number of integral roots in degree $d$ polynomial?

Given $f(x_1,\dots,x_n)\in\mathbb Z[x_1,\dots,x_n]$ such that
Each coefficient is bound in absolute value by $B$
Degree of each variable in any monomial is bound by $d$
Total degree is $d'$
$f(x_1,\...

**2**

votes

**0**answers

99 views

### On an exercise in The Probabilistic Method : random dilate of a set in a finite field

This is related to Problem $4.6$ in ``The Probabilistic Method'' by Alon and Spencer, where one essentially has to prove the following:
Let $p$ be a prime, and $A$ be any subset of $\mathbb{F}_p$. ...

**5**

votes

**2**answers

141 views

### Enumeration of lattice paths of a specific type

One of the approaches to "Special" meanders led (in particular) to the following question:
What is the number $a_{m,n}(\ell)$ of $\ell$-step paths from $(1,1)$ to $(m,n)$ using the ...

**6**

votes

**2**answers

106 views

### Neighboring number of a permutation

For any positive integer $n\in\mathbb{N}$ let $S_n$ denote the set of all bijective maps $\pi:\{1,\ldots,n\}\to\{1,\ldots,n\}$. For $n>1$ and $\pi\in S_n$ define the neighboring number $N_n(\pi)$ ...

**18**

votes

**1**answer

481 views

### Order of Conway's “look and say” recurrence

Let $L_n$ be the length of the $n$th term of Conway's "look and say"
sequence (https://oeis.org/A005341). The generating function $F(x)=
\sum_{n\geq 0}L_nx^n$ is a rational function, say $P(x)/Q(x)$ ...

**2**

votes

**0**answers

118 views

### What kind of curve is this, from the distribution of roots of Catalan polynomials? [closed]

We consider the distribution of roots of some Catalan polynomials.
And we get the following curve that the roots approach it.
What kind of curve is this?

**5**

votes

**1**answer

208 views

### On the “infinitely often in” relation between subsets of $\mathbb{N}$

Let ${\mathbb N}$ denote the set of positive integers, let $A,B\subseteq \mathbb{N}$. For $n\in\mathbb{N}$ we set $n+A:=\{n+a: a\in A\}$. We say that $A$ is infinitely often in $B$ if the set $$\big\{...

**3**

votes

**1**answer

109 views

### Expected size of the smallest preimage set

Let $f$ a function from $\{0, 1 \}^{2n}$ to $\{0, 1 \}^{n}$ uniformly picked at random. I would like to have an estimation of the expected size of the smallest premiage set of $f$, more formally $\...

**2**

votes

**0**answers

51 views

### Total Coloring Conjecture for Cayley Graphs

The total Coloring Conjecture(TCC) states that any total coloring of a simple graph $G(V,E)$ has its total chromatic number bounded as $\chi^{T}(G)\le \Delta+2$ where $\Delta $ is the maximal degree ...

**2**

votes

**0**answers

58 views

### Algebraic description of the reduced incidence algebra of a poset

In the book "Combinatorial theory" by Martin Aigner (from 1979), the standard algebra of a poset is introduced as the subalgebra of the incidence algebra of a poset consisting of the functions that ...

**2**

votes

**1**answer

110 views

### Does the likelihood of these tables exist?

Probably it does, and may be a number near $e^{-3/2}$ for 2-deficient tables. First some background.
Early on in my studies of universal algebra, I encountered a result of Vadim Murskii, with the ...

**14**

votes

**1**answer

617 views

### Combinatorial inequality for dominant dimension

In the following I present a conjecture on Nakayama algebras that I have for nearly 2 years now. Since I was not able to solve it and it can be stated purely combinatorically, I thought it might be ...

**7**

votes

**0**answers

83 views

### Permutation groups with diameter $O(n \log n)$

I suspect that many permutation puzzles can be solved in $O(n \log n)$ moves, which has led me to the following question/conjecture:
Suppose that
1. $P_i$ for $i<k=O(1)$ are permutations on an $n$ ...

**1**

vote

**0**answers

36 views

### Examples of associative inducers and other inducers

I am curious about how well the following technique can produce algebraic structures and semigroups in particular.
Let $(X,\circ)$ be a semigroup. Let $Y$ be a set and let $L:X\rightarrow P(Y)$ be a ...

**4**

votes

**1**answer

95 views

### Hamming representability of finite graphs

This is a follow up on an older question.
We construct graph on the vertex set $\{0,1\}^n$ where $n$ is a positive integer. For $x,y \in \{0,1\}^n$ the Hamming distance of $x,y$ is the cardinality of ...

**0**

votes

**1**answer

102 views

### Conjecture on representing graphs within $\{0,1\}^n$

We construct graph on the vertex set $\{0,1\}^n$ where $n$ is a positive integer. For $x,y \in \{0,1\}^n$ the Hamming distance of $x,y$ is the cardinality of the set $\{ i \in \{0, ..., n-1\} : x(i) \...

**2**

votes

**1**answer

99 views

### How to uniformly sample a square (0,1)-matrix whose trace is 0 and whose row sums and column sums are the same?

Happy New Year!
Suppose I would like to sample a $n \times n$ (0,1)-matrix whose trace is 0, and whose row sums and column sums are all $m$ with $1 \le m \le n-1.$ How can I sample this matrix ...

**11**

votes

**1**answer

276 views

### To find a longer path with fixed endvertices in a graph satisfies the following property

Suppose that $G=(V,E)$ is a simple graph and $P=(V_1,E_1)$ is a path in $G$ where
$$V_1=\{v_0,v_1,\cdots,v_n\},\ E_1=\{v_0v_1,v_1v_2,\cdots,v_{n-1}v_n\}.$$
I found that if the path $P$ satisfies:
...

**1**

vote

**0**answers

119 views

### How often do random games of go end in illegal moves?

Suppose that moves are generated from two players in accordance with three rules: each move is chosen uniformly at random among places on the board ($19 \times 19$, $9 \times 9$, or $k \times k$ with ...

**4**

votes

**2**answers

179 views

### How many ways to fill in a square grid with certain restrictions

Suppose I have a 5x5 grid of squares. I would like to fill in 15 checkmarks in the squares such that (1) each of the 25 square cells contains at most one checkmark, (2) each row has exactly 3 ...

**0**

votes

**4**answers

317 views

### How to compute this series: $\sum_{k=0}^\infty \frac{C_k}{2^{2k+1}}$ [closed]

How to compute this series: $$\sum_{k=0}^\infty \frac{C_k}{2^{2k+1}}$$ where $C_k$ is the catalan number: $C_k=\frac{1}{k+1}{2k \choose k}$. (Further, is there any general method to treat this ...

**1**

vote

**1**answer

59 views

### Enumerating isomorphic subgraphs

For digraphs $G$ and $H$ if we can partition $V(G)$ into a family $\{Q_t\}_{t\in V(H)}$ indexed by $V(H)$ such that $E(G)=\bigcup_{(u,v)\in E(H)}Q_u\times Q_v$, then is every subgraph of $G$ ...

**4**

votes

**1**answer

297 views

### Spreading $n$ points in $\{0,1\}^n$ as far as possible

Given a positive integer $n$, the Hamming distance $d^H_n(x,y)$ of $x,y\in \{0,1\}^n$ is defined by $$d^H_n(x,y) = |\{k\in\{0,\ldots,n-1\}: x(k)\neq y(k)\}|.$$
We say that a positive integer $s$ is $...

**5**

votes

**1**answer

191 views

### Inequality number of facets simplicial complex

In a recent preprint, Adiprasito proves that if $\Delta$ is a simplicial complex of dimension $d$ that can be embdedded in a $2d$-dimensional homology sphere (say $\Sigma$) that satisfies a version of ...

**6**

votes

**0**answers

203 views

### Is the permanent of the matrix $[(\frac{i+j}{2n+1})]_{0\le i,j\le n}$ always positive?

Recall that the permanent of an $n\times n$ matrix $A=[a_{i,j}]_{1\le i,j\le n}$ is defined by
$$\operatorname{per}A=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.$$
In 2004, R. Chapman [Acta ...

**0**

votes

**1**answer

71 views

### Finding a good transversal basis

A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such ...

**5**

votes

**2**answers

283 views

### The number of Dyck paths of length $2n$ and height exactly $k$

In A080936 gives the number of Dyck paths of length $2n$ and height exactly $k$ and has a little more information on the generating functions.
For all $n\geq 1$ and $\frac{(n+1)}{2}\leq k\leq n$ we ...

**1**

vote

**1**answer

97 views

### On a theorem of Chetwynd and Hilton in Graphs

Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...

**1**

vote

**0**answers

91 views

### Has the “semidirect monoid of a semiring” been considered anywhere?

Given a semiring $S$, we get a monoid $M(S)$ as follows:
The underlying set of $S$ is $S^2$
The identity element is $(0,1)$
The law of composition is given by $$(a,A)(b,B) = (Ba+b,AB),$$ where $a,A,b$...

**1**

vote

**0**answers

86 views

### extending a partition of a number to get new partition

Let $\lambda = (k_1^{m_1}\,k_2^{m_2})$ where $0<k_1<k_2$ be a partition of $n$ in the power notation.
Let $\mu = p_0^{r_0}\,p_1^{r_1}\,\cdots\, p_t^{r_t} \,(k_1^{m_1}\,k_2^{m_2})\,q_0^{s_0}\,...

**-2**

votes

**1**answer

216 views

### Negative Dirichlet Pigeonhole Principle

From Dirichlet Pigeonhole Principle if $p$ is a prime and if $a,b\in\mathbb Z$ are in $(0,p/2)$ then there is a $t\in(0,p)\cap\mathbb Z$ such that $\|(x,y)\|_\infty<\lceil\sqrt p\rceil$ holds where ...

**2**

votes

**1**answer

252 views

### Homogeneous van der Waerden

The Erdős Discrepancy Problem is whether in any two-coloring of the naturals for any $C$ there is a sequence $d, 2d, \ldots nd$ such that the difference of red and blue numbers in it is more than $C$.
...

**1**

vote

**2**answers

250 views

### Prove that there exists a nonempty subset $ I$ of $ \{1,2,…,n\}$ such that $ \sum_{i\in I}{\frac {1}{b_i}}$ is an integer

Let $ a_1,a_2,...,a_n$ and $ b_1,b_2,...,b_n$ be positive integers such that any integer $ x$ satisfies at least one congruence $ x\equiv a_i\pmod {b_i}$ for some $ i$. Prove that there exists a ...

**4**

votes

**1**answer

211 views

### Applications of De-Bruijn Sequences in “Pure Mathematics”

I know of a few applications of De-Bruijn Sequences and De Bruijn Graphs in combinatorics, applied mathematics, Engineering and computer science. But I have only found one application of De Bruijn ...

**8**

votes

**1**answer

153 views

### On the existence of a particular type of finite measure on $\mathbb N$

Let $\mathbb N$ denote the set of all positive integers. Does there exist a countably additive measure $\mu : \mathcal P(\mathbb N) \to [0,\infty)$ such that $\mu(\mathbb N)<\infty$ and $\mu(\{nk: ...

**0**

votes

**0**answers

46 views

### Polynomial time way of testing optimality of given vertex for linear programming

Is there a fast way (polynomial complexity) of testing whether a given vertex for a linear program is optimal, without assuming non-degeneracy?
I can find the optimal vertex in worst-case polynomial ...

**2**

votes

**1**answer

58 views

### Stretching map of $n$ points from $\{0,1\}^n$ to $\{0,1\}^{n+1}$ with respect to their Hamming distance

Given a positive integer $n$, the Hamming distance $d^H_n(x,y)$ of $x,y\in \{0,1\}^n$ is defined by $$d^H_n(x,y) = |\{k\in\{0,\ldots,n-1\}: x(k)\neq y(k)\}|.$$
Given an integer $n>0$ and a set $S\...