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

10,166 questions
Filter by
Sorted by
Tagged with
70 views

### How to write down the contrapositive of a statement and prove if it's right or not [closed]

I have been battling with my professor over this question for months. Every time I come up with an answer she tells me wrong. Question: Consider the following proposition concerning an integer n ≥ 2. ...
• 1
1 vote
57 views

### Hardness of a Hybrid problem combining knapsack and scheduling

I am trying to prove whether the following problem is NP-hard or not: Items with a certain length arrive in a fixed sequence and must be assigned to one of two containers which are constrained in ...
23 views

### How many strings of octal numbers of length n are “good”? [closed]

A string of octal numbers of length n is called “good” if k=n(0)+n(7) and l=n(3)+n(4) are odd numbers, where n(i), i=0, 1, …, 7, represents the number of i’s found in the string. How many strings of ...
222 views

### Maximal set of $n$-bits that does not span $\mathbb{R}^n$

I am trying to find out the maximum-sized subset $S\subseteq \{0,1\}^n$ of $n$-bit strings that does not span $\mathbb{R}^n$. It is easy to show that $S$ has size at least $2^{n-1}$ when $S$ exactly ...
348 views

### Inequality of inclusion-exclusion term

This question was initially posted on math.stackexchange.com but did not receive any answers for half a week. While analyzing the properties of an algorithm I am working on (I'm a computer scientist), ...
• 45
1 vote
65 views

• 3,525
267 views

• 11
187 views

### Is the Rado graph the unique countable graph that has all finite graphs as induced subgraphs?

I understand that since the Rado graph is the Fraïsse limit of the class of finite graphs, it is the unique homogeneous graph with this property. Is there another graph not isomorphic to the Rado ...
44 views

### Kernel perfection in some powers of cycles

Suppose I orient the edges of the power of cycle graph $G=C_n^k$ where $n=16$ and $k=4$ in such a way that all the generated cycles by the elements $1,2,3,4$ are given the standard lexical orientation....
• 1,841
160 views

• 315
114 views

44 views

96 views

### Finding an easy example appying the general Lovász local lemma

Is there any easy application for the generanl local lemma as follows? If someone knows, please tell me the references or just post an example here. Thanks. General Lovász local lemma: Consider a set ...
• 1,068
126 views

### Bounding the size of subspaces of $\mathbb{Z}^n$

For a subgroup $V$ of $\mathbb{Z}^n$, define $\Vert V \Vert$ to be the smallest $k$ such that $V$ is generated by its intersection with the closed $k$-ball around the origin in $\mathbb{R}^n$. Also, ...
• 23
125 views

### Major indices of standard tableaux of shapes obtained from addable cells of a given Young diagram

I have a "very" indirect proof that the following fact is true for every Young diagram $\lambda \vdash n$ and every $r \in \{0,\dotsc,n\}$: d_\lambda = \sum_{a \in \mathrm{...
• 133
75 views

### Isomorphism and counting for tree quivers

Let $Q$ be a quiver which is a connected tree and let $A=KQ/I$ be a quiver algebra with $I$ an admissible ideal, meaning that $I$ is generated by paths of length $\geq 2$. Let $n$ be the number of ...
• 25.3k
214 views

### Injection of Catalan objects into 3-connected planar graphs

Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon. Let $P_n$ be the number of three-connected planar ...
• 5,473