Journal ArticleForum of Mathematics, Sigma · March 18, 2024
Many problems and conjectures in extremal combinatorics concern polynomial inequalities between homomorphism densities of graphs where we allow edges to have real weights. Using the theory of graph limits, we can equivalently evaluate polynomial expression ...
Full textCite
Journal ArticleElectronic Journal of Combinatorics · January 1, 2024
Let G be a multipartite graph with partition V1, V2, …, Vk of V (G). Let di,j denote the edge density of the pair (Vi, Vj). An independent transversal is an independent set of G with exactly one vertex in each Vi . In this paper, we prove an asymptotically ...
Full textCite
Journal ArticleCombinatorica · 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 textCite
Journal ArticleAdvances 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 textCite
Journal ArticleCombinatorics Probability and Computing · March 1, 2023
We suggest two related conjectures dealing with the existence of spanning irregular subgraphs of graphs. The first asserts that any -regular graph on vertices contains a spanning subgraph in which the number of vertices of each degree between and deviates ...
Full textCite
Journal ArticleEuropean 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 textCite
Journal ArticleElectronic Journal of Combinatorics · January 1, 2023
Given a simple graph G, the irregularity strength of G, denoted s(G), is the least positive integer k such that there is a weight assignment on edges (Formula present) for which each vertex weight (Formula present) is unique amongst all (Formula present). ...
Full textCite
Journal ArticleCombinatorica · 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 textCite
Journal ArticleRevista 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 textCite
Journal ArticleRandom 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 textCite
Journal ArticleSIAM 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 textCite
Journal ArticleSIAM 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 textCite
Journal ArticleIEEE 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 textCite
ConferenceLeibniz 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 textCite
ConferenceCombinatorics 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 textCite
Journal ArticleIEEE 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 textCite
Journal ArticleJournal 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 textCite
ConferenceProceedings 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 textCite
Journal ArticleElectronic 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 textCite
ConferenceProceedings 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 textCite
Conference31st 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
ConferenceProceedings 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 textCite
Journal ArticleIEEE 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 textCite
Conference30th 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
Journal ArticleElectronic 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 textCite
Journal ArticleEuropean 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 textCite
Journal ArticleStatistics 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 textCite
