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
53 views

Differences of elements of a set of natural numbers (reference request)

Let $A$ be a subset of $[n] = \{1,2,\dots,n\}$. Define $\overline A = \{(i,j) : i, j \in A \text{ and } i > j \}$ and define $(i_1,j_1) \sim (i_2,j_2) $ if $i_1 - j_1 = i_2 - j_2$. This is ...
5
votes
0answers
118 views

A “polar dual” for projective varieties?

Given a projective variety $X$ (over $\mathbb{C}$, say) with an affine paving $X=\sqcup_i C_i$, one can construct a poset $P_X$ on the set of cells $\{C_i\}$ by saying $C_i \leq C_j$ whenever $C_i \...
15
votes
1answer
263 views

Geometric interpretation of the exceptional isomorphism $PSp(4,3)=PSU(4,2^2)$

It is well-known that there is an isomorphism between $PSp(4,3)$ (the symplectic group of dimension $4$ over $\mathbb F_3$) and $PSU(4,2^2)$ (the unitary group defined by $4\times4$ unitary matrices ...
0
votes
1answer
78 views

Bound for Large deviations of sums of independent (not identical) variables

I am working with a sum of variables $X_i$; they are all independent, but not identically distributed. For any $i$, I can show the bound $$\Lambda^*_{X_i}(t) := \sup_t \langle t, x \rangle - \Lambda_X(...
-1
votes
1answer
73 views

Tuza theorem to prove vizing theorem

The Tuza theorem states that every graph with no cycle congruent to 1 mod $k$ is $k$ colorable. Now, the line graph of any simple graph of maximum degree $d$ is seen to posess the property that it has ...
8
votes
2answers
232 views

Two rows of bounded numbers

Given is an integer $n\ge 2$ and two rows of $n$ positive real numbers each, with each number not more than $n-0.5$, such that the numbers in each row sum to $n$. Is it always possible to choose some ...
6
votes
2answers
239 views

Multivariate Lagrange inversion with zero powers

(Also asked on MSE) The multivariate Lagrange inversion formula, which I found in a couple of papers (such as this and this), is as follows. If $f_i=t_ig_i(f)$, $1\le i\le k$, then $$ [t^n]h(f(t))=\...
2
votes
0answers
61 views

Representing graphs as induced subgraphs of $\text{Hom}(H,K)$

Let $H, K$ be simple, undirected graphs, and let $\text{Hom}(H,K)$ the collection of graph homomorphisms $f: H\to K$. (Note that $\text{Hom}(H,K)$ might be empty.) For $f,g\in \text{Hom}(H,K)$ we say ...
5
votes
0answers
95 views

Cut norm versus $l_1$ norm

Let $K$ be the set of $n\times n$ matrices with zero diagonal entries and such that the sum of all entries is zero. The cut norm of a $n\times n$ matrix $M$ is: $$ cut(M) = \sup_{S, T, S\cap T = \...
0
votes
2answers
104 views

Majority-driven manipulations of integer vectors

Motivation. Recently I was watching two people play a game that involved arranging sticks in a number of heaps and moving them around in certain allowed ways that I think I was able to infer from ...
7
votes
3answers
338 views

Polygonal paths and polygons with prescribed set of vertices

Let $A$ be a finite set of points in the plane. How can we determine if there is a simple open polygonal path (i.e. without intersections), whose vertices are exactly $A$, with no straight angles ...
1
vote
1answer
95 views

Distribution of non-overlapping words in randomly generated text

The question can be described in the following way: Suppose I have a finite language $\mathcal{L}$ over alphabet $\Sigma$. I have a string that is composed of a concatenated series of $n$ instances ...
0
votes
1answer
114 views

Size of parities in counting partitions into odd parts

Let $p_{odd}(n)$ be the number of partitions of $n$ into odd parts (see here). For instance, one has the generating function $$\prod_{k\geq1}\frac1{1-q^{2k-1}}.$$ QUESTION. What is the size of this ...
2
votes
0answers
86 views

Lorentzian (=Minkowskian) Hadwiger-Nelson problem: is the chromatic number finite?

Background: Some years ago, I collected a number of thoughts and partial results (which, based on Soifer's Mathematical coloring book, I believed were new) on the Hadwiger-Nelson problem in a note ...
4
votes
1answer
81 views

Complexity of graph 3 coloring and counting algorithm

3-coloring a graph $G$ is equivalent to partitioning the vertices of $G$ in three independent sets. The smallest independent set $A$ is at most $n/3$ where $n$ is the order of $G$. We have $G \...
11
votes
1answer
324 views

$q$-analogs of total positivity

A real matrix $M$ is called totally positive if all of its minors are positive; these matrices have been extensively studied, and there are generalizations to other Lie types, for example by Lusztig. ...
0
votes
1answer
78 views

Terminology and approximation to logarithm of a sum of products of binomial coefficients

Denote $$T(m)=\sum_{1\leq n_m\leq n_{m-1}\leq\dots\leq n_2\leq n_1\leq m}\prod_{i=1}^{m}\binom{n_i}{n_{i+1}}.$$ Is there a name for this kind of summation and is there a good estimate for $\ln T(m)$ ...
0
votes
2answers
182 views

Interpolating asymptotic expression for logarithm of middle binomial sums

Define $S(k,2n)=\sum_{i=-k}^k\binom{2n}{n+i}$ at every $k\in\{0,\dots,n\}$. We know $$\ln(S(\gamma\mbox{ } n^\gamma,2n))\asymp(2n\ln2-\frac12\ln\pi-\frac12\ln n)$$ at $\gamma\rightarrow0$ and $$\ln(S(...
1
vote
0answers
69 views

Relation between Betti Numbers and Chromatic Number of a simple graph

Is there a relation between the betti numbers of a graph considered as a simplicial complex and its chromatic number? Typically the first Betti number is said to be the cyclomatic number of the graph....
0
votes
0answers
179 views

A gap problem in elementary additive combinatorics

Given $a,b\in\mathbb N$ define the set $$\chi(a,b)=\{M\in\{0,1\}^{n^a\times n^b}:\mbox{ every row of }M\mbox{ is distinct}\}.$$ Also given ${\bf{x}}=(x_1,\dots,x_{n^b})\in\mathbb Z^{n^b}$ define the ...
7
votes
2answers
248 views

Rank matrices for type $D$ Bruhat order

Roughly, this question asks how the Bruhat (strong) order in type $D$ can be understood like the Bruhat orders in types A and B=C. I'll review how types A and B work before asking my question. As a ...
3
votes
0answers
103 views

Number of adjoint orbits containing a $(0,1)$-matrix

Motivated by this question, what can be said about the number $f(n)$ of adjoint orbits of $\mathrm{Mat}(n,\mathbb{C})$ (the ring of all $n\times n$ complex matrices) that contain a $(0,1)$-matrix? ...
7
votes
0answers
197 views

Possible oversight in paper of Greene and Kleitman on chains in dominance order on partitions?

This question is about a possible lacuna in a paper of Greene and Kleitman which Zarathustra Brady made me aware of. The paper in question is "Longest Chains in the Lattice of Integer Partitions ...
7
votes
2answers
231 views

What makes skew characters of the symmetric group special?

For integer partitions $\mu\subset\lambda$ we can define the skew character $\chi^{\lambda/\mu}$ (for example?) via the Littlewood-Richardson rule. Many combinatorial gadgets and algorithms extend in ...
1
vote
1answer
51 views

Regions of hyperplane arrangements and their faces

Consider a finite hyperplane arrangement $\mathcal{A}$ over $\mathbb{R}^n$. Let the regions given by $\mathcal{A}$ be $\mathcal{R}(\mathcal{A})=\{A_1,\dots A_m\}$ for some $m$. For any index set $I\...
5
votes
1answer
155 views

Non-nesting matchings and Catalan numbers

It is well-known that the number of non-nesting perfect matchings on $2n$ points is given by the Catalan number $C_n$; see part (a) of the figure below. This is item e^5 in Stanley's list (http://www-...
0
votes
1answer
80 views

Number of positive integer solutions with a lower bound

If $0\leq\gamma<\alpha<1$ and $t=\lceil n^\gamma\rceil$ hold then how many positive solutions to the linear diophantine equation $$x_1+\dots+x_t=\lceil n^\alpha\rceil$$ have the property $$n^\...
4
votes
0answers
116 views

Overview of Combinatorial Technique of “Selberg’s Symmetry Formula”

In the paper entitled "A Computational History of Prime Numbers and Riemann Zeros" (on page 4, click here) it is written about "Selberg’s symmetry formula" that- Until 1950 it was widely believed (...
1
vote
1answer
48 views

Counting multisets satisfying a fixed property

Suppose $S$ is a infinite set and $R\subset S$ is also infinite. Now, we want to find the number of multisets $(M,\nu)$, with $M\subset S, |(M,\nu)|=n$, and having an additional property that for ...
6
votes
1answer
274 views

How large a subset of $\mathbb{F}_q^d$ can determine all determinants?

Denote by $\mathbb{F}_q$ a finite field with $q$ elements. For $\mathcal{P}$ be arbitrary subset of $\mathbb{F}_q^d.$ We define the set $$S:= \left\{ \det([x_1,x_2,\dots,x_d]): x_1,x_2,\dots,x_d \in ...
1
vote
0answers
97 views

Asymptotics of the Steenrod algebra / $s$-partitions?

Recall that an $s$-partition is a partition of a natural number $n$ such that each part is of the form $2^r-1$. By a fundamental theorem of Milnor, the number $p_s(n)$ of $s$-partitions of $n$ counts ...
1
vote
2answers
154 views

Bilinear recurrence relation between even Bernoulli numbers

Throughout this question $n$ is a positive integer greater than 1. Consider the following well-known identity by Euler, $$\sum_{k=1}^{n-1} \binom{2n}{2k}B_{2k}B_{2n-2k}=-(2n+1)B_{2n}.$$ Rather ...
0
votes
0answers
58 views

Singular values and the chromatic number

What relation, if any, is there between the singular values of the adjacency matrix ( or possibly incidence matrix) of a simple graph and its chromatic number. Typically, do we have Hoffmann type, or ...
3
votes
1answer
126 views

Map on class of all finite posets coming from maximal sized antichains

Let $P$ be a finite poset. Let $\mathcal{A}$ denote the set of antichains of $P$. Equip $\mathcal{A}$ with a partial order $\preceq$ whereby $X \preceq Y$ means for all $x \in X$ there exists $y \in Y$...
3
votes
0answers
71 views

Arzela-Ascoli-analogue statement over a given cardinality of discrete space

(I think there would be better title for my question. If there is a good idea on the title, please let me know.) Consider the following statement: Let $A$ be a set (with the discrete topology, if ...
2
votes
2answers
164 views

Cartan determinants of subsets

Let $n \geq 3$ be fixed. We associate to every subset $S \subseteq \{1,...,n-1 \}$ a number, which we call Cartan determinant of $S$ (see the end of this post for a representation theoretic background)...
5
votes
2answers
190 views

Nontrivial expansion in sumsets

Let $A \subset \mathbb{Z}/p$, let $f$ be a function on $\mathbb{Z}/p$ and let $B:=\{f(a): a \in A\}$. Can we conclude that $|A+B|$ is large if $f$ is a sufficiently "nice" function? For instance say ...
1
vote
0answers
86 views

Generating graphs of groups

Suppose $G$ is a group and $S \subset G$ is its finite subset. Let’s define the generating graph of $G$ in respect to $S$ as $Gen(G, S)$ - a graph $\Gamma(V, E)$, where $V = S$ and $E = \{(a, b) \in S ...
3
votes
1answer
238 views

“Non-associative” standard polynomials

I saw somewhere (I appreciate if anyone has any references to proof of this fact) that if $A$ is a finite dimensional associative algebra such that $\textrm{dim}(A)<n$, then $A$ satisfies the ...
1
vote
0answers
72 views

Flag $f$-vectors of CW-complexes

Hidden away in the appendix of this nice paper by Björner and Kalai, they give a clean description of $f$-vectors that can arise from regular CW-complexes in terms of truncations of the Euler-Poincaré ...
2
votes
0answers
129 views

Tradeoffs in translation-invariant tilings of $\mathbb{R}^3$

Suppose I tile $\mathbb{R}^3$ in a ($\mathbb{Z}^3$-)translation-invariant manner. If we insist on the tiling being regular, then we are left with only the cubic tiling. However, suppose that we ...
3
votes
0answers
82 views

Terminology for set systems: “trace” or “projection”?

Although the following question is not in itself mathematical, it is the expertise/breadth of the research community in mathematics that I wish to appeal to, beyond the filtered/trained search results ...
4
votes
2answers
169 views

Number of nonequivalent weight functions on a set of $n$ elements

For a finite set $S$ of $n$ elements, say a weight function is a function $f \colon S \to \mathbb{R}$. For any subset $T \subseteq S$, define $f(T) = \sum _{x \in T} f(x)$. Define two weight functions ...
1
vote
0answers
58 views

The degree of a (combinatorial) selfmap

If $f$ is a map from a finite set to itself, is there any widely accepted definition of the "degree" of $f$? I would like to define deg $f$ as the quantity discussed in Quantifying the ...
2
votes
1answer
28 views

Simple balance incomplete block design, (complete graph clique decomposition)

I am trying to find methods to construct a $(n,k,1)$-BIBD with large $n$ and $k$. Basically, I'm wondering if there's an established method to create as many sets of size $k$ from elements $\{1, ..., ...
2
votes
1answer
154 views

How to classify solutions to the following equations?

I would like to classify the sets of integers $a_{1},...,a_{n}$ that satisfy the following two equations. $$\sum_{k=1}^{n}a_{k}\equiv 0\mod 2$$ $$\sum_{i\neq j}a_{i}a_{j}=0$$ For example, if $n=3$, I ...
0
votes
1answer
106 views

Closed form solution for a binomial coefficient relation?

In following, $x_{n}$ is a set of given numbers, n = 0, 1, 2, ..., $y_{n}$ is defined by the following recursive relation of $x_{n}$: For example: ${\displaystyle {x_{1}=x_{0}y_{1} }}.$ ${\...
7
votes
3answers
274 views

Quantifying the noninvertibility of a function

Given a function $f$ from a finite set $X$ to itself, it seems natural to consider $\kappa_f := (\sum_{x \in X} |f^{-1}(x)|^2)/|X|$ as a measure of the non-invertibility of $f$: it equals 1 if $f$ is ...
8
votes
0answers
241 views

When does a graph have a minimally strong orientation?

Given any asymmetric relation $A\subseteq V^2$ a digraph $D=(V,A)$ is minimally strong iff $D$ is strongly connected and for every arc $a\in A$ the digraph $D−a=(V,A\setminus\{a\})$ is not strongly ...
1
vote
1answer
130 views

Finding Littlewood-Richardson coefficients without using identities

The Littlewood-Richardson coefficients $C^{R}_{QP}$ for some partitions $R, Q, P$ can usually be dealt with using identities like for example $$C^{R}_{QP} = 0 \quad \text{ if } \quad|R| \neq |Q| + |P|...