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

6,675 questions

**0**

votes

**0**answers

15 views

### Structure of color critical graph

Let $G$ be a $k$-color critical graph on $N$ vertices. It is a known fact that every vertex of $G$ has at least $k-1$ neighbors (there are more results available on minimum number of edges in color ...

**-3**

votes

**0**answers

75 views

### Differential privacy [on hold]

I'm reading the following book on privacy.
https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf
however I'm having a lot of trouble making any kind of intuitive sense from the very complicated ...

**2**

votes

**2**answers

82 views

### Asymptotics of regular semisimple elements in finite groups of lie type

Let $G$ be a reductive algebraic group defined over $\mathbb{F}_{q}$. Let $G(\mathbb{F_{q}})$ denote the finite group of fixed points under the Frobenius map $F$. Now, we know that the set of regular ...

**4**

votes

**0**answers

123 views

### Product of $q$-analogues

Background
Recall that the $q$-analogue $[n]_q\in\mathbb Z[q]$ of a natural number $n\in\mathbb N$ is defined as
$$ [n]_q := \frac{q^n -1}{q-1}$$
the idea being that formulas involving $q$ will ...

**2**

votes

**1**answer

56 views

### Polynomial time decodable binary linear codes achieving $GV$ bound?

Are there explicit or random construction of linear codes that achieve the $GV$ bound with polynomial time decodable property with alphabet size $q=2$?
Tsfasman, Manin, Vladut beat the bound at ...

**4**

votes

**0**answers

77 views

### Generalized graph-minor theorem?

Consider the following generalized graph-minor theorem:
GM($κ,λ$): Given any collection $S$ of $κ$ simple undirected graphs each with less than $λ$ vertices, there are distinct graphs $G,H$ in $S$ ...

**6**

votes

**0**answers

80 views

+500

### Does hereditary 2-coloring imply polychromatic 3-coloring for large edges?

For a hypergraph $\mathcal H=(V,\mathcal E)$, denote by $m_k$ the smallest number for which we can $k$-color any $X\subset V$ such that for any $E\in \mathcal E$ with $|E\cap X|\ge m_k$ all $k$ colors ...

**1**

vote

**0**answers

119 views

### A binary wrap function [on hold]

This question was inspired by a card puzzle.
Define a wrap function to take an $N$-bit number to another $N$-bit number by
"negating and reversing and wrapping leading bits" (this is just the ...

**9**

votes

**0**answers

97 views

### Irreducibility of root-height generating polynomial

The height $ht(\alpha)$ of a positive root $\alpha$ in a (finite, crystallographic) root system $\Phi$ is $\sum_{i=1}^n c_i$ where $\alpha = \sum_{i=1}^n c_i \alpha_i$ is its decomposition as a sum of ...

**2**

votes

**1**answer

86 views

### Is there a two-dimensional Higman's lemma?

A string over a finite alphabet $A$ can be thought of as a function
$f:\{1,2,...,m\} \rightarrow A$ for some natural number $m$.
A 2-Dim string over $A$ is a function $f$ where
$f:\{1,2,\ldots,m\}\...

**0**

votes

**0**answers

80 views

### Kastanas' game and completely Ramsey sets

recently I was reading the article ''On the Ramsey property for sets of reals'' of Ilias Kastanas (https://www.jstor.org/stable/2273667?seq=1#metadata_info_tab_contents), in this article the author ...

**7**

votes

**3**answers

322 views

### Arranging all permutations on $\{1,\ldots,n\}$ such that there are no common points

If $n>0$ is an integer, let $[n]=\{1,\ldots,n\}$. Let $S_n$ denote the set of all permutations (bijections) $\pi:[n]\to[n]$.
For which positive integers $n$ is there a bijection $\Phi:[n!]\to S_n$ ...

**1**

vote

**0**answers

27 views

### Minimum transitive dominating subtournament

For any positive integer $k$, does there exist a tournament such that the smallest dominating set that forms a transitive subtournament has size exactly $k$?
A tournament that does not work for $k>...

**4**

votes

**1**answer

45 views

### Calculate number of vertices adjacent to a clique, but not each other

I have a network of N sensors and a test that tells me whether two sensor outputs are definitely not causally related. This allows me to construct a causality graph where each sensor is a vertex and ...

**0**

votes

**0**answers

16 views

### Difference between Adjacent strong edge coloring and vertex distinguishing strong edge coloring

What is the exact difference between the adjacent strong edge coloring and vertex distinguishing proper edge coloring of graphs? This paper refers to the fact that the adjacent strong edge coloring of ...