BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Jacques Verstraete

Jacques Verstraete contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CO

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2022arXiv

Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth

In this paper, we consider a randomized greedy algorithm for independent sets in $r$-uniform $d$-regular hypergraphs $G$ on $n$ vertices with girth $g$. By analyzing the expected size of the independent sets generated by this algorithm, we show that $α(G)\geq (f(d,r)-ε(g,d,r))n$, where $ε(g,d,r)$ converges to $0$ as $g\rightarrow\infty$ for fixed $d$ and $r$, and $f(d,r)$ is determined by a differential equation. This extends earlier results of Gamarnik and Goldberg for graphs. We also prove that when applying this algorithm to uniform linear hypergraphs with bounded degree, the size of the independent sets generated by this algorithm concentrate around the mean asymptotically almost surely.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Set-coloring Ramsey numbers via codes

For positive integers $n,r,s$ with $r > s$, the set-coloring Ramsey number $R(n;r,s)$ is the minimum $N$ such that if every edge of the complete graph $K_N$ receives a set of $s$ colors from a palette of $r$ colors, then there is guaranteed to be a monochromatic clique on $n$ vertices, that is, a subset of $n$ vertices where all of the edges between them receive a common color. In particular, the case $s=1$ corresponds to the classical multicolor Ramsey number. We prove general upper and lower bounds on $R(n;r,s)$ which imply that $R(n;r,s) = 2^{Θ(nr)}$ if $s/r$ is bounded away from $0$ and $1$. The upper bound extends an old result of Erdős and Szemerédi, who treated the case $s = r-1$, while the lower bound exploits a connection to error-correcting codes. We also study the analogous problem for hypergraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A generalization of the Bollobás set pairs inequality

The Bollobás set pairs inequality is a fundamental result in extremal set theory with many applications. In this paper, for $n \geq k \geq t \geq 2$, we consider a collection of $k$ families $\mathcal{A}_i: 1 \leq i \leq k$ where $\mathcal{A}_i = \{ A_{i,j} \subset [n] : j \in [n] \}$ so that $A_{1, i_1} \cap \cdots \cap A_{k,i_k} \neq \emptyset $ if and only if there are at least $t$ distinct indices $i_1,i_2,\dots,i_k$. Via a natural connection to a hypergraph covering problem, we give bounds on the maximum size $β_{k,t}(n)$ of the families with ground set $[n]$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Triangle-free Subgraphs of Hypergraphs

In this paper, we consider an analog of the well-studied extremal problem for triangle-free subgraphs of graphs for uniform hypergraphs. A loose triangle is a hypergraph $T$ consisting of three edges $e,f$ and $g$ such that $|e \cap f| = |f \cap g| = |g \cap e| = 1$ and $e \cap f \cap g = \emptyset$. We prove that if $H$ is an $n$-vertex $r$-uniform hypergraph with maximum degree $\triangle$, then as $\triangle \rightarrow \infty$, the number of edges in a densest $T$-free subhypergraph of $H$ is at least \[ \frac{e(H)}{\triangle^{\frac{r-2}{r-1} + o(1)}}.\] For $r = 3$, this is tight up to the $o(1)$ term in the exponent. We also show that if $H$ is a random $n$-vertex triple system with edge-probability $p$ such that $pn^3\rightarrow\infty$ as $n\rightarrow\infty$, then with high probability as $n \rightarrow \infty$, the number of edges in a densest $T$-free subhypergraph is \[ \min\Bigl\{(1-o(1))p{n\choose3},p^{\frac{1}{3}}n^{2-o(1)}\Bigr\}.\] We use the method of containers together with probabilistic methods and a connection to the extremal problem for arithmetic progressions of length three due to Ruzsa and Szemerédi.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The de Bruijn-Erdos Theorem for hypergraphs

Fix integers $n \ge r \ge 2$. A clique partition of ${[n] \choose r}$ is a collection of proper subsets $A_1, A_2, ..., A_t \subset [n]$ such that $\bigcup_i{A_i \choose r}$ is a partition of ${[n] \choose r}$. Clique partitions are related to design theory, coding theory, projective geometry, and extremal combinatorics. Let $\cp(n,r)$ denote the minimum size of a clique partition of ${[n] \choose r}$. A classical theorem of de Bruijn and Erd\H os states that $\cp(n, 2) = n$ and also determines the extremal configurations. In this paper we study $\cp(n,r)$, and show in general that for each fixed $r \geq 3$, \[\cp(n,r) \geq (1 + o(1))n^{r/2} \quad \quad {as}n \to \infty.\] We conjecture $\cp(n,r) = (1 + o(1))n^{r/2}$, and prove this conjecture in a very strong sense for $r = 3$ by giving a characterization of optimal clique partitions of ${[n] \choose 3}$ for infinitely many $n$. Precisely, when $n = q^2 + 1$ and $q$ is a prime power, we show \[ \cp(n,3) = n\sqrt{n-1} \] and characterize those clique partitions achieving equality. We also give an absolute lower bound $\cp(n,r) \geq {n \choose r}/{q + r - 1 \choose r}$ when $n = q^2 + q + r - 1$, and for each $r$ characterize the finitely many configurations achieving equality with the lower bound. Finally we note the connection of $\cp(n,r)$ to extremal graph theory, and determine some new asymptotically sharp bounds for the Zarankiewicz problem.

0 citations0 reviewsNo code linkedOpen access