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

**1**

vote

**3**answers

89 views

### Bijective operations on finite simple graphs

Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.
I am interested in specific bijective maps $\mathcal G_n\to\mathcal G_n$, defined for all $n$. An ...

**24**

votes

**3**answers

751 views

### Is the Ford-Fulkerson algorithm a tropical rational function?

The Ford-Fulkerson algorithm
Let me recall the standard scenario of flow optimization (for integer flows at least):
Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Consider a digraph $D$ with vertex ...

**0**

votes

**0**answers

41 views

### Sum of Binomial Coefficients from 1 to N having specific form [on hold]

In this question I want to know how we can find the sum of the series if N = 2*I
like 2C1 + 4C2 + 6C3 + …. upto N terms.
[Sum of 'the first k' binomial coefficients for fixed n

**6**

votes

**4**answers

3k views

### Maximum determinant of $\{0,1\}$-valued $n\times n$-matrices

What's the maximum determinant of $\{0,1\}$ matrices in $M(n,\mathbb{R})$?
If there's no exact formula what are the nearest upper and lower bounds do you know?

**7**

votes

**3**answers

933 views

### Transforming a binary matrix into triangular form using permutation matrices

I am interested in the complexity of the following problem:
Given an $m\times n$ binary matrix $M$, can we permute its rows/columns to obtain a triangular matrix?
I am also interested in ...

**-4**

votes

**1**answer

56 views

### Regular graph such that $2$ distinct vertices have same neighborhood set [on hold]

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

**11**

votes

**1**answer

492 views

### Frankl's conjecture restricted to finite topological spaces

A finite topological space is a finite family of finite sets that is closed under both union and intersection.
Frankl's conjecture states that for any finite union-closed family of finite sets, ...

**0**

votes

**0**answers

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

**45**

votes

**4**answers

3k views

### Difficult examples for Frankl's union-closed conjecture

Frankl's well-known union-closed conjecture states that if F is a finite family of sets that is closed under taking unions (that is, if A and B belong to the family then so does $A\cup B$), then there ...

**13**

votes

**6**answers

3k views

### analog of principle of inclusion-exclusion

When I teach elementary probability to my finite math students, a common error is to mix up the concepts of disjointness and independence. At some point I thought that it might be helpful to some ...

**-2**

votes

**0**answers

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

**2**

votes

**2**answers

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

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

**8**

votes

**6**answers

1k views

### Proof of a combinatorial equation

How can we use elementary methods to prove that
$$\sum_{i = 2}^{n}{{n \choose i} i! n^{n - i}} = \sum_{i = 1}^{n - 1}{{n \choose i}i^i (n - i)^{n - i}}$$
for any integer $n \geq 0$?
The values of ...

**8**

votes

**0**answers

201 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

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

**20**

votes

**2**answers

2k views

### A Putnam problem with a twist

This question is motivated by one of the problem set from this year's Putnam Examination. That is,
Problem. Let $S_1, S_2, \dots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\dots,n\}$ in some ...

**11**

votes

**1**answer

281 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

**1**answer

138 views

### On $\det[x+(\frac{i\pm j}p)]_{1\le i,j\le(p-1)/2}$ for primes $p\equiv 3\pmod 4$

I have made the followng conjecture on the basis of my computation.
Conjecture. For any prime $p\equiv3\pmod4$ with $p>3$, we have
$$\det\left[x+\left(\frac{i+j}p\right)\right]_{1\le i,j\le(p-1)/2}...

**3**

votes

**0**answers

49 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

89 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

111 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

107 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

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

**15**

votes

**1**answer

277 views

### Chromatic numbers of infinite abelian Cayley graphs

The recent striking progress on the chromatic number of the plane by de Grey arises from the interesting fact that certain Cayley graphs have large chromatic number; namely, the graph whose vertices ...

**5**

votes

**1**answer

104 views

### An extension of the Izergin-Korepin determinant to the eight-vertex model

In the six-vertex model, edges in a square lattice are oriented so that the in-degree of each vertex is exactly two. This gives six types of allowable vertices:
$$\begin{array}{cccccc}
\begin{...

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

**18**

votes

**1**answer

484 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)$ ...

**6**

votes

**2**answers

108 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)$ ...

**2**

votes

**0**answers

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

**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

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?

**14**

votes

**1**answer

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

**5**

votes

**1**answer

210 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\{...

**0**

votes

**1**answer

82 views

### Finding $P$ points among $N$ to approximate a probability density function?

Let $f$ be a probability density function (positive such that $\int_{\mathbb{R}} f(x) \mathrm{d} x = 1$) and $X_0 = \{x_n\}_{1\leq n \leq N}$ be $N$ given real points. We also fix $1 \leq P \leq N$ ...

**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 $\...

**6**

votes

**2**answers

301 views

### How hard is it to compute the diameter and the growth function of a finite permutation group of small degree?

Let $G \leq {\rm S}_n$ be a finite permutation group, and let
$S = \{g_1, \dots, g_k\}$ be a generating set for $G$ which is closed
under inversion and which does not contain the identity.
The growth ...

**0**

votes

**0**answers

104 views

### Probability of degree $0$ gcd between every pair of random homogeneous polynomials shifted by random primes?

Take $n,d,B\in\mathbb Z_{>0}$ with $d<n$ and denote $\mathcal M_{n,d}$ to be set of all total degree $d$ monomials in $n$ variables $x_1,\dots,x_n$ with degree $\leq1$ in each variable (...

**46**

votes

**6**answers

5k views

### Is there an “elegant” non-recursive formula for these coefficients? Also, how can one get proofs of these patterns?

Not sure if this is a "good" question for this forum or if it'll get panned, but here goes anyway...
Consider this problem. I've been trying to find a formula to expand the "regular iteration" of "...

**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

**1**answer

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

**3**

votes

**1**answer

312 views

### Generating Uniquely k-Optimal Point Sets

This question is motivated by the observation that finding an optimal tour through a set of points in the Euclidean plane is especially simple, if the points are in convex configuration and, that the ...

**1**

vote

**1**answer

66 views

### Random Optimization on Graphs: Minimum Cut

Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) ...

**5**

votes

**1**answer

233 views

### Finding a semi-sparse vertex in a grid

Let $H$ be a $r \times r$ grid. Suppose that at most $r/10^5$ vertices of this grid are colored red. For every vertex $v \in V(H)$, let $B_i(v)$ be the ball of radius $i$ centered at $v$. (Or for ...

**3**

votes

**1**answer

324 views

### Typo in Soundararajan's *Bulletin of the AMS* article on Tao's resolution of The Erdos Discrepancy Problem?

I think that there is a typo in the paper referred to in the title of the question, available here. While discussing Roth's proof of AP discrepancy, on page 2, the author states that
Roth [20] ...

**4**

votes

**1**answer

185 views

### Distribution of longest run locations in a random string

Let x be a random n-bit string, and let $I ={i_1,i_2,...,i_n}$ be the starting indexes of the longest 0-runs of x, sorted in decreasing order (so $i_1$ is the starting index of the longest (~$\log n$) ...

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

**5**

votes

**1**answer

495 views

### What is the six positive real number for a dice producing a highest chance?

Say there is a dice with six faces, each face has a positive real number different from others. There is a chessman on the origin of the number axis. In each trial, the dice rolls infinite times. ...

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