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

7,946
questions

**0**

votes

**0**answers

7 views

### Hi,A question about binomial coefficients

Is there a good lower bound for the tail of sums of binomial coefficients.lower bound for \sum_{i=1}^k {n \choose 2i-1}?

**1**

vote

**0**answers

59 views

### Constructive way to optimally cover a compact subset of Euclidean space

Let, $(X,d)$ be a simply connected compact subset of $\mathbb{R}^d$ with non-empty interiorn, let $d$ denote the Euclidean metric, and let $\varepsilon>0$. Is there a way to iteratively select ...

**1**

vote

**0**answers

69 views

### A query on Galvin's theorem for bipartite graphs

The Galvin's theorem is the generalized version of Dinitz conjecture that states that if the maximum degree of any bipartite graph is $\Delta$, then its edges are colorable properly if each of its ...

**0**

votes

**0**answers

87 views

### Notation for the regular and the adjoint representation of a finite group, in particular the symmetric group

The (left) regular representation of a finite group $G$ is the action on itself by left multiplication, $g\cdot h = gh$.
The adjoint representation of a finite group $G$ is the action on itself by ...

**4**

votes

**2**answers

140 views

### Tree-width of graphs in which any two cycles touch

Let $G$ be a graph s.t. any two cycles $C_1, C_2 \subseteq G$ either have a common vertex or $G$ has an edge joining a vertex in $C_1$ to a vertex of $C_2$. Equivalently: for every cycle $C$ the graph ...

**3**

votes

**1**answer

60 views

### Injective choice function for finite Fano planes

Let $H=(V,E)$ be a hypergraph that is a finite Fano plane, that is, $V$ is a finite set and $E$ has the following properties:
for $e_1\neq e_2\in E$ we have $|e_1|=|e_2|$, as well as $|e_1\cap e_2|=1$...

**2**

votes

**1**answer

128 views

+50

### Combinatorial optimization problem with interdependent constraints on points on a line segment

We are given a set $S$ of $n$ real numbers in $[0,1]$, with $0,1\in S$, and a value $\alpha\in(0,1/2)$. For each ordered triplet $(i,j,k)$ of values contained in $S$ (with $i\le j \le k$), we define ...

**-4**

votes

**0**answers

42 views

### Discrete Math - Modular Equations [closed]

I'm not sure how to go about doing this. There exists an 'x' value between 0 and 21 that satisfies both equations:
x mod 3 = 2
x mod 7 = 4
How do I solve these ...

**0**

votes

**0**answers

29 views

### Closedness of certain functional form; solvability of linear system; equationally compactness

To motivate my question, let $E \subseteq \mathbb{R} \times \mathbb{R}$ be an arbitrary set and suppose that a sequence of bivariate functions $h^{n}: E \to \mathbb{R}$ can be decomposed as $$ h^n (...

**4**

votes

**1**answer

122 views

### Exchanges between independent sets of a matroid

Let $I, J$ be two bases of a matroid. For every $x$ in $I$, there is some $y$ in $J$ such that, if we exchange $x$ with $y$, then both resulting sets ($I \setminus x \cup y$ and $J \setminus y \cup x$)...

**3**

votes

**0**answers

66 views

### Number of cells in array covered by a random permutation

Consider a set $A \subseteq [n] \times [n]$ with $|A| = a = \alpha n$ for some $\alpha \in [0,1]$.
Suppose we select a permutation $\pi \in S_n$ uniformly at random. This permutation $\pi$ can also be ...

**5**

votes

**1**answer

138 views

### Minimum number of independent pairs in a matroid

Given a matroid $M$ with ground set $E$ of size $2n$, suppose there exists $A\subseteq E$ of size $n$ such that both $A$ and $E\setminus A$ are independent. What is the minimum number of $B\subseteq E$...

**4**

votes

**2**answers

189 views

### Combinatorial representation of function

Let $f(x, y, z)$ is the number of distinct ways of representing $x$ as a sum of at most $y$ positive integers that are all smaller or equal to $z$. Moreover, If $yz < x$, then the function gives 0....

**3**

votes

**2**answers

109 views

### Graphs on $\{0,1\}^n$ based on fixed Hamming distance

Let $n$ be a positive integer and consider $\{0,1\}^n$. We define the Hamming distance $d_H(x,y)$ of members $x,y\in\{0,1\}^n$ by $$d_H(x,y)=|\big\{i\in\{0,\ldots,n-1\}:x(i)\neq y(i)\big\}|.$$
For ...

**-1**

votes

**0**answers

189 views

### Disappearing Pigeons [closed]

Suppose you have a magic box that, at random points of time, randomly selects objects within it and makes them disappear. We can assume that before each disappearance the box chooses an object with ...

**2**

votes

**0**answers

77 views

### Lower bound on iterated matrix application

Let $n \in \mathbb Z^2$ such that the non self-adjoint weighted Laplacian is
$$(\Delta u)(n)=u(n_1+1,n_2)-u(n_1-1,n_2) + i( u(n_1,n_2+1)- u(n_1,n_2-1))$$
the adjoint operator is then
$$(\Delta^* u)(n)=...

**11**

votes

**3**answers

924 views

### Integrality of a binomial sum

The following sequence appears to be always an integer, experimentally.
QUESTION. Let $n\in\mathbb{Z}^{+}$. Are these indeed integers?
$$\sum_{k=1}^n\frac{(4k - 1)4^{2k - 1}\binom{2n}n^2}{k^2\binom{...

**3**

votes

**2**answers

144 views

### A “Markov game”

I call games similar to the one I describe below to be Markov games. I am selecting just that one or rather a 1-parameter series of games. The open challenge is to find out which of the players $\ 0\ $...

**2**

votes

**0**answers

66 views

### How to define a function that has these specific properties?

Suppose $x = (x_1,x_2,\dots,x_K) \in \mathbb{Z}^K_{\geq 0}$. For $x,y \in \mathbb{Z}^K_{\geq 0}$, we write $x \succ y$ or $y \prec x$ if $x \neq y$ and
\begin{align*}
x_{i(x,y)} > y_{i(x,y)...

**27**

votes

**2**answers

973 views

### Is being simply connected very rare?

Essentially, my question is how strong a restriction it is to be simply connected.
Here is a way of making this precise: Let's say we want to count simplicial complexes (of dimension 2, though that ...

**2**

votes

**1**answer

132 views

### Generators of sandpile groups of wheel graphs

In the paper "On the Sandpile Group of a Graph" by Cori and Rossin one can find a result related to the structure of the sandpile group of $W_n$. Is there a way to provide a set of ...

**3**

votes

**2**answers

106 views

### When do the circuits of a matroid have a connected intersection graph?

When does a matroid $M$ have a set of circuits $\mathcal{C}$ with a connected intersection graph i.e. when is the graph $G$ with$V(G)=\mathcal{C}$ and adjacencies $\{A,B\}\in E(G)\iff A\cap B\neq\...

**2**

votes

**1**answer

84 views

### Number of 5x5 matrix permutations without repetitions in rows or columns

Context
In the boardgame Azul, your goal is to complete as much as possible of a $5\times5$ board by placing 25 tiles of 5 different colours (5 tiles of each colour) so that no colour appears twice in ...

**24**

votes

**2**answers

1k views

### Function of $(x_1,x_2,x_3,x_4)$ that factors in two ways as $\phi_1 (x_1 ,x_2 )\phi_2(x_3 ,x_4 )=\psi_1 (x_1,x_3)\psi_2(x_2,x_4)$

Suppose we have a function $f(x_1 ,x_2 ,x_3 ,x_4).$ We know that we can factor it in two ways as $f(x_1 ,x_2 ,x_3 ,x_4)=\phi_1 (x_1 ,x_2 )\phi_2(x_3 ,x_4 )=\psi_1 (x_1,x_3)\psi_2(x_2,x_4)$
Show that ...

**3**

votes

**1**answer

175 views

### Sum of product of binomial coefficients

I would like to compute the following sum:
$$
\sum_{k=0, \, k =odd}^{\min\{2n, m\}} {2n \choose 2n-k}{2m-2n \choose m-k}
$$
So far I can prove that
$$
\sum_{k=0, \, k =odd}^m {2n \choose 2n-k}{2m-2n \...

**3**

votes

**1**answer

69 views

### An averaging procedure on finite multisets of $2$-adic integers

Recently there was this question talking about an averaging procedure on finite multisets of integers.
After seeing that question, I thought about the same procedure but with integers replaced by $2$-...

**5**

votes

**0**answers

102 views

### Exponential bound for very weak sunflowers?

Call $r$ sets diverse if for every $0\le i\le r$ there is an element contained in exactly $i$ of them.
A family of sets is r-diverse if any $r$ of its members are diverse.
Is there for every $r\ge 3$ ...

**6**

votes

**0**answers

155 views

### Geometric foundation of the Grothendieck polynomials

Grothendieck polynomials were firstly defined in
Alain Lascoux and Marcel-Paul Sch¨utzenberger. Structure de Hopf de l’anneau de cohomologie et de l’anneau de Grothendieck d’une vari´et´e de drapeaux....

**15**

votes

**3**answers

836 views

### Is matroid realizability computable?

I attended a talk which generalized matroid realizability over a field to matroid realizability over division rings, and showed that the question of realizability is undecidable. However, they used a ...

**3**

votes

**2**answers

178 views

### Planar graph of high valence

A classic result in graph theory tells us that any planar graph must have at least one vertex with valence no bigger than 5. On the other hand, there exist examples of planar graphs that are 5-regular ...

**2**

votes

**1**answer

189 views

### VC dimension of vector spaces

Does the collection of all subspaces of a fixed finite-dimensional vector space have bounded VC dimension?
Could someone please provide references for this question?

**2**

votes

**1**answer

43 views

### Extending spanning sets on contractions of matroids

Suppose you have a matroid, and $T$ is a subset of a spanning set $S$.
Now consider the contraction of the matroid to the set $T$ and suppose $X$ is a spanning subset of $T$ with respect to that ...

**-2**

votes

**1**answer

131 views

### Combinatoric Problem [closed]

Let $2\leq k\leq r\leq n$ are positive integers and $r=kt$.
I construct sets such that $\cup_{i=1}^n A_i=\{1,2,3,\dots,n\}=X$, this union is disjoint and if $x\in A_i$ and $y\in A_j$ for all $i\leq j$...

**10**

votes

**0**answers

173 views

### Does every finite poset have a rigid endomorphism?

Crossposted on Mathematics.
In this post, an order-preserving self-map of a poset $X$ will be called an endomorphism of $X$, and such an endomorphism $f$ will be called rigid if the only automorphism ...

**1**

vote

**1**answer

149 views

### What is the definition of brick product? Graph theory

Can anyone help me with the exact definition of brick product of graphs, say path, cycle.
I am not able to find a paper with a clear definition on the internet. Can anyone give me a URL to such a ...

**-1**

votes

**1**answer

126 views

### What is the most likely sequence? [closed]

I have a jar containing n numbered marbles, where 1...x marbles are red and marbles x+1...n ...

**14**

votes

**1**answer

427 views

### Spanning trees: the last darn $1/4$

Let $\Gamma$ be a connected graph. By (Kleitman-West, 1991),
if every vertex of $\Gamma$ has degree $\geq 3$, then $\Gamma$ has a spanning
tree with $\geq n/4+2$ leaves, where $n$ is the number of ...

**5**

votes

**0**answers

76 views

### Additional examples of classes of networks whose Hasse diagram of the poset is a perfect graph

This question is very important for my research, which is why I ask it here.
I do not have a formal background in graph theory so please excuse me if I state a term incorrectly (and feel free to ...

**1**

vote

**0**answers

57 views

### What can be said about a class of incidence structures closed under duals and complements?

Note that I do not work in combinatorics, and so this question might be a bit naive. The question is inspired by some structures that arise in my research within representation theory.
Recall that an ...

**0**

votes

**0**answers

74 views

### Expected position in random permutation

Let $S$ be a set of $n$ numbers, and $\pi(x):S\rightarrow \left\{ 1,\ldots,n\right\}$ define a permutation. The position $p(x, \pi)$ of an element $x \in S$ in a given permutation $\pi$ is the sum of ...

**3**

votes

**1**answer

84 views

### Transversals and almost transversals of a finite family of sets

The following is a purely combinatorial problem that I came across in the course of research in non-classical logic. It sounds to me like the kind of question that someone may very well have ...

**7**

votes

**2**answers

205 views

### Fixed point for a map from $\{0,1\}^N$ to itself

Let $N\geq2.$ Let $F$ be a function from $\left\{ 0,1\right\} ^{N}$ to itself
dreceasing for the product order defined by $$ (x_1,x_2,\ldots,x_N)\leq (y_1,\ldots,y_N)\ \text{ if and only if for all }...

**10**

votes

**2**answers

130 views

### Maximal in-degree in directed voting graph

Real-life motivation. Our team has $n$ members. For the next in-team presentation session, everyone had 1 talk prepared that he or she would be able to present. Now everyone could cast $1$ vote about ...

**6**

votes

**0**answers

70 views

### When are Hamming codes cyclic?

I've asked this question on math.stackexchange before, but it has not been solved.
The following statement appears to be true:
The $q$-ary Hamming code of codimension $r$ over $\mathbb{F}_q$ is ...

**5**

votes

**0**answers

158 views

### Is there a short proof for the permutation invariance of this combinatorial map?

Consider a positive integer $n$ and integers $(c_i)_{1\le i \le 4}$, with $1 \le c_i \le n$. Conside the map:
$$f_n: (c_1,c_2,c_3,c_4) \mapsto \delta_{c_1,c_2}\delta_{c_3,c_4} - \# \{ |2n+1-2|x||, \ x ...

**0**

votes

**0**answers

31 views

### How is the second smallest eigenvalue of normalized laplacian bounded for random graphs?

It is well known that for any graph G following holds
$\frac{\lambda_2}{2} ≤ \phi(G) ≤ \sqrt{2\lambda_2}$, where $\phi(G)$ is the conductance of the graph and $\lambda_2$ is the second smallest ...

**3**

votes

**0**answers

77 views

### Relation between two conjectures on reconstruction of graphs

In spectral graph theory, there is a conjecture that claims: Almost every graph is determined by its adjacency spectrum ($DS$). This conjecture belongs to professor Willem Haemers.
Also, we have a ...

**4**

votes

**1**answer

391 views

### I want to know the name of or any references for a matrix in the book “The representation theory of the symmetric groups” by Gordon James

$\DeclareMathOperator{\Ind}{\operatorname{Ind}}$I'm reading "The representation theory of the symmetric groups" written by Gordon James.
I found the matrix $B$ in the chapter 6 ("The ...

**4**

votes

**1**answer

263 views

### Minimally separating graphs

We say that a simple, undirected graph $G=(V,E)$ is separating if for all $x\neq y\in V$ there are $e_x,e_y\in E$ such that $x\in e_x$ and $y\in e_y$, and $e_x\cap e_y = \varnothing$. We say $G$ is ...

**4**

votes

**0**answers

93 views

### How does a map from permutahedra to associahedra factor through multiplihedra?

Let $P_i$ denote permutahedra, $K_i$ associahedra and $J_i$ multiplihedra. In their famous paper on operadic diagonals, Saneblidze and Umble use a projection $p_i: P_i \to K_{i+1}$ which factors as $...