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
4 votes
0 answers
134 views

Approximation of a convex shape in the $d$-dimensional Euclidean space for $d\gg 1$

We are given a convex shape $C$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume of $C$ be $\tfrac12$ (I guess nothing changes for any other fixed constant ...
1 vote
0 answers
143 views

Bounds for the number of self-conjugate partitions [closed]

is there any upper bound for the number of self-conjugate partitions, or equivalently the number of partitions with distinct odd parts? P.S.: I didn't get why my question has been moved to Math Stack ...
  • 531
0 votes
1 answer
84 views

Does $\sum_{|S| \text{ even}} f(S) \le \sum_{|T| \text{ even}} f(T)$ hold for all nondecreasing submodular functions f?

Let $f : 2^n \to \mathbb{R}$ be a nondecreasing submodular function, where $2^n$ is the powers of $\{1, \dots, n\}$. Here nondecreasing means that $f(S) \le f(T)$ for all $S \subseteq T$. And ...
  • 507
1 vote
1 answer
143 views

A combinatorial matrix reconstruction problem II

For a positive integer $n$, let an $n$-shuffle be a multiset $S=[(S_i,d_i)|i=1,\ldots,n]$ of pairs $(S_i,d_i)$, where each $S_i$ is a multiset of $n$ numbers containing the number $d_i$. A realization ...
0 votes
1 answer
97 views

Asymptotics of certain sum with alternating sign (inclusion exclusion principle)

I'm aware of the replies to this question, but I was not able to apply the suggested methods in my case. I would like to compute the asymptotics of the resulting sum $S$ when computing the number of ...
  • 253
5 votes
1 answer
139 views

$d$-ball approximation for $d\gg 1$ with a convex hull of random points on its boundary

Given a $d$-ball $\mathcal{S}^{d}$, let $P_n$ a set of $n$ points selected uniformly at random on the boundary $\mathcal{S}^{d-1}$ of $\mathcal{S}^{d}$. Let $\mathcal{C}_n$ the convex hull of $P_n$. ...
4 votes
1 answer
173 views

Representation of $\mathrm{AGL}(V)$ on the homology of the poset of affine subspaces of $V$

Let $V$ be an $n$-dimensional vector space over a finite field $F$ (of order $q$). Denote by $\mathrm{AGL}(V)$ the group of invertible affine transformations of $V$; so $\mathrm{AGL}(V)$ consists of ...
0 votes
0 answers
86 views

Bound on the number of maximum matchings in a graph

It is known that the number of perfect matchings in a graph is bounded above by the integer part of the square root of the permanent of its adjacency matrix. But, suppose I take the square root of the ...
  • 1,775
1 vote
2 answers
188 views

Only trivial solutions to system of linear diophantine equations possibly related to hamiltonian cycles in graphs

This might be related to counting hamiltonian cycles. @Peter Taylor gave negative result about the one dimensional case, but we believe his attack is not directly applicable to this question. Given ...
  • 23.7k
4 votes
0 answers
191 views

A technical question about a paper by Gross-Hacking-Keel

I have a technical question on the commutativity of diagrams (2.11) and (2.12) in the paper "Birational geometry of cluster algebras" by Gross-Hacking-Keel: For the leftmost square in (2.11),...
  • 61
11 votes
1 answer
284 views

Configurations of points and circles

Problem. Several circles are drawn on the plane and all points of their intersection or touching are marked. For which $n$ it is possible that each circle contains exactly $n$ marked points and each ...
5 votes
0 answers
91 views

Does the (Poincare) dual complex represent the same topology?

To start with, consider some abstract $3$-dimensional simplicial complex $\Delta$ representing a manifold without boundary, for simplicity. Then, there is this well-known construction of the "(...
  • 505
1 vote
0 answers
121 views

Counting Hamiltonian cycles in graph and finding a coefficient of polynomial

Exact result is #P-Hard, so we are looking for bounds. Let $G$ be simple graph or simple digraph and $A$ its adjacency matrix. $A$ is $n \times n$ with entries only zeros or ones. Let $K=\mathbb{Z}[...
  • 23.7k
4 votes
0 answers
141 views

How many choices for $(f,g)$ such that $f \circ g = h$?

For $a,b,c \in \mathbb{N}$ let $[a] := \{1,...,a\}$ and suppose a map $h: [a] \rightarrow [c]$ is given. How many choices $(f,g)$ for maps $f: [a] \rightarrow [b]$ and $g: [b] \rightarrow [c]$ are ...
  • 489
0 votes
0 answers
30 views

Can Paulus graphs be distinguished using 4-WL test?

Being strongly regular graphs, different Paulus graphs cannot be distinguished using a 3-WL test. Is it known whether they can be distinguished using a 4-WL test?
2 votes
0 answers
49 views

Regular graphs of tangent spheres

Problem 1. Let several non-overlapping spheres in $\mathbb{R^3}$ are given. For which $n$ it is possible that each sphere is tangent to exactly $n$ other spheres? Consider the smallest sphere. Since ...
5 votes
1 answer
202 views

Can there be an application of discrete mathematics in PDEs, mainly the ones used in hydrodynamics?

Can there be applications of graph theory, combinatorics etc. in PDEs mainly hydrodynamics? Tried my luck with Google's search engine, didn't show much info. I guess you can try to use these features ...
  • 1,487
2 votes
1 answer
226 views

Parabolic subgroup of Weyl group

Let $W$ be the Weyl group of a semisimple algebraic group $G$. $I$ be the simple roots. $J\subset I$ generate a parabolic subgroup of $W$ denote by $W_J$. $w^J$ is the shortest representative of $w$ ...
7 votes
1 answer
136 views

A formula for the generating function of Hoggatt binomials or of some Young tableaux

Let ${\left\langle\matrix {n \cr k}\right\rangle}_r$ denote the $r-$Hoggatt binomials defined by $${{\left\langle\matrix {n \cr k}\right\rangle}_r=\frac{\langle n \rangle_r!}{\langle k \rangle_r! \...
5 votes
1 answer
245 views

Largest girth of a graph of average degree k

Let G be a graph with $n \ge 3$ nodes and with average degree $3\le k\le n$. What are the largest and smallest girth G can have?
  • 4,971
1 vote
1 answer
163 views

Deciding if given number is a permanent of matrix

The permanent of an $n$-by- $n$ matrix $A=\left(a_{i j}\right)$ is defined as $$ \operatorname{perm}(A)=\sum_{\sigma \in S_{n}} \prod_{i=1}^{n} a_{i, \sigma(i)} $$ The sum here extends over all ...
2 votes
1 answer
97 views

The number of $3$-CNF formulas in $n$-variables and the fraction of satisfiable ones

What is the number of $3$-CNF (conjunctive normal form) formulas with $n$ sentential variables and what is the fraction of satisfiable ones? I consider two formulas the same if they are syntactically ...
2 votes
0 answers
78 views

List decodability of Reed-Solomon codes beyond the Johnson bound

In a paper on a proximity test for Reed-Solomon codes the authors state an "extremely optimistical" conjecture on the list decodability of Reed-Solomon codes (over prime fields $\mathbb F_q$)...
3 votes
0 answers
66 views

Unit distance graphs with large minimum degree

Inspired by this (now closed) question, I was wondering the following: What is the smallest possible cardinality of a set $P$ of points in the plane such that no three points in $P$ are collinear, ...
6 votes
0 answers
164 views

Number of square-free polynomials over a finite field - a combinatorial interpretation?

Cross-posted from MSE. The question has remained unanswered for six years but I still like it! One can show using zeta functions that the number of (monic)square-free polynomials of degree $n$ over a ...
  • 7,142
1 vote
0 answers
78 views

Doubly log-concave or doubly log-convex

Suppose $(a_k)_{k\geq0}$ is a sequence of real numbers. Consider the operator $\mathcal{L}a_k=a_k^2-a_{k-1}a_{k+1}$. We say $(a_k)_k$ is log-concave (resp. log-convex) provided $\mathcal{L}a_k\geq0$ (...
0 votes
0 answers
40 views

Cohomology groups of the complex of sets whose convex hull not containing 0 in $\mathbb{R}^d$

Wegner proves that let $K$ be a finite family of convex sets in $\mathbb{R}^d$, then the Nerve of $K$, which is a simplicial complex and is defined as $$D=N(K):=\{ \{S_1,\dots, S_k\}: S_i\in K \text{ ...
  • 241
1 vote
0 answers
128 views

Has Mac Lane's article "When can a graph be mapped on a torus?" been published anywhere?

I came across the following abstract of an article: Mac Lane, S., When can a graph be mapped on a torus?, Bull. Amer. Math. Soc. 42(9), 629 (1936). Abstract #341. MR1563375, JFM 62.0694.07. Q. Does ...
4 votes
0 answers
138 views

Invariant Spaces of Hypergraphs

The following arose from a question in model theory (specifically in the model theory of modules). Fix an arity $k$. Let $[\mathbb{Q}]^k$ denote the set of all subsets of $\mathbb{Q}$ of cardinality $...
5 votes
0 answers
159 views

Groups of non-orientable genus 1 and 2

The non-orientable genus (aka crosscap-number) $\overline{\gamma}(G)$ of a finite group $G$ is the minimum non-orientable genus among all its connected Cayley graphs (and $0$ if $G$ has a planar ...
1 vote
0 answers
51 views

Constructing k-wise independent variables over a general set

We have seen in class a polynomials based construction that builds in $O(n^k)$ time, $n$ random variables, $k$-wise independent, over a field with $n$ elements. More specifically, you generate all the ...
  • 11
2 votes
0 answers
99 views

Combinatorial characterizations of complex weight supports

This question is related to my last question and is originally motivated by recent advances in quantum physics. I am looking for combinatorial characterizations of some algebraically defined families ...
  • 2,747
4 votes
0 answers
169 views

Non-crossing and crossing bijection in higher genus

This is a follow-up question of my SO post I'll briefly mention it here. So given a $n$ cycle say $(1,2,\ldots,n)$, what are the monotonic 2 -tuples, of the form $(a,b)(c,d)$, monotonicity in on the ...
  • 635
12 votes
2 answers
459 views

Generating function for counting partitions with corners

A corner of an integer partition is a location at where a box can be added to its Ferrers diagram to give a new partition. E.g. the partition $\{1,1,1\}$ has two corners, and $\{1,2\}$ has three ...
3 votes
1 answer
131 views

When Alexander dual of a simplicial complex is a matroid?

Let $C$ be a simplicial complex on a finite set $V$: that means $C$ is a collection of subsets of $V$ such that if $\sigma\in C$ and $\tau\subseteq \sigma$, then $\tau\in C$. The Alexander dual $D(C)$ ...
  • 241
12 votes
0 answers
271 views

$q$-analogue of the multinomial theorem?

The $q$-binomial theorem states that $$ \prod_{k=0}^{n-1}(1+q^kt) = \sum_{k=0}^n q^{\binom k2}{n\brack k}_q t^k. $$ This identity is a $q$-analogue of the binomial theorem $$ (1+t)^n = \sum_{k=0}^n \...
7 votes
1 answer
126 views

Density of “diagonal sets” in amenable groups

Let $G$ be a countable amenable group with a (left) Følner sequence $(F_n)$. Let $\Gamma$ be a subset of $G$ that has density $1$ with respect to $(F_n)$, in the sense that $$ \lim_{n \to \infty} \...
  • 323
0 votes
0 answers
416 views

How to calculate determinants of such types?

Consider next determinant that we want to expand around $h=1$ \begin{eqnarray} Z_q \ = \ h^{N N_f} \ \ \left ( \prod_{n=1}^{N} \ \sum_{l_n=0}^{N_f -q} \ h^{2l_n+q} \ \binom{N_f}{l_n} \right ) \ \...
2 votes
0 answers
76 views

Evaluation of a summation involving Hermite polynomials

I started with the the following four-variable function, $f(s,x,y,u)$, expressed as a summation involving the product of Hermite polynomials. $f(s,x,y,u)=\sum_{n=0}^{\infty}\frac{H_{n}(x)H_{n}(y)}{(n-...
3 votes
0 answers
93 views

Counting homologically non-trivial and trivial cycles in $n \times n$ square lattice torus of a given length $l \geq n$

This should be a fairly standard question but I can't really seem to find a reference. Consider an $n \times n$ square lattice torus $\mathbb T$. Given a length $l \geq n$, what is the number of ...
11 votes
1 answer
304 views

Complexity of counting regions in hyperplane arrangements

Let $H_1,\ldots,H_n$ be hyperplanes in $\Bbb R^d$. Denote $\mathcal{H} :=\{H_1,\ldots,H_n\}$ and let $c(\mathcal{H})$ be the number of regions in the complement: $\Bbb R^d\setminus \bigcup H_i$. ...
  • 16k
1 vote
1 answer
193 views

Gaussian at $q=\pm1$, log-concave polynomials, Catalan numbers

Let $[n]_q!=\prod_{j=1}^n\frac{1-q^j}{1-q}$ with $[0]_q!:=1$ and the Gaussian polynomials $\binom{n}k_q=\frac{[n]_q!}{[k]_q!\,\cdot\,[n-k]_q!}$. Adopt the convention that $\binom{n}k_q=0$ whenever $k&...
0 votes
0 answers
117 views

Szemeredi's regularity lemma for countably infinite graphs?

Consider the following version of Szemeredi's regularity lemma found in the Fox and Lovasz paper, "A tight lower bound for Szemeredi's regularity lemma", arXiv: 1403.1768v1 [math.CO] 7 Mar ...
2 votes
1 answer
82 views

Lower bound on the number of balanced graphs

Let $\alpha>1$ be a constant and define $B_n$ as the number of (labeled) balanced graphs with $n$ vertices and $\left\lceil \alpha n\right\rceil $ edges. The paper Strongly Balanced Graphs and ...
  • 123
7 votes
1 answer
183 views

Robinson-Schensted-Knuth (RSK) under restriction

I am curious about the following result concerning the Robinson-Schensted insertion procedure. I can formulate a proof via the Schützenberger evacuation operator, but I have struggled to find such an ...
2 votes
0 answers
90 views

Perfect matching decomposition algorithm for bipartite regular graphs

It is a well-known result that a bipartite graph can be decomposed into edge-disjoint perfect matchings if and only if it is regular. Now here comes the question. Given a bipartite regular graph, is ...
  • 21
5 votes
1 answer
306 views

Is there a simple expression for $\sum_{k =1}^{(p-3)/2} \frac{1\cdot 3\cdots (2k-1)}{2\cdot 4 \cdots 2k\cdot(2k+1)} \bmod p$?

Let $p \equiv 1 \pmod 4$ be a prime and $E_n$ denote the $n$-th Euler number. While investigating $E_{p-1} \pmod{p^2}$ I have encountered this summation (modulo $p$) \begin{align*} \sum_{k =1}^{\frac{...
2 votes
0 answers
72 views

Maximal subsets of affine or projective space with no three collinear points

Let ${\mathbb A}^n_q$ and ${\mathbb P}^n_q$ be affine and projective spaces of dimension $n$ over a field of order $q$. Say that a subset of either ${\mathbb A}^n_q$ or ${\mathbb P}^n_q$ is generic if ...
2 votes
1 answer
148 views

Only trivial solution to a pair of constrained linear diophantine equations

Given positive integer $n$, we are looking for a set of $n$ positive integers $a_i$. The following linear integer program must have only the trivial integer solution of all ones. $0 \le x_i \le \frac{...
  • 23.7k
1 vote
0 answers
44 views

How can we hang the weighted trees so that vertices nearer to root (based on distances, not hop count) lie in upper levels?

I have a set of edge weighted trees, each tree rooted at some vertex. Consider these trees are hung from the roots and vertices are arranged in some levels. I wish to design an algorithm (...