# 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
Filter by
Sorted by
Tagged with
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}?
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 ...
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 ...
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 ...
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 ...
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$...
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 ...
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 ...
29 views

924 views

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$-...
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$ ...
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....
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 ...
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 ...
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?
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 ...
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$...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
205 views

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