# 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,445 questions
Filter by
Sorted by
Tagged with
46 views

### Clique sizes of generalized Kneser graphs

Are there known bounds for clique size in generalized Kneser graphs $KG(n,k,t)=K(n,k,t-1)$, the graph formed by distinct $k$ subsets of $n$ set so that two subsets with at most $t$ elements in common ...
• 1,975
55 views

### Cycles in Kneser graphs with three vertices forming triangles

Consider the Kneser graphs $G=K(n,k)$. Is it possible to list how many even cycles, or, at the least, existence of an even cycle of a given order in $G$, such that any three consecutive vertices form ...
• 1,975
612 views

### Does every big polyomino contain a big arithmetic progression?

Define a $k$-AP (arithmetic progression) as $k$ vertices whose $x$- and $y$-coordinates both from an arithmetic progression, for example, (1,0), (2,2), (3,4) is a 3-AP. Is it true that for every $k$ ...
• 18.2k
3k views

### Number of real roots of 0,1 polynomial

$0,1$ polynomial has coefficients from $\{0,1\}$. I investigate the number of roots in such polynomials. We are talking about real roots, and multiples are counted only once. It was found numerically ...
• 442
35 views

### Determining homomorphism using automorphism group of two graphs

I wish to know the connection between the automorphism group of two graphs and homomorphism between them, if any. Like all Kneser graphs $K(n,k)$ have the same automorphism group $S_n$. But, given ...
• 1,975
1 vote
83 views

• 3,278
132 views

### Smallest dominating set

Given a graph $G$, we say $S$ is a dominating set if $S\cup \{N(x):x\in S\}=V(G)$. Let $d(n,k)$ be the smallest integer $s$ so that every $n$-vertex graph $G$ with minimum degree $k$ has some ...
• 3,335
401 views

• 12.6k
111 views

### Do uniquely Hamiltonian graphs have cycles of a sufficiently long length?

Let $C$ be a Hamiltonian cycle of a graph $G$. Call an edge $e$ of $G$ a chord if $e\not\in C$. Let each edge of $C$ be weighted $1$ and each chord be weighted $2$. The weight of a path or cycle of ...
• 673
101 views

• 301
264 views

### Generating 21-vertex 4-regular plane graphs with 8 faces of degree 3 and 15 faces of degree 4

Is there any way to generate all 4-regular plane graphs with 21 vertices, 8 faces of degree 3, and 15 faces of degree 4? If so, how many of these graphs are there and what are they?
• 1,130
56 views

### Some version of graph removal lemma

I found the following statement in 'A proof of the stability of extremal graphs, Simonovits’ stability from Szemerédi’s regularity' by Zoltán Füredi: Lemma: For any $\alpha>0$ and a graph $F$, ...
• 281
45 views

### Existence of finite 3-dimensional hyperbolic balanced geometry

Together with @TarasBanakh we faced the problem described in the title. Let me start with definitions. A linear space is a pair $(S,\mathcal L)$ consisting of a set $S$ and a family $\mathcal L$ of ...
• 471
87 views

• 1,593