Source author record

Jiaxi Nie

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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