As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [extremal-combinatorics]

The tag has no usage guidance.

178 questions
Filter by
Sorted by
Tagged with
1 vote
174 views

### Reference for a topological result

I am reading the short paper due to Erdös and Bollobás "On a Ramsey-Turán type problem", where they obtain a lower bound for the number of edges on an $n$-graph without $K_4$ as a subgraph ...
116 views

### On nilpotent singular $\mathbb F_2^{n\times n}$ matrices

Let $M$ be a $0/1$ matrix over $\mathbb F_2^{n\times n}$ with determinant $0$. The set of such singular matrices form a semigroup. The set of nilpotent matrices of size $n\times n$ form a semigroup. ...
226 views

### A Sauer-Shelah-like lermma for prefix tree

I proved a variant of the Sauer-Shelah lemma and I was wondering if something like that is already known. Let $S \subseteq \{0,1\}^n$. We say that a set of coordinates $K \subseteq [n]$ is shattered ...
280 views

116 views

1 vote
68 views

### 4-cycles vs eigenvalue information on quasi-random graphs

My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs. The main purpose of the paper is to show ...
54 views

### Maximal families of equal length intervals consist of equilateral triangles

My question is a follow up to How to find n points on a plane so that as many pair of points as possible have the same distance? -- see the conjecture at the bottom of this post. Let $\ n\$ be a ...
1 vote
Suppose $A$ is some set. Let's define a pair semigroup over $A$ as $P[A] = (A\times A \cup \{0\}, \circ)$, where the $\circ$ operation is defined by the following two identities: $\forall a \in P[A]$ ...
### How many edges can be in an unbalanced bipartite graph of girth $>6$?
Let $G = (V, E)$ be a bipartite graph with $n, m$ nodes in its bipartition and girth (shortest cycle length) $>6$. There is a simple counting argument called the Moore Bounds that gives |E| = O\...