Scholars@Duke
Fan Wei

Fan Wei

Assistant Professor of Mathematics
Mathematics
fan.wei@duke.edu
Duke Mathematics, Campus Box 90320, Durham, NC 27708
Box 90320, Durham, NC 27708

Selected Publications

On the Asymptotic Confirmation of the Faudree–Lehel Conjecture for General Graphs

Journal Article Combinatorica · August 1, 2023 Given a simple graph G, the irregularity strength of G, denoted by s(G), is the least positive integer k such that there is a weight assignment on edges f: E(G) → { 1 , 2 , ⋯ , k} attributing distinct weighted degrees: f~ (v) : = ∑ u:{u,v}∈E(G)f({ u, v}) t ... Full text Cite

Phase transition of degeneracy in minor-closed families

Journal Article Advances in Applied Mathematics · May 1, 2023 Given an infinite family G of graphs and a monotone property P, an (upper) threshold for G and P is a “fastest growing” function p:N→[0,1] such that limn→∞⁡Pr⁡(Gn(p(n))∈P)=1 for any sequence (Gn)n∈N over G with limn→∞⁡|V(Gn)|=∞, where Gn(p(n)) is the rando ... Full text Cite

Irregular subgraphs

Journal Article Combinatorics, Probability and Computing · March 2023 AbstractWe suggest two related conjectures dealing with the existence of spanning irregular subgraphs of graphs. The first asserts that any Full text Cite

Threshold Ramsey multiplicity for paths and even cycles

Journal Article European Journal of Combinatorics · January 1, 2023 The Ramsey number r(H) of a graph H is the minimum integer n such that any two-coloring of the edges of the complete graph Kn contains a monochromatic copy of H. While this definition only asks for a single monochromatic copy of H, it is often the case tha ... Full text Cite

Non-Bipartite K-Common Graphs

Journal Article Combinatorica · February 1, 2022 A graph H is k-common if the number of monochromatic copies of H in a k-edge-coloring of Kn is asymptotically minimized by a random coloring. For every k, we construct a connected non-bipartite k-common graph. This resolves a problem raised by Jagger, Štov ... Full text Cite

THRESHOLD RAMSEY MULTIPLICITY FOR ODD CYCLES

Journal Article Revista de la Union Matematica Argentina · January 1, 2022 The Ramsey number r(H) of a graph H is the minimum n such that any two-coloring of the edges of the complete graph Kn contains a monochromatic copy of H. The threshold Ramsey multiplicity m(H) is then the minimum number of monochromatic copies of H taken o ... Full text Cite

On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices

Journal Article Random Structures and Algorithms · December 1, 2021 Given a k-vertex graph H and an integer n, what are the n-vertex graphs with the maximum number of induced copies of H? This question is closely related to the inducibility problem introduced by Pippenger and Golumbic in 1975, which asks for the maximum po ... Full text Cite

On the number of cliques in graphs with a forbidden subdivision or immersion

Journal Article SIAM Journal on Discrete Mathematics · January 1, 2020 How many cliques can a graph on n vertices have with a forbidden substructure? Extremal problems of this sort have been studied for a long time. This paper studies the maximum possible number of cliques in a graph on n vertices with a forbidden clique subd ... Full text Cite

Finding cliques in social networks: A new distribution-free model

Journal Article SIAM Journal on Computing · January 1, 2020 We propose a new distribution-free model of social networks. Our definitions are motivated by one of the most universal signatures of social networks, triadic closure|the property that pairs of vertices with common neighbors tend to be adjacent. Our most b ... Full text Cite

Dynamic Structure Embedded Online Multiple-Output Regression for Streaming Data.

Journal Article IEEE transactions on pattern analysis and machine intelligence · February 2019 Online multiple-output regression is an important machine learning technique for modeling, predicting, and compressing multi-dimensional correlated data streams. In this paper, we propose a novel online multiple-output regression method, called MORES, for ... Full text Cite

Finding cliques in social networks: A new distribution-free model

Conference Leibniz International Proceedings in Informatics, LIPIcs · July 1, 2018 We propose a new distribution-free model of social networks. Our definitions are motivated by one of the most universal signatures of social networks, triadic closure - the property that pairs of vertices with common neighbors tend to be adjacent. Our most ... Full text Cite

Fast Property Testing and Metrics for Permutations

Conference Combinatorics Probability and Computing · July 1, 2018 The goal of property testing is to quickly distinguish between objects which satisfy a property and objects that are -far from satisfying the property. There are now several general results in this area which show that natural properties of combinatorial o ... Full text Cite

A Self-Paced Regularization Framework for Multilabel Learning.

Journal Article IEEE transactions on neural networks and learning systems · June 2018 In this brief, we propose a novel multilabel learning framework, called multilabel self-paced learning, in an attempt to incorporate the SPL scheme into the regime of multilabel learning. Specifically, we first propose a new multilabel learning formulation ... Full text Cite

On the number of cliques in graphs with a forbidden minor

Journal Article Journal of Combinatorial Theory. Series B · September 1, 2017 Reed and Wood and independently Norine, Seymour, Thomas, and Wollan proved that for each positive integer t there is a constant c(t) such that every graph on n vertices with no Kt-minor has at most c(t)n cliques. Wood asked in 2007 if we can take c(t)=ct f ... Full text Cite

Graph edge partitioning via neighborhood heuristic

Conference Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · August 13, 2017 We consider the edge partitioning problem that partitions the edges of an input graph into multiple balanced components, while minimizing the total number of vertices replicated (one vertex might appear in more than one partition). This problem is critical ... Full text Cite

On the Local Approach to Sidorenko's Conjecture

Journal Article Electronic Notes in Discrete Mathematics · August 1, 2017 A well-known conjecture of Erdős-Simonovits and Sidorenko states that, if H is a bipartite graph, then the random graph with edge density p has in expectation asymptotically the minimum number of copies of H over all graphs of the same number of vertices a ... Full text Cite

Local max-cut in smoothed polynomial time

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 19, 2017 In 1988, Johnson, Papadimitriou and Yannakakis wrote that "Practically all the empirical evidence would lead us to conclude that finding locally optimal solutions is much easier than solving NP-hard problems". Since then the empirical evidence has continue ... Full text Cite

Self-paced multi-task learning

Conference 31st AAAI Conference on Artificial Intelligence, AAAI 2017 · January 1, 2017 Multi-task learning is a paradigm, where multiple tasks are jointly learnt. Previous multi-task learning models usually treat all tasks and instances per task equally during learning. Inspired by the fact that humans often learn from easy concepts to hard ... Cite

Permutation property testing under different metrics with low query complexity

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2017 The goal of property testing is to quickly distinguish between objects which satisfy a property and objects that are far from satisfying the property. There are now several general results in this area which show that natural properties of combinatorial ob ... Full text Cite

Max-Margin-Based Discriminative Feature Learning.

Journal Article IEEE transactions on neural networks and learning systems · December 2016 In this brief, we propose a new max-margin-based discriminative feature learning method. In particular, we aim at learning a low-dimensional feature representation, so as to maximize the global margin of the data and make the samples from the same class as ... Full text Cite

On the Asymptotic Confirmation of the Faudree–Lehel Conjecture for General Graphs

Journal Article Combinatorica · August 1, 2023 Given a simple graph G, the irregularity strength of G, denoted by s(G), is the least positive integer k such that there is a weight assignment on edges f: E(G) → { 1 , 2 , ⋯ , k} attributing distinct weighted degrees: f~ (v) : = ∑ u:{u,v}∈E(G)f({ u, v}) t ... Full text Cite

Phase transition of degeneracy in minor-closed families

Journal Article Advances in Applied Mathematics · May 1, 2023 Given an infinite family G of graphs and a monotone property P, an (upper) threshold for G and P is a “fastest growing” function p:N→[0,1] such that limn→∞⁡Pr⁡(Gn(p(n))∈P)=1 for any sequence (Gn)n∈N over G with limn→∞⁡|V(Gn)|=∞, where Gn(p(n)) is the rando ... Full text Cite

Irregular subgraphs

Journal Article Combinatorics, Probability and Computing · March 2023 AbstractWe suggest two related conjectures dealing with the existence of spanning irregular subgraphs of graphs. The first asserts that any Full text Cite

Threshold Ramsey multiplicity for paths and even cycles

Journal Article European Journal of Combinatorics · January 1, 2023 The Ramsey number r(H) of a graph H is the minimum integer n such that any two-coloring of the edges of the complete graph Kn contains a monochromatic copy of H. While this definition only asks for a single monochromatic copy of H, it is often the case tha ... Full text Cite

Non-Bipartite K-Common Graphs

Journal Article Combinatorica · February 1, 2022 A graph H is k-common if the number of monochromatic copies of H in a k-edge-coloring of Kn is asymptotically minimized by a random coloring. For every k, we construct a connected non-bipartite k-common graph. This resolves a problem raised by Jagger, Štov ... Full text Cite

THRESHOLD RAMSEY MULTIPLICITY FOR ODD CYCLES

Journal Article Revista de la Union Matematica Argentina · January 1, 2022 The Ramsey number r(H) of a graph H is the minimum n such that any two-coloring of the edges of the complete graph Kn contains a monochromatic copy of H. The threshold Ramsey multiplicity m(H) is then the minimum number of monochromatic copies of H taken o ... Full text Cite

On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices

Journal Article Random Structures and Algorithms · December 1, 2021 Given a k-vertex graph H and an integer n, what are the n-vertex graphs with the maximum number of induced copies of H? This question is closely related to the inducibility problem introduced by Pippenger and Golumbic in 1975, which asks for the maximum po ... Full text Cite

On the number of cliques in graphs with a forbidden subdivision or immersion

Journal Article SIAM Journal on Discrete Mathematics · January 1, 2020 How many cliques can a graph on n vertices have with a forbidden substructure? Extremal problems of this sort have been studied for a long time. This paper studies the maximum possible number of cliques in a graph on n vertices with a forbidden clique subd ... Full text Cite

Finding cliques in social networks: A new distribution-free model

Journal Article SIAM Journal on Computing · January 1, 2020 We propose a new distribution-free model of social networks. Our definitions are motivated by one of the most universal signatures of social networks, triadic closure|the property that pairs of vertices with common neighbors tend to be adjacent. Our most b ... Full text Cite

Dynamic Structure Embedded Online Multiple-Output Regression for Streaming Data.

Journal Article IEEE transactions on pattern analysis and machine intelligence · February 2019 Online multiple-output regression is an important machine learning technique for modeling, predicting, and compressing multi-dimensional correlated data streams. In this paper, we propose a novel online multiple-output regression method, called MORES, for ... Full text Cite

Finding cliques in social networks: A new distribution-free model

Conference Leibniz International Proceedings in Informatics, LIPIcs · July 1, 2018 We propose a new distribution-free model of social networks. Our definitions are motivated by one of the most universal signatures of social networks, triadic closure - the property that pairs of vertices with common neighbors tend to be adjacent. Our most ... Full text Cite

Fast Property Testing and Metrics for Permutations

Conference Combinatorics Probability and Computing · July 1, 2018 The goal of property testing is to quickly distinguish between objects which satisfy a property and objects that are -far from satisfying the property. There are now several general results in this area which show that natural properties of combinatorial o ... Full text Cite

A Self-Paced Regularization Framework for Multilabel Learning.

Journal Article IEEE transactions on neural networks and learning systems · June 2018 In this brief, we propose a novel multilabel learning framework, called multilabel self-paced learning, in an attempt to incorporate the SPL scheme into the regime of multilabel learning. Specifically, we first propose a new multilabel learning formulation ... Full text Cite

On the number of cliques in graphs with a forbidden minor

Journal Article Journal of Combinatorial Theory. Series B · September 1, 2017 Reed and Wood and independently Norine, Seymour, Thomas, and Wollan proved that for each positive integer t there is a constant c(t) such that every graph on n vertices with no Kt-minor has at most c(t)n cliques. Wood asked in 2007 if we can take c(t)=ct f ... Full text Cite

Graph edge partitioning via neighborhood heuristic

Conference Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · August 13, 2017 We consider the edge partitioning problem that partitions the edges of an input graph into multiple balanced components, while minimizing the total number of vertices replicated (one vertex might appear in more than one partition). This problem is critical ... Full text Cite

On the Local Approach to Sidorenko's Conjecture

Journal Article Electronic Notes in Discrete Mathematics · August 1, 2017 A well-known conjecture of Erdős-Simonovits and Sidorenko states that, if H is a bipartite graph, then the random graph with edge density p has in expectation asymptotically the minimum number of copies of H over all graphs of the same number of vertices a ... Full text Cite

Local max-cut in smoothed polynomial time

Conference Proceedings of the Annual ACM Symposium on Theory of Computing · June 19, 2017 In 1988, Johnson, Papadimitriou and Yannakakis wrote that "Practically all the empirical evidence would lead us to conclude that finding locally optimal solutions is much easier than solving NP-hard problems". Since then the empirical evidence has continue ... Full text Cite

Self-paced multi-task learning

Conference 31st AAAI Conference on Artificial Intelligence, AAAI 2017 · January 1, 2017 Multi-task learning is a paradigm, where multiple tasks are jointly learnt. Previous multi-task learning models usually treat all tasks and instances per task equally during learning. Inspired by the fact that humans often learn from easy concepts to hard ... Cite

Permutation property testing under different metrics with low query complexity

Conference Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2017 The goal of property testing is to quickly distinguish between objects which satisfy a property and objects that are far from satisfying the property. There are now several general results in this area which show that natural properties of combinatorial ob ... Full text Cite

Max-Margin-Based Discriminative Feature Learning.

Journal Article IEEE transactions on neural networks and learning systems · December 2016 In this brief, we propose a new max-margin-based discriminative feature learning method. In particular, we aim at learning a low-dimensional feature representation, so as to maximize the global margin of the data and make the samples from the same class as ... Full text Cite

Spatially regularized streaming sensor selection

Conference 30th AAAI Conference on Artificial Intelligence, AAAI 2016 · January 1, 2016 Sensor selection has become an active topic aimed at energy saving, information overload prevention, and communication cost planning in sensor networks. In many real applications, often the sensors' observation regions have overlaps and thus the sensor net ... Cite

Touchless User Interface Utilizing Several Types of Sensing Technology

Journal Article FUJITSU SCIENTIFIC & TECHNICAL JOURNAL · 2014 Link to item Cite

Involutions on standard Young tableaux and divisors on metric graphs

Journal Article Electronic Journal of Combinatorics · September 6, 2013 We elaborate upon a bijection discovered by Cools, Draisma, Payne, and Robeva (2012) between the set of rectangular standard Young tableaux and the set of equivalence classes of chip configurations on certain metric graphs under the relation of linear equi ... Full text Cite

Product decompositions of the symmetric group induced by separable permutations

Journal Article European Journal of Combinatorics · May 1, 2012 In this paper we consider the rank generating function of a separable permutation π in the weak Bruhat order on the two intervals [id,π] and [π,w0], where w0=n,n-1,..., 1. We show a surprising result that the product of these two generating functions is th ... Full text Cite

Two-sample Dvoretzky-Kiefer-Wolfowitz inequalities

Journal Article Statistics and Probability Letters · March 1, 2012 The Dvoretzky-Kiefer-Wolfowitz (DKW) inequality says that if F n is an empirical distribution function for variables i.i.d. with a distribution function F, and K n is the Kolmogorov statistic nsupx{pipe}(Fn-F)(x){pipe}, then there is a constant C such that ... Full text Cite