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

Vikram Kamat

Vikram Kamat contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CODiscrete MathematicsData Structures and Algorithms

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
3topics
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

6 published item(s)

preprint2022arXiv

On intersecting families of independent sets in trees

A family of sets is intersecting if every pair of its sets intersect. A star is a family with some element (a center) in each of its sets. The classical 1961 result of Erdős, Ko, and Rado states that every intersecting family of r-sets with $r\leq n/2$ has size at most that of a star. We say that graph G is r-EKR if, among all intersecting families of independent r-sets of G, the largest is attained by a star. In 2005 Holroyd and Talbot conjectured that every graph G is r-EKR for all $1\leq r\leq μ(G)/2$, where $μ(G)$ is the size of the smallest maximal independent set in G. We verified the conjecture in 2011 for all chordal graphs containing an isolated vertex. For graphs without isolated vertices it is difficult to determine the center of the largest star, which is often necessary to prove that they are EKR. A tree has the leaf property if its largest star occurs on one of its leaves. We proved that every tree T has the leaf property when $r\leq 4$, and in 2017 Borg and other authors gave examples of families of trees not having the leaf property when $r\geq 5$. A split vertex in a tree is a vertex of degree at least 3. A spider is a tree with exactly one split vertex. Here we prove that all spiders have the leaf property for all $r\leq α(G)$, where $α(G)$ is the independence number of $G$, and we characterize which of its leaves are maximum star centers. A pendant tree is one for which each of its split vertices is adjacent to a leaf. Here we show that all pendant trees have the leaf property for all $r\leq α(G)$. We also consider pendant trees with exactly two split vertices and provide partial results on the locations of their maximum star centers.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An Erdős-Ko-Rado Theorem for unions of length 2 paths

A family of sets is intersecting if any two sets in the family intersect. Given a graph $G$ and an integer $r\geq 1$, let $\mathcal{I}^{(r)}(G)$ denote the family of independent sets of size $r$ of $G$. For a vertex $v$ of $G$, the family of independent sets of size $r$ that contain $v$ is called an $r$-star. Then $G$ is said to be $r$-EKR if no intersecting subfamily of $ \mathcal{I}^{(r)}(G)$ is bigger than the largest $r$-star. Let $n$ be a positive integer, and let $G$ consist of the disjoint union of $n$ paths each of length 2. We prove that if $1 \leq r \leq n/2$, then $G$ is $r$-EKR. This affirms a longstanding conjecture of Holroyd and Talbot for this class of graphs and can be seen as an analogue of a well-known theorem on signed sets, proved using different methods, by Deza and Frankl and by Bollobás and Leader. Our main approach is a novel probabilistic extension of Katona's elegant cycle method, which might be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An Erdős--Ko--Rado theorem for matchings in the complete graph

We consider the following higher-order analog of the Erdős--Ko--Rado theorem. For positive integers r and n with r<= n, let M^r_n be the family of all matchings of size r in the complete graph K_{2n}. For any edge e in E(K_{2n}), the family M^r_n(e), which consists of all sets in M^r_n containing e, is called the star centered at e. We prove that if r<n and A is an intersecting family of matchings in M^r_n, then |A|<=|M^r_n(e)|$, where e is an edge in E(K_{2n}). We also prove that equality holds if and only if A is a star. The main technique we use to prove the theorem is an analog of Katona&#39;s elegant cycle method.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On k-wise intersecting families of vertex sets in perfect matchings

We consider the following generalization of the seminal Erdős-Ko-Rado theorem, due to Frankl. For k>= 2, let F be a k-wise intersecting family of r-subsets of an n element set X, i.e. any k sets in F have a nonempty intersection. If r<= (k-1/k)n, then |F|<={n-1 \choose r-1}. We extend Frankl&#39;s theorem in a graph-theoretic direction. For a graph G, and r>=1, let P^r(G) be the family of all r-subsets of the vertex set of G such that every r-subset is either an independent set or contains a maximum independent set. We will consider k-wise intersecting subfamilies of this family for the graph M_n, where M_n is the perfect matching on 2n vertices, and prove an analog of Frankl&#39;s theorem. This result can also be considered as an extension of a theorem of Bollobás and Leader for intersecting families of independent vertex sets in M_n.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Parameterized Complexity of the Maximum Edge Coloring Problem

We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q>1 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. This problem is NP-hard for q>1, and has been well-studied from the point of view of approximation. Our main focus is the case when q=2, which is already theoretically intricate and practically relevant. We show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a linear vertex kernel.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On cross-intersecting families of independent sets in graphs

Let A_1,...,A_k be a collection of families of subsets of an n-element set. We say that this collection is cross-intersecting if for any i,j in [k] with i not equal to j, A in A_i and B in A_j implies that the intersection of A and B is nonempty. We consider a theorem of Hilton which gives a best possible upper bound on the sum of the cardinalities of uniform cross-intersecting subfamilies. We formulate a graph-theoretic analogue of Hilton&#39;s cross-intersection theorem, similar to the one developed by Holroyd, Spencer and Talbot for the Erdos-Ko-Rado theorem. In particular we build on a result of Borg and Leader for signed sets and prove a theorem for uniform cross-intersecting subfamilies of independent vertex subsets of a disjoint union of complete graphs. We proceed to obtain a result for a much larger class of graphs, namely chordal graphs and propose a conjecture for all graphs. We end by proving this conjecture for the cycle on n vertices.

0 citations0 reviewsNo code linkedOpen access