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.

Filter by
Sorted by
Tagged with
0
votes
0answers
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
2answers
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
2answers
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
0answers
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
0answers
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
3answers
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
2answers
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
0answers
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
2answers
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
1answer
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
2answers
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
1answer
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
3answers
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
2answers
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
2answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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 $...

1
2 3 4 5
159